Re: converting this grammar to LL1

"Te-Cheng Shen" <te-cheng_shen@agilent.com>
6 Nov 2002 11:50:10 -0500

          From comp.compilers

Related articles
converting this grammar to LL1 te-cheng_shen@agilent.com (Te-Cheng Shen) (2002-10-20)
Re: converting this grammar to LL1 chungyc@pobox.com (Yoo Chung) (2002-10-24)
Re: converting this grammar to LL1 joachim_d@gmx.de (Joachim Durchholz) (2002-10-24)
Re: converting this grammar to LL1 patrick.volteau@st.com (Patrick Volteau) (2002-10-25)
Re: converting this grammar to LL1 andreas.gieriet@externsoft.ch (Andreas Gieriet) (2002-10-25)
Re: converting this grammar to LL1 te-cheng_shen@agilent.com (Te-Cheng Shen) (2002-11-06)
Re: converting this grammar to LL1 joachim_d@gmx.de (Joachim Durchholz) (2002-11-07)
Re: converting this grammar to LL1 slk12@earthlink.net (SLK Parsers) (2002-11-12)
| List of all articles for this month |

From: "Te-Cheng Shen" <te-cheng_shen@agilent.com>
Newsgroups: comp.compilers
Date: 6 Nov 2002 11:50:10 -0500
Organization: Agilent Technologies
References: 02-10-097 02-10-103
Keywords: LL(1), parse
Posted-Date: 06 Nov 2002 11:50:10 EST

> > E-> F = E
> > E -> F
> >
> > F -> id| & id | ( E ) | E [ int ]
>
> I think you'll have to factor out the e[int] alternative as well. How
> the exact rules should be depends on how you want to parse E=E[int]: as
> (E=E)[int] or as E=(E[int])?


If I modify the last rule in the above grammar to


F->id|&id|(E) | F[int]


(just replace 'E' with 'F')


the purpose of last rule is to generate E=(E[int]) instead of (E=E)[int]


then, the modified grammar should be unambiguous.


The problem is "How do I know the modified grammar generate the SAME
language as the original one?"
Or I should ask this question "Is there any algorithm to make this kind of
ambiguity go away?" I am NOT asking for
very general algorithms which can translate ANY ambiguous grammar to
umanbiguous ones because they
might not exist.


For example, there are some general rules to translate this kind of
ambiguous grammar


E->E+E


to either left-recursive or right-recursive grammars. With those
general rules, we are sure that modified grammar can alwasy generate
the same language.


Any rules to translate ambiguity from F->E[int]


thanks


tcs


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.