Re: Seamlessly parsing left-recursive grammars with LL parsers ?

"Matt O'Connor" <angagon@earthlink.net>
27 Mar 2005 12:50:36 -0500

          From comp.compilers

Related articles
Seamlessly parsing left-recursive grammars with LL parsers ? louis@mulliemedia.com (Louis Mullie) (2005-03-20)
Re: Seamlessly parsing left-recursive grammars with LL parsers ? angagon@earthlink.net (Matt O'Connor) (2005-03-27)
Re: Seamlessly parsing left-recursive grammars with LL parsers ? branco.medeiros@gmail.com (2005-03-31)
Re: Seamlessly parsing left-recursive grammars with LL parsers ? louis@mulliemedia.com (Louis Mullie) (2005-04-02)
| List of all articles for this month |

From: "Matt O'Connor" <angagon@earthlink.net>
Newsgroups: comp.compilers
Date: 27 Mar 2005 12:50:36 -0500
Organization: Compilers Central
References: 05-03-079
Keywords: parse, LL(1)

Louis Mullie wrote:
> To parse : 6 + 3 + 2
>
> (token) num := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
> add := add '+' term
> term := num
>
> Obviously, 'add' would infinitely recurse in an LL parser.
> Now, consider the following transformation to the grammar :
> ----------------------------------------------------------------------------
> input = reverseOrder(input);
> foreach (grammar.nonterminals as symbol) {
> if (symbol.isLeftRecursive()) symbol.rule =
> reverseOrder(symbol.rule) + '|' + symbol;
> }


Hmm, what if you have a grammar like this (a grammar with more than 3
elements on the right-hand side):
add := add '+' '*' term
term := num


would it not become:


add := term '*' '+' add | term
term := num


Which isn't right, the ordering is changed.


Also, simply flipping the "outside" non-terminals (here, add and term)
will probably introduce extra complications.


> The grammar becomes :
> 2 + 3 + 6
> (token) num := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
> add := term '+' add | term
> term := num


This also changes the meaning of the grammar. Before add couldn't
produce just a number, now it can.


Oh, also it is my understanding that LR grammars are a superset of LL
grammars.


Matt


Post a followup to this message

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