|LALR1 and LL1 email@example.com (Neelesh Bodas) (2005-04-11)|
|Re: LALR1 and LL1 firstname.lastname@example.org (Sylvain Schmitz) (2005-04-16)|
|Re: LALR1 and LL1 email@example.com (Karsten Nyblad) (2005-04-26)|
|Re: LALR1 and LL1 firstname.lastname@example.org (Sylvain Schmitz) (2005-04-26)|
|Re: LALR1 and LL1 email@example.com (2005-04-28)|
|Re: LALR1 and LL1 firstname.lastname@example.org (Karsten Nyblad) (2005-04-30)|
|Re: LALR1 and LL1 email@example.com (Sylvain Schmitz) (2005-05-02)|
|Re: LALR1 and LL1 firstname.lastname@example.org (Hans Aberg) (2005-05-02)|
|From:||Hans Aberg <email@example.com>|
|Date:||2 May 2005 14:29:12 -0400|
|References:||05-04-023 05-04-041 05-04-059 05-04-088 <427611B6.firstname.lastname@example.org>|
|Posted-Date:||02 May 2005 14:29:12 EDT|
At 13:40 +0200 2005/05/02, Sylvain Schmitz wrote:
>Hans Aberg wrote:
>>Do you have any reference? -- Akim Demaille sent me an example where LL(1)
>>isn't LR(1). :-) I reposted it here, but I have forgotten when.
>I could not find your post in the archives. Anyway this result is a
>very sure one; you can find a demonstration for it in
>_Parsing_Theory_ by Sippu and Soisalon-Soininen, vol. 2, pp.
>To give a more intuitive answer, an LL(k) parser is like an LR(k)
>parser with a semantic action embedded at the very beginning of
>every single rule: it has to decide immediately what to do, only
>looking at the "k" first tokens from this point of the rule. From
>there, proper inclusion of the set of all LL(k) grammars in the set
>of LR(k) grammars is obvious.
Let repost it here, then. It is from the Help-Bison mailing list
<http://mail.gnu.org/mailman/listinfo/help-bison>, 17 Jan 2002, from
>>>>> "Hans" == Hans Aberg <email@example.com> writes:
Hans> It is probably LL(1) then (modulo tweaks), which => LALR(1),
This is not absolutely true, although it is in practice. IIRC the
result holds when there are no empty rules. See for instance
or the errata of Andrew Appel about this book on compiler
Page 64. Figure 3.26 incorrectly shows LL(1) as a subset of
SLR. In fact, LL(1) is not even a subset of LALR(1): there is
an LL(1) grammar that is not LALR(1).
Shouldn't this be in the comp.compilers FAQ?
[If it's only come up twice since 1993, that doesn't seem so frequent. -John]
Return to the
Search the comp.compilers archives again.