Thu, 28 Feb 2008 00:49:39 +0100

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

From: | "mailings@jmksf.com" <mailings@jmksf.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 28 Feb 2008 00:49:39 +0100 |

Organization: | Compilers Central |

Keywords: | LALR, question |

Posted-Date: | 27 Feb 2008 22:00:13 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.