Re: Method for state reduction in LALR(1) parsers?

"Paul B Mann" <paul@paulbmann.com>
Wed, 27 Feb 2008 23:53:21 -0600

          From comp.compilers
Related articles
Method for state reduction in LALR(1) parsers? mailings@jmksf.com (mailings@jmksf.com) (2008-02-28)
Re: Method for state reduction in LALR(1) parsers? paul@paulbmann.com (Paul B Mann) (2008-02-27)
| List of all articles for this month |
From: "Paul B Mann" <paul@paulbmann.com>
Newsgroups: comp.compilers
Date: Wed, 27 Feb 2008 23:53:21 -0600
Organization: Compilers Central
References: 08-02-092
Keywords: LALR, bibliography
Posted-Date: 28 Feb 2008 10:44:12 EST

> I'm searching for a way to minimize the states of a LALR(1) parser.
> My thought of minimizing the states of a LALR(1) parser has been: What
> if the parser performs a shift and a reduce in one single step?


This is well documented in the book, "Compiler Construction" by Goos and
Waite, published about 1985, by Springer Verlag.


This is the technique used in the LR parser generator, LRGen at
http://lrgen.com


The book says that by introducing SHIFT-REDUCE actions, you can
eliminate about 30% of the states. This will work fine for all states
that have only one reduce action. States that have more than one
reduce action, cannot be removed, however.


The GOTO action is usually a positive number in the parser tables and the
SHIFT-REDUCE number is a negative number. It does increase the
speed of the parsers, while reducing the size of the tables.




Paul B Mann

Post a followup to this message

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