Re: LALR1 and LL1

Hans Aberg <haberg@math.su.se>
2 May 2005 14:29:12 -0400

          From comp.compilers

Related articles
LALR1 and LL1 neelesh.bodas@gmail.com (Neelesh Bodas) (2005-04-11)
Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-16)
Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-26)
Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-04-26)
Re: LALR1 and LL1 haberg@math.su.se (2005-04-28)
Re: LALR1 and LL1 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-04-30)
Re: LALR1 and LL1 schmitz@i3s.unice.fr (Sylvain Schmitz) (2005-05-02)
Re: LALR1 and LL1 haberg@math.su.se (Hans Aberg) (2005-05-02)
| List of all articles for this month |

From: Hans Aberg <haberg@math.su.se>
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 <427611B6.4090902@i3s.unice.fr>
Keywords: parse

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]



Post a followup to this message

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