14 Mar 2003 11:24:41 -0500

Related articles |
---|

good LALR theory tutorial? newgroup.post@luisma.com (axis) (2003-03-09) |

Re: good LALR theory tutorial? nde@comp.leeds.ac.uk (Nick Efford) (2003-03-14) |

Re: good LALR theory tutorial? rda@lemma-one.com (Rob Arthan) (2003-03-14) |

Re: good LALR theory tutorial? urfaust@optushome.com.au (Faust) (2003-03-14) |

From: | Rob Arthan <rda@lemma-one.com> |

Newsgroups: | comp.compilers |

Date: | 14 Mar 2003 11:24:41 -0500 |

Organization: | Lemma 1 Ltd. |

References: | 03-03-026 |

Keywords: | parse, LALR, question |

Posted-Date: | 14 Mar 2003 11:24:41 EST |

axis wrote:

*> I'm reading the dragon book (Compilers: Principles, Techniques, and Tools)*

*> and the explanation of LALR method (well, specifically the LR(1) method,*

*> which then is then simplified to LALR) wasn't too clear. Most online*

*> resources I've found have a very similar explanations, or their examples*

*> are very limited. Anyone out there have a link to a good explanation, or*

*> maybe more extensive examples?*

*>*

*> Thanks!*

The dragon book describes the yacc algorithm which is a lot harder to

understand and also less efficient than some of the alternatives. It

put me off trying to understand LALR parsing properly for over 10

years. However, I've now get a working implementation and wish I'd

known what I now know a long time ago.

I couldn't find any very useful online links or even recent text-book

references, but the journal references that inspired me to revisit LALR

were:

F.DeRemer and F. Pennello, Efficient Computation of LALR(1) Look-Ahead Sets

TOPLAS. 1982. Volume 4.

M. Bermudez and G. Logothetis, Simple Computation of LALR(1) Lookahead Sets.

Information Processing Letters. 1989. Volume 31.

If you managed to come to grips with the description of SLR(1) in the

dragon book, then you will find the Bermudez-Logothetis method very easy to

understand - it just applies the same algorithms to a derived grammar which

takes account of left context in a very direct way. The DeRemer-Pennello

paper is rather longer but the method it describes is easy to understand

and, by various examples, they highlight a lot of potential mistakes you

can make in designing an LALR algorithm.

Rob Arthan (rda@lemma-one.com)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.