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

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

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