Re: LALR1 and LL1

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.
>239--248.
>
>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
Akim Demaille:


>>>>> "Hans" == Hans Aberg <haberg@matematik.su.se> 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


                  http://compilers.iecc.com/comparch/article/93-09-025


or the errata of Andrew Appel about this book on compiler
implementation:


                  http://www.cs.princeton.edu/~appel/modern/basic/ml/errata.html


                  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]

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