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

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/

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