Re: converting this grammar to LL1

"Andreas Gieriet" <andreas.gieriet@externsoft.ch>
25 Oct 2002 00:12:49 -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: "Andreas Gieriet" <andreas.gieriet@externsoft.ch>
Newsgroups: comp.compilers
Date: 25 Oct 2002 00:12:49 -0400
Organization: eXternSoft GmbH
References: 02-10-097
Keywords: parse, LL(1)
Posted-Date: 25 Oct 2002 00:12:49 EDT

Try this (EBNF):


  E: P R .
  P: id | '&' id | '(' E ')' .
  R: [ Q R ] .
  Q: '=' E | '[' int ']' .


This should be LL1.






How to get there:


1) combine non-ambiguous parts to one production:
          E: P | E '=' E | E '[' int ']' .
          P: id | '&' id | '(' E ')' .


2) rewrite the ambiguous parts to a prefix and a suffix.
          E: P | E Q .
          Q: '=' E | '[' int ']' .


3) eliminate left recursion:
          E: P R .
          R: [ Q R ] .


All three modifications result in the grammer stated above.


HTH


Andi




Te-Cheng Shen schrieb:
>
> Hello:
> This is supposed to be really simple but I have worked on it for hours
> but all generated grammar are ambiguous and I am not sure why.
>
> This is the grammar
>
> E->id | &id | (E) | E[int] | E=E
>
> First of all, can this grammar make LL1? I am not sure.
>
> What I am doing is:
> Make this production
>
> E-> E = E
>
> to
>
> E -> F = E
> E -> F
>
> according to algorithms mentioned in textbook.
>
> Then the resulting grammar is
>
> 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.
>
> Can anyone show me how to make it unambiguous?
>
> thanks a lot
>
> tcs


--
Andreas Gieriet mailto:andreas.gieriet@externsoft.ch
eXternSoft GmbH http://www.externsoft.com/
Zurlindenstrasse 49 phone:++41 1 454 3077
CH-8003 Zurich/SWITZERLAND fax: ++41 1 454 3078


Post a followup to this message

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