Re: converting this grammar to LL1

"Patrick Volteau" <patrick.volteau@st.com>
25 Oct 2002 00:10:54 -0400

          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: "Patrick Volteau" <patrick.volteau@st.com>
Newsgroups: comp.compilers
Date: 25 Oct 2002 00:10:54 -0400
Organization: http://groups.google.com/
References: 02-10-097
Keywords: parse, LL(1)
Posted-Date: 25 Oct 2002 00:10:54 EDT

>
> E-> F = E
> E -> F
>
> F -> id| & id | ( E ) | E [ int ]
>
>
> then I apply another algorithm to eliminate left-recursions.
> then I apply another algorithm to left-factor this grammar.
>
>
> However, I use this tool LellRap to verify my resulted grammar. It is
> still ambiguous.
>


Well, I don't think your new grammar is ambiguous, but it doesn't mean
that it can be parsed by a LL1 automaton (which is probably what
LellRap
is trying to tell you). Let's try with two sentences:
"a=b" and "&a=b"
For "a=b", when I start the current token is id ("a") so I must derive
a rule that starts with F, but should I use E->F or E->F=E ? This is
where
the look-ahead token helps me: "=" tells me to use E->F=E.


For "&a=b", the current token is "&" and the look-ahead token is id,
which
does not allow to take decision between E->F and E->F=E. To take this
decision, I have to look more than just one token ahead (two in this
case).


I believe the following grammar is LL1 (basically I just eliminated
left recursions in your original grammar):
E -> E' F
F -> [ int ] F | = E' F | (epsilon)
E' -> id | & id | ( E )


Patrick.


Post a followup to this message

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