29 Dec 2006 22:59:06 -0500

Related articles |
---|

LALR(k) lookahead computation leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-12-28) |

Re: LALR(k) lookahead computation 148f3wg02@sneakemail.com (Karsten Nyblad) (2006-12-29) |

Re: LALR(k) lookahead computation housel@cox.net (Peter S. Housel) (2006-12-31) |

From: | Karsten Nyblad <148f3wg02@sneakemail.com> |

Newsgroups: | comp.compilers |

Date: | 29 Dec 2006 22:59:06 -0500 |

Organization: | Compilers Central |

References: | 06-12-107 |

Keywords: | parse, LALR |

Posted-Date: | 29 Dec 2006 22:59:06 EST |

Leonardo Teixeira Passos wrote:

*> Hi there.*

*>*

*> Is there any generalization over DeRemer's LALR(1) algorithm in*

*> order to calculate LALR(k) lookahead set?*

First, which algorithm are you talking about? Are you talking about the

algorithm DeRemer published together with Penello:

http://portal.acm.org/citation.cfm?id=357187&coll=portal&dl=ACM

If you are talking an algorithm previously published by DeRemer alone,

then you should read the article I link to, because DeRemer has

published an erroneous algorithm, and the article I link to tells you

what is wrong.

I had a student extend the algorithm of DeRemer and Penello 20 years

ago. Unfortunately I can't find her report. There are two problems.

First you need to generalize the algorithm for finding transitive

closures to handle LALR(K) lookahead set, and that is not strait

forward. (DeRemer and Penello call that algorithm Digraph.) I use a

system where I make recursive calls of the algorithm such that the

algorithm is called K times inside each other for calculating LALR(K).

Secondly, DeRemer and Penello do not handle lookahead set for tokens

being stacked, because they are only needed if K>1. You do not need

them if you are sure your grammar is LALR(K), because then you can

select the right operation of the parser from the lookahead set of the

reductions, but DeRemer's and Penello's algorithm can be extended to

handle it, and it is not that difficult.

Also read: Bent Bruun Kristensen, Ole Lehrmann Madsen: Methods for

Computing LALR(k) Lookahead. ACM Trans. Program. Lang. Syst. 3(1): 60-82

(1981)

These two have not discovered the use of the transitive closure

algorithm, but later Fred Ives has demonstrated, that this algorithm is

faster than DeRemer's and Penello's if you enhance BBK's and OLM's

algorithm to use transitive closure algorithm.

Personally I use a combination of the enhanced BBK and OLM algorithm

with results from two Korean scientists.

Karsten Nyblad

148f3wg02 at sneakemail dot com

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.