15 Dec 2001 00:37:01 -0500

Related articles |
---|

Bison version of the LALR(1) algorithm haberg@matematik.su.se (2001-11-29) |

Re: Bison version of the LALR(1) algorithm pjj@cs.man.ac.uk (Pete Jinks) (2001-12-07) |

Re: Bison version of the LALR(1) algorithm johnl@iecc.com (2001-12-07) |

Re: Bison version of the LALR(1) algorithm haberg@matematik.su.se (2001-12-15) |

Re: Bison version of the LALR(1) algorithm thp@cs.ucr.edu (2001-12-20) |

From: | haberg@matematik.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 15 Dec 2001 00:37:01 -0500 |

Organization: | Mathematics |

Keywords: | LALR |

Posted-Date: | 15 Dec 2001 00:37:01 EST |

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/>

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.