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

Max Hailperin <max@gustavus.edu>
22 Jul 2006 18:23:43 -0400

          From comp.compilers

Related articles
[5 earlier articles]
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)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-23)
Re: Why LL(1) Parsers do not support left recursion? cbarron413@adelphia.net (Carl Barron) (2006-07-24)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-25)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-25)
[19 later articles]
| List of all articles for this month |

From: Max Hailperin <max@gustavus.edu>
Newsgroups: comp.compilers
Date: 22 Jul 2006 18:23:43 -0400
Organization: Compilers Central
References: 06-07-024 06-07-027 06-07-035 06-07-046 06-07-050 06-07-055
Keywords: parse

Chris F Clark <cfc@shell01.TheWorld.com> writes:
....
> > It's not a matter of the parser, but instead of the parser generator.
>
> Ok, let me make that more clear. No parser generator executing the LL
> algorithm for constructing a parser, can construct a parser from a
> grammar with left-recursion. A parser generator running any LR
> (e.g. LR(0), SLR, LALR, canonical LR, minimal state LR, etc.)
> algorithm can construct parsers for left-recursive grammars, presuming
> that grammar has no conflicts (and Andru's grammar is conflict-free).
....


You seem to be conceding too much here. The essential difference is
in the parsers, not just the parser generators. Recall (as I
explained in http://compilers.iecc.com/comparch/article/06-04-136 )
that an LR parser is a shift/reduce parser whereas an LL parser is a
confirm/expand parser. Each also has a control that decides at each
step which of the two possible actions to take (whether to shift or
reduce in an LR parser, whether to confirm or expand in an LL parser).
The parser generator only influences that control function, not what
the two possible actions are. Yet the issue with left recursion stems
directly from the available actions, not from the control. For a
left-recursive grammar, no control -- no matter how it works or how it
was generated -- can possibly decide between confirming and expanding
given only the previous input and a bounded amount of lookahead into
the future input. Deciding between shifting and reducing, on the
other hand is possible.


  -Max Hailperin
    Professor of Computer Science
    Chair, Mathematics and Computer Science Department
    Gustavus Adolphus College
    http://www.gustavus.edu/+max/


Post a followup to this message

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