Re: Bison version of the LALR(1) algorithm

John R. Levine wrote:
>>Can somebody give a reference to a description of the LALR(1)
>>algorithm that Bison uses?
>
>The REFERENCES file in the bison source distribution says:


Oops, I should have read this one. :-)


>Also, Bison uses a faster but less space-efficient encoding for the
>parse tables (see Corbett's PhD thesis from Berkeley, "Static
>Semantics in Compiler Error Recovery", June 1985, Report No. UCB/CSD
>85/251), and more modern technique for generating the lookahead sets.


I have it, though only on a pixel format; it used to be at
    http://www.lrde.epita.fr/people/akim/download/corbett-phd-tiffs.tar.gz
which is a copy of the one in the Berkeley library. Corbett says that the
thesis TeX sources, he has only on an old tape which he does know if he
can read anymore.


>(See "Efficient Construction of LALR(1) Lookahead Sets" by F. DeRemer
>and A. Pennello, in ACM TOPLS Vol 4 No 4, October 1982. Their
>technique is the standard one now.)


The Aho et al book mentions both this reference and a "more efficient
LALR(1)", but it does not say if it is the algorithm of the reference. The
book at http://www.cs.vu.nl/~dick/PTAPG.html explains how to produce
non-deterministic parsers from grammars.


    Hans Aberg * Email: Hans Aberg <haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

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