Bermudez-Logothetis LALR(1) Lookahead Algorithm

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)

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