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

Hans-Peter Diettrich <DrDiettrich1@aol.com>
22 Jul 2006 18:23:09 -0400

          From comp.compilers

Related articles
[4 earlier articles]
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)
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)
[24 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich1@aol.com>
Newsgroups: comp.compilers
Date: 22 Jul 2006 18:23:09 -0400
Organization: Compilers Central
References: 06-07-024 06-07-027 06-07-035 06-07-046 06-07-050 06-07-055
Keywords: LL(1), parse

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


Post a followup to this message

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