Re: LALR1 and LL1

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]

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