Re: Bermudez-Logothetis LALR(1) Lookahead Algorithm

Rob Arthan wrote:


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


Thanks to those who replied by e-mail urging me to tread cautiously -
I was, I assure you. I now have a working LALR(1) parser generator
implemented in and generating Standard ML (snd have tested the results
against an earlier SLR(1) parser generator and against bison). This
should appear in the next open source release of the ProofPower
system.


I have had a separate e-mail correspondence with Prof. Bermudez who
has kindly confirmed the following as the right reading of the
relevant parts of the paper (and so confirmed my thoughts above and
pointed out a mistake that I nearly made):


In the production:


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


the sequence of p_i and X_i is required to form a path in the graph of
the LR(0) automaton. However, the state, p_{n+1}, say, at the end of this
path will not normally be the state at the end of the edge [p_1:A].


So for example, in figure 5 of the paper, there is a production


        [1:S] -> [1:a][6:A][7:c]


but there is no production:


        [1:S] -> [1:a][6:A][13:c]


because, while [13:c] is one of the symbols in the state transition
grammar, there is no path from state 6 to state 13 via non-terminal A.


Moreover, the state at the end of the path [1:a][6:A][7:c] is 8, which is
not the same as the state at the end of the edge [1:S], which is 2. What
happens is that on state 8, reading end-of-input, the parser will reduce to
S and pop its stack until it gets back to state 1 and then it will move via
state 2 to the accepting state.


This all turns out to be wonderfully easy to implement - it only adds about
300 non-comment lines of Standard ML code to my earlier SLR(1)-based
parser generator (and about 80 of those are for diagnostics and listings).
I have been put off implementing LALR(1) for over 10 years because of the
uninspiring description of the over-complex (and slow) yacc algorithm in
Aho & Ullman - drat that dragon!


Rob Arthan (rda@lemma-one.com)

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