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

Chris F Clark schrieb:


> Preamble: excuse this note for being excessively harsh. Dodi normally
> posts correct information, and as such deserves to be held to a high
> standard, cognizant of the respect he has earned. However, he pushed
> a hot button of mine by suggesting that left-recursion was some
> hueristic thing...


Let me summarize my points (John, you may drop my long answer ;-)


1. LL parsers cannot handle left recursion, whereas LR parsers cannot
handle right recursion.


2. Most languages are ambiguous at the syntax level, so that implicit
disambiguation (longest match...) or explicit semantical constraints
must be introduced. (see: dangling else...).


3. Only LL(1) recursive descent parsers are readable, that's why no
LL(k) parser generators exist, in contrast to LR(k) parser generators.


4. When at least one terminal must be consumed, before a recursive
invocation of a rule, no infinite recursion can occur. (every loop will
terminate after all terminals in the input stream have been consumed)


Any objections, so far?




Ad (1+2): We should keep grammars apart from languages. Most languages
require recursive grammars, but allow for both left or right recursive
grammars.
Languages with "expr '+' expr" or "list ',' list" can be parsed in
multiple ways. Unless there exist additional (semantical) restrictions,
correct and equivalent left or right recursive grammars can be
constructed for such languages.
And when a human is allowed to disambiguate a grammar for such a
language himself, a parser generator should be allowed to do the same ;-)


Ad (3): This is the only reason for the preference of LR parsers. Why
spend time with tweaking a grammar to LR(1)/LL(1), when a parser
generator for LR(k) is available?


DoDi

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