Re: LALR1 and LL1

Sylvain Schmitz <schmitz@i3s.unice.fr>
16 Apr 2005 11:10:45 -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: 16 Apr 2005 11:10:45 -0400
Organization: Compilers Central
References: 05-04-023
Keywords: parse, theory, comment

Neelesh Bodas wrote:
> is every LL1 grammar an LALR1 grammar?
> In either case (No/Yes), I would be thankful if I could get a
> counterexample/proof for the claim or any pointers for the same.


A counterexample found in Sippu and Soisalon-Soininen's monograph
_Parsing_Theory_:


S -> aA | bB
A -> Cc | Dd
B -> Cd | Dc
C -> FE
D -> FH
E -> empty
F -> empty
H -> empty


This grammar is SLL(1) and thus LL(1), but is not LALR(k) for any k: in
the state reached when reading "aF" or "bF", one can reduce the empty
string to E or H. We have lost track of the first token read---"a" or
"b"---and the allowed lookaheads are "c" and "d" for both reductions.


You will find in the same monograph that every reduced LL(1) grammar in
which no nonterminal derives only the empty string is an LALR(1)
grammar. And for k >= 2, there are reduced \epsilon-free LL(k) grammars
which are not LALR(k), like the following one:


S -> aA | bB
A -> Cc | Dd
B -> Cd | Dc
C -> E
D -> H
E -> g
H -> g


This grammar is SLL(2) but not LALR(k) for any k.


--
Hope that helps,


      Sylvain
[Are LL1 languages, as opposed to grammars, LALR languages? -John]


Post a followup to this message

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