Re: Why LL(1) Parsers do not support left recursion?

"DevInstinct" <martin_lapierre@videotron.ca> asked:
> My question: why is that? In which case a LL(1) parser can enter
> infinite recursivity?
>
> I can't find a good example that demonstrates that.


Quinn Tyler Jackson answered:
> expr ::= expr "+" expr;
> expr ::= '[0-9]+';
>
> OK, using a top-down approach, parse:
>
> 5+2
>
> As soon as you enter expr, you enter expr, which brings you to expr, which
> brings you to expr, after which you enter expr, ....


Hans-Peter Diettrich <DrDiettrich1@aol.com> challenged:
> This example applies to both LL and LR parsers. It should be clear that
> a parser generator should handle such cases appropriately.
>
> In the case of an LL parser, a recursive call can occur only after a
> token has been consumed.


An LL parser generator cannot handle the case correctly, as the FIRST
of both alternatives is 0-9. Thus, while it would be nice if an LL
parser would wait to consume a token before making a recursive call,
the LL algorithm requires one to make the recursive call before
consuming the token, because making the call is necessary to allow the
called procedure to consume the token. It also isn't a solution
simply not to make the recursive call, for if you don't make the
recursive call, you simply have eliminated the recursive rule from the
grammar. If you simply wait to make the recursive call until after
the token has been consumed, you have changed the grammar in another
way.


The point is that in an LL parser, you need to determine by looking at
the lookahead (FIRST sets in this case) how many calls must be made,
because you must make exactly the right series of calls before
consuming the token.


However, Dodi's assertion that LR parsers should (will) properly
handle this case is correct.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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