DeRemer Pennello LALR(1) Construction Algo

This is a rather directed question: I am currently implementing an LALR(1)
constructor which uses DeRemer and Pennello's Lookahead set algorithm
described in ACM TOPLAS Vol.4 No.4 Oct1982 615-649 and explained using an
example in 'The Theory and Practice of Compiler Writing" by Tremblay and
Sorenson.


This algorithm defines several binary relations to assist in the LA set
generation, one of which 'LOOKBACK' relates which FOLLOW sets contribute to
a LA set.


The problem I'm having is in regards to the example grammar in Tremblay ---
my implementation is emitting one extra LOOKAHEAD relation which I can't for
the life of me reason why it is incorrect. It is:


    (12, T -> T * f) LOOKBACK (8, T)


Which implies that the following statement is true: "when the top of the
stack reads state 12 and spells out T * f, reduction by T -> T * f will pop
three symbols off the stack and reveal state 8 (which has a nonterminal
transition on T)".


Given the example grammar, I don't see why this statement is false. I've
analysed the possible configurations of the stack and that one seems
perfectly valid to me, yet it is conspicously absent from Tremblay.
Additionally, it does not affect the final answer (the lookahead sets).


This is how I am identifying LOOKBACK relations:


foreach state p in the LR(0) machine
do
      foreach item in p of the form [ A -> dot alpha ] /* an item with the dot
at the front */
      do
            trace through the LR(0) machine along the path given by alpha
                until you hit the item with the dot at the end [ A -> alpha dot ] to
get state q.
            add a relation (q, A -> alpha) LOOKBACK (p, A)
      done
done


I expect that people who have implemented this algorithm or people who have
studied the example in detail may be able to offer insight why my approach
is flawed.


Thanks for your help,
Paul

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