|Efficient generation of LALR(1) look-aheads in Parser Generators email@example.com (1992-07-27)|
|Re: Efficient generation of LALR(1) look-aheads in Parser Generators firstname.lastname@example.org (1992-08-03)|
|Question on moving from interpreted language to hypercube executable email@example.com (1992-08-04)|
|From:||firstname.lastname@example.org (Karsten Nyblad)|
|Organization:||TFL, A Danish Telecommunication Research Laboratory|
|Date:||Mon, 3 Aug 1992 08:14:04 GMT|
|Keywords:||yacc, bibliography, theory|
email@example.com (Andrew Dunstan) writes:
> Berkeley yacc uses the algorithm from DeRemer and Pennello. So does
> Bison. Original yacc uses an old and horribly inefficient algorithm.
> There was a paper later than DeRemer and Penello by Park etc., which
> apparently had a much more efficient algorithm, although the paper
> itself is even harder to follow than that of DeRemer and Pennello,
> which is saying something!
> Does anybody know of a publicly available implementation of this
The algorithm of Park is further described in:
Kwang Moo Choe: "A New Analysis of LALR Formalisms"
Report CS-TR-84-03 from Korea Advanced Institute of Science
and Technology, Seoul, Republic of Korea.
Take care. There are a number of errors in the report, some of them not
that easy to find.
Also make sure to get the correspondence between Fred Ives and Park and
Choe in Sigplan Notices. They discuss an optimization to Park and Choe's
algorithm publish in Sigplan notices by Ives.
Ives, F. "Unifying view of Recent LALR(1) lookhead set
algorithms", Sigplan Notices 21, 7 (July 1986) p. 131-135
It also describe the algorithms of Park and Choe and DeRemer and Pennello
in further details.
Park, J. C. H., Choe, K. M. "Remarks on Recent algorithm
for LALR lookahead sets", Sigplan Notices, 22, 4 (April
1987) p. 30-32
Ives, F. "Response ot Remarks on Recent Algorithms for LALR
Lookahead Sets", Sigplan Notices, 22, 8, (August 1987)
Ives and Park and Choe exchanged two more letters. Especially the last
one is interesting. In that, Fred Ives claims that the algorithm by
Madsen and Kristensen is faster if combined with Eve algorithm for
calculating transitive closures. Unfortunately, I have lost these two
letters, so you will have to search for them your self. They must have
appeared in Sigplan Notices during the year following August 1987. The
last one is just one page. I have implemented Madsen and Kristensen's
algorithm combined with Eve's and Park and Choe's and can confirm, that it
is extremely fast.
Kristensen, B. B., Madsen, O. L., "Methods for Computing
LALR(K) Lookahead", ACM TOPLAS, vol 3, 1, p. 60-82
Eve, J. K.-S., "On Computing the Transitive Closure of
a Relation", Acta Inf 8, P. 303-314
Also this book contains a lengthy description of DeRemer and Pennello's
S. Sippo, E. Soisalon-Soininen, "Parsing Theory"
Volume 2, Springer Verlag's EATCS Monograps on Theoretical
TFL, A Danish Telecommunication Research Laboratory
Return to the
Search the comp.compilers archives again.