Re: LALR1 and LL1

Hans Aberg <>
2 May 2005 14:29:12 -0400

          From comp.compilers

Related articles
LALR1 and LL1 (Neelesh Bodas) (2005-04-11)
Re: LALR1 and LL1 (Sylvain Schmitz) (2005-04-16)
Re: LALR1 and LL1 (Karsten Nyblad) (2005-04-26)
Re: LALR1 and LL1 (Sylvain Schmitz) (2005-04-26)
Re: LALR1 and LL1 (2005-04-28)
Re: LALR1 and LL1 (Karsten Nyblad) (2005-04-30)
Re: LALR1 and LL1 (Sylvain Schmitz) (2005-05-02)
Re: LALR1 and LL1 (Hans Aberg) (2005-05-02)
| List of all articles for this month |

From: Hans Aberg <>
Newsgroups: comp.compilers
Date: 2 May 2005 14:29:12 -0400
Organization: Compilers Central
References: 05-04-023 05-04-041 05-04-059 05-04-088 <>
Keywords: parse
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
<>, 17 Jan 2002, from
Akim Demaille:

>>>>> "Hans" == Hans Aberg <> 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?
      Hans Aberg
[If it's only come up twice since 1993, that doesn't seem so frequent. -John]

Post a followup to this message

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