Re: Efficient generation of LALR(1) look-aheads in Parser Generators

andrewd@cs.adelaide.edu.au (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
> algorithm?


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)
      p. 99-104


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
algorithm:


      S. Sippo, E. Soisalon-Soininen, "Parsing Theory"
      Volume 2, Springer Verlag's EATCS Monograps on Theoretical
      computer Science.


Karsten Nyblad
TFL, A Danish Telecommunication Research Laboratory
E-mail: karsten@tfl.dk
--

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