Compilers - Method for state reduction in LALR(1) parsers?

Author

Method for state reduction in LALR(1) parsers?

mailings@jmksf.com

2008-02-27, 10:22 pm

Hello folks.

I'm searching for a way to minimize the states of a LALR(1) parser. I
found a possibility on my own, but this does not seem to be working
with all grammars. I'm not able to debug the true problem behind my
attemp to minimize the states, but there is a problem.

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 - in my opinion - possible, when the closure on a state's kernel
causes a partition with a single configuration that looks as

x: y .A

where A is a terminal symbol, x a nonterminal symbol and y is a
sequence of terminals, nontermals or even epsilon.

So such a configuration causes an action table entry in the parse
table that says "SHIFT AND REDUCE". So "A" will first be shifted, and
then the production is reduced.

But this is not a stable and bug-free solution - but I am sure that my
attemp is not completely wrong.

There is one parser generator that uses - as I analyzed - this
optimization, this is Anagram from Jerome T. Holland, but I cannot ask
him for his algorithm because he died some years ago.

Does anyone of you know a solution of reducing the states like Anagram
does? The difference between Anagram and my experimental parser
generator is, that Anagram never produces states that are, as derived
from the above configuration, like

x: y A.

so my idea was the one I mentioned above. Anagram produces 5 states
where my parser generator produces 7 states, and my view is that Anagram
even performs such a method of minimizing the states - but how?

Thanks in advance for your help!

Regards,
Jan

Paul B Mann

2008-02-28, 10:25 pm

> 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

Sponsored Links