Bermudez-Logothetis LALR(1) Lookahead Algorithm

Rob Arthan <rda@lemma-one.com>21 Feb 2003 01:23:57 -0500

From comp.compilers

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)
| List of all articles for this month |

 From: Rob Arthan 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