Re: LALR(k) lookahead computation

"Peter S. Housel" <>
31 Dec 2006 09:25:56 -0500

          From comp.compilers

Related articles
LALR(k) lookahead computation (Leonardo Teixeira Passos) (2006-12-28)
Re: LALR(k) lookahead computation (Karsten Nyblad) (2006-12-29)
Re: LALR(k) lookahead computation (Peter S. Housel) (2006-12-31)
| List of all articles for this month |

From: "Peter S. Housel" <>
Newsgroups: comp.compilers
Date: 31 Dec 2006 09:25:56 -0500
Organization: Cox
References: 06-12-107 06-12-112
Keywords: LALR
Posted-Date: 31 Dec 2006 09:25:56 EST

On Fri, 29 Dec 2006 22:59:06 -0500, Karsten Nyblad wrote:
> 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.

The references for the Fred Ives adaptation:
- Ives, Fred. July 1986. Unifying View of Recent LALR(1) Lookahead Set
    Algorithms. ACM SIGPLAN Notices 21, 7, pp. 131-135.
- Ives, Fred. August 1987. Response to Remarks on Recent Algorithms for
    LALR Lookahead Sets. ACM SIGPLAN Notices 22, 8, pp. 99-104.

I have implemented this algorithm as a literate program explaining how it
works in detail. See

for a human-readable version of the sources.

-Peter S. Housel-

Post a followup to this message

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