Method for state reduction in LALR(1) parsers?

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

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