Mon, 3 Aug 1992 08:14:04 GMT

Related articles |
---|

Efficient generation of LALR(1) look-aheads in Parser Generators andrewd@cs.adelaide.edu.au (1992-07-27) |

Re: Efficient generation of LALR(1) look-aheads in Parser Generators karsten@tfl.dk (1992-08-03) |

Question on moving from interpreted language to hypercube executable brannon@stun4r.cs.caltech.edu (1992-08-04) |

Newsgroups: | comp.compilers |

From: | karsten@tfl.dk (Karsten Nyblad) |

Organization: | TFL, A Danish Telecommunication Research Laboratory |

Date: | Mon, 3 Aug 1992 08:14:04 GMT |

Keywords: | yacc, bibliography, theory |

References: | 92-07-097 |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.