Re: LALR(k) lookahead computation

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

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