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

Hans-Peter Diettrich <DrDiettrich1@aol.com>
21 Jul 2006 14:06:51 -0400

          From comp.compilers

Related articles
Why LL(1) Parsers do not support left recursion? martin_lapierre@videotron.ca (DevInstinct) (2006-07-16)
RE: Why LL(1) Parsers do not support left recursion? qtj-query@shaw.ca (Quinn Tyler Jackson) (2006-07-16)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? tom@infoether.com (Tom Copeland) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? rahul.chaudhry@gmail.com (Rahul Chaudhry) (2006-07-18)
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-19)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? luvisi@andru.sonoma.edu (Andru Luvisi) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? egagnon@sablevm.org (Etienne Gagnon) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-23)
[23 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich1@aol.com>
Newsgroups: comp.compilers
Date: 21 Jul 2006 14:06:51 -0400
Organization: Compilers Central
References: 06-07-024 06-07-027 06-07-035 06-07-046
Keywords: parse
Posted-Date: 21 Jul 2006 14:06:51 EDT

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


Post a followup to this message

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