Re: good LALR theory tutorial?

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)

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