Karsten Nyblad <148f3wg02@sneakemail.com>29 Dec 2006 22:59:06 -0500

From comp.compilers

Related articles
LALR(k) lookahead computation leonardo@dcc.ufmg.br (Leonardo Teixeira Passos) (2006-12-28)
Re: LALR(k) lookahead computation housel@cox.net (Peter S. Housel) (2006-12-31)
| List of all articles for this month |

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

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.