Skip to main content

Efficient computation of LALR(1) look-ahead sets

Frank DeRemer, Thomas J. Pennello

DOI 10.1145/800229.806968 dblp BibTeX

Abstract

We define two relations that capture the essential structure of the problem of computing LALR(1) look-ahead sets, and present an efficient algorithm to compute the sets in time linear in the size of the relations. In particular, for a PASCAL grammar, our algorithm performs less than 20% of the set unions performed by a popular-compiler (YACC).

Related papers

Efficient Computation of LALR(1) Look-Ahead Sets TOPLAS 1982
On the (non-) Relationship between SLR(1) and NQLALR(1) Grammars TOPLAS 1988
Unifying view of recent LALR(1) lookahead set algorithms PLDI 1986
Clairvoyance: look-ahead compile-time scheduling CGO 2017
Dynamic Look Ahead Compilation: A Technique to Hide JIT Compilation Latencies in Multicore Environment CC 2009
A practical arbitrary look-ahead LR parsing technique PLDI 1986
Look-ahead SLP: auto-vectorization in the presence of commutative operations CGO 2018
A New Analysis of LALR Formalisms TOPLAS 1985