Re: LALR(k) lookahead computation

"Peter S. Housel" <housel@cox.net>
31 Dec 2006 09:25:56 -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 148f3wg02@sneakemail.com (Karsten Nyblad) (2006-12-29)
Re: LALR(k) lookahead computation housel@cox.net (Peter S. Housel) (2006-12-31)
| List of all articles for this month |

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

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


    http://monday.sourceforge.net/lib/language/grammar/grammar-project.html


for a human-readable version of the sources.


-Peter S. Housel- housel@acm.org


Post a followup to this message

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