21 Feb 2003 01:23:57 -0500

Related articles |
---|

Bermudez-Logothetis LALR(1) Lookahead Algorithm rda@lemma-one.com (Rob Arthan) (2003-02-21) |

Re: Bermudez-Logothetis LALR(1) Lookahead Algorithm rda@lemma-one.com (Rob Arthan) (2003-02-24) |

Re:Bermudez-Logothetis LALR(1) Lookahead Algorithm robert.thorpe@antenova.com (Rob Thorpe) (2003-03-09) |

From: | Rob Arthan <rda@lemma-one.com> |

Newsgroups: | comp.compilers |

Date: | 21 Feb 2003 01:23:57 -0500 |

Organization: | Lemma 1 Ltd. |

Keywords: | parse, LALR, question |

Posted-Date: | 21 Feb 2003 01:23:56 EST |

I am working on an implementation of the Bermudez-Logothetis method for

calculating LALR(1) lookahead sets (from their paper Simple Computation of

LALR(1) Lookahead Set, in Information Processing Letters 31(1989), pp.

233-238). I'm actually upgrading an SLR(1) implementation, so their

treatment is very convenient for me because I have most of the harder

algorithms coded and tested already.

Their method is to construct an auxiliary grammar. They don't give it a

name, so I'm calling it the state transition grammar. The symbols of the

state transition grammar are the transitions of the LR(0) automation. I.e.,

they are pairs written [p:X] where p is a state of the LR(0) automaton and

X is a symbol of the original grammar which labels an edge out of p.

If I'm reading the paper aright, Bermudez & Logothetis define the

productions of the state transition grammar to be all productions of the

form:

[p_1:A] -> [p_1:X_1][p_2:X_2]...[p_n:X_n]

where A -> X_1X_2...X_n is a production of the original grammar. Their

formal definition doesn't make any reference to the state transition

function of the LR(0) automaton.

Am I right in thinking that this is overkill or am I missing something?

Surely you only need toi consider the productions of the above form, where

for each i, 1 <= i < n, there is a transition from p_i to p_{i+1} along an

edge labelled with X_i. The diagrams in the paper strongly suggest this,

but the formal definition of the productions in the state transition

grammar doesn't.

Any help gratefully received.

Rob Arthan (rda@lemma-one.com)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.