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

Chris F Clark schrieb:


> An LL parser generator cannot handle the case correctly, as the FIRST
> of both alternatives is 0-9.


What's "correct" handling of such a case? LR parser generators also use
heuristics in ambiguous situations.


> 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.


But the procedure already *has* been called, so it IMO is allowed 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.


I agree that parser generators tend to change the grammar, in order to
resolve conflicts. The sample grammar contains no indication about the
grouping of the operation, but what does that *mean*? Does it mean
that the grammar is useless, invalid, or simply ambiguous? Provided
that the grammar is considered to be ambiguous, a parser generator
either can reject it, or do whatever it likes.


Let me give a more simplified grammar:


expr ::= expr;
expr ::= '[0-9]+';


Here an LL parser might enter infinite recursion *before* consuming a
token, whereas an LR parser might recurse *after* consuming a token.


>
> 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.


It's not a matter of the parser, but instead of the parser generator. I
see no reason why a parser generator should be able to create an LR
parser for the original grammer, but not an LL parser. And, for
completeness, a parser generator IMO should reject the grammar anyhow.


DoDi

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