16 Apr 2005 11:10:45 -0400

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) |

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.