4 May 2000 17:11:52 -0400

Related articles |
---|

DeRemer Pennello LALR(1) Construction Algo johnston.p@worldnet.att.net (Paul Johnston) (2000-05-04) |

Re: DeRemer Pennello LALR(1) Construction Algo francois@fdesar.net (=?iso-8859-1?Q?Fran=E7ois=20D=E9sarm=E9nien?=) (2000-05-08) |

From: | "Paul Johnston" <johnston.p@worldnet.att.net> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 4 May 2000 17:11:52 -0400 |

Organization: | AT&T Worldnet |

Distribution: | inet |

Keywords: | parse, question |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.