Re: Bison version of the LALR(1) algorithm

Pete Jinks <pjj@cs.man.ac.uk>
7 Dec 2001 23:40:46 -0500

          From comp.compilers
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)
| List of all articles for this month |
From: Pete Jinks <pjj@cs.man.ac.uk>
Newsgroups: comp.compilers
Date: 7 Dec 2001 23:40:46 -0500
Organization: Computer Science Dept, University of Manchester
References: 01-11-134
Keywords: yacc
Posted-Date: 07 Dec 2001 23:40:46 EST

Hans Aberg wrote:
>
> Can somebody give a reference to a description of the LALR(1)
> algorithm that Bison uses?
>
> The file state.h of the Bison sources says that first, a
> non-deterministic finite state machine that parses the specified
> grammar is created; it is then converted into a deterministic finite
> state machine.


I don't know what Bison uses, but your description sounds like the
algorithm I first came across in:
Syntax Analysis and Software Tools
K.John Gough
Addison-Wesley 1988
chapter 9 Bottom-up parsing
The references there point to
D.E.Knuth (1965)
On the translation of languages from left to right
Information and control v8 pp323-350
which apparently covers both this and the "usual" form of the algorithm.


--
Peter J. Jinks, Room 2.99, Department of Computer Science,
University of Manchester, Oxford Road, Manchester, M13 9PL, U.K.
(+44/0)161-275 6186 http://www.cs.man.ac.uk/~pjj

Post a followup to this message

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