Re: Bison version of the LALR(1) algorithm

thp@cs.ucr.edu
20 Dec 2001 02:03:48 -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: thp@cs.ucr.edu
Newsgroups: comp.compilers
Date: 20 Dec 2001 02:03:48 -0500
Organization: University of California, Riverside
References: 01-12-063
Keywords: parse, LALR
Posted-Date: 20 Dec 2001 02:03:48 EST

Hans Aberg <haberg@matematik.su.se> wrote:
[...]
: The book at http://www.cs.vu.nl/~dick/PTAPG.html explains how to produce
: non-deterministic parsers from grammars.


Given a context-free grammar, it's easy to produce an equivalent
nondeterministic push-down automaton, and vice versa. Unfortunately,
there are nondeterministic pushdown automata (and their equivalent
context-free grammars) for which there are no equivalent deterministic
push-down automata. The goal of LR-parsing is to come up with
algorithms -- generalizations of the set-of-states algorithm for
determinizing nondeterministic finite-state automata -- that can
determinize as many nondeterministic push-down automata as possible
without the resulting deterministic PDAs being overly large. (As of
the mid '70s, the LALR algorithm was considered to be the right
tradeoff between generality and size of the resulting DPDAs.)


Tom Payne

Post a followup to this message

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