Bison version of the LALR(1) algorithm

haberg@matematik.su.se (Hans Aberg)
29 Nov 2001 23:05:49 -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: haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 29 Nov 2001 23:05:49 -0500
Organization: Mathematics
Keywords: parse, yacc, question
Posted-Date: 29 Nov 2001 23:05:49 EST

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.


This seems to differ from the description in say Aho et al
"Compilers", which creates the deterministic machine directly. (The
book has hints to the effect that this corresponds to the NFA -> DFA
translation, but does not describe this explicitly in detail.)


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.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.