Re: LALR1 and LL1

Sylvain Schmitz <schmitz@i3s.unice.fr>
2 May 2005 14:26:03 -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: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: 2 May 2005 14:26:03 -0400
Organization: Compilers Central
References: 05-04-023 05-04-041 05-04-059 05-04-088
Keywords: parse, theory
Posted-Date: 02 May 2005 14:26:03 EDT

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.


--
Regards,


      Sylvain

Post a followup to this message

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