Re: LALR?

> Hello,


> I've read the book 'Parsing Techniques - A pratical guide' and I
> found it very good, but I'd like to know if there are other
> documents or papers on the web about lalr parsing, examples, or a
> description of the DeRemer and Pennello algorithm. Can anybody point
> me to some links?


> Thanks to all,
> tano


Sadly, I have had a difficult time finding good information online
regarding LALR. My favorite source on this topic is: Compilers:
Principles, Techniques, and Tools by Aho, Sethi, and Ullman


They start with a conceptual overview of LR itself and then show the
reader successively complex class of LR grammars. These are: SLR,
canonical LR, and then the capstone LALR. SLR is somewhat limited in
capabilities. Canoncial LR was incrediably powerful, but at a
potentially crippling sizes for the parse tables (I think Knuth showed
this). The state information is encoded into the parse table can be
impractically large. LALR merges many of the almost duplicate
elements, thus reducing the parse table size significantly. While you
can generate an LALR parse table directly, it is a very good
experience to take a canoncial LR table and merge the duplicate items
by hand. The book takes this approach and you really get to see where
LALR is "fixing up" another grammar. It shows why we can and how we
can merge canonical LR items. Eliminating the duplicate items makes
some grammars not work with LALR, but not many.


I have really not done the book credit in this paragraph. The text
does a very fine teaching the reader LR related stuff.


- Tim

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