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