2 May 2005 14:29:12 -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: | 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.