LALR(k) lookahead set algorithms

tbr@tfic.bc.ca (Tom Rushworth )
Fri, 16 Apr 1993 03:40:00 GMT

          From comp.compilers

Related articles
LALR(k) lookahead set algorithms tbr@tfic.bc.ca (1993-04-16)
| List of all articles for this month |

Newsgroups: comp.compilers
From: tbr@tfic.bc.ca (Tom Rushworth )
Keywords: LALR, bibliography
Organization: Compilers Central
Date: Fri, 16 Apr 1993 03:40:00 GMT

There was a series of papers several years back in TOPLAS and SIGPLAN Notices
about improved algorithms for LALR(1) lookahead set generation:


  1982 October - TOPLAS vol 4 # 4,
          "Efficient Computation of LALR(1) Look-Ahead Sets",
          DeRemer and Pennello


  1985 January - TOPLAS vol 7 # 1,
          "A New Analysis of LALR Formalisms",
          Park, Choe and Chang


  1986 July - SIGPLAN Notices vol 21 # 7, (Proceedings of the SIGPLAN'86
          Symposium on Compiler Construction)
          "Unifying View of recent LALR(1) Lookahead Set Algorithms"
          Ives


  1987 April - SIGPLAN Notices vol 22 # 4,
          "Remarks on Recent Algorithms for LALR Lookahead Sets"
          Park and Choe


  1987 August - SIGPLAN Notices vol 22 # 8,
          "Response to Remarks on Recent Algorithms for LALR Lookahead Sets"
          Ives


I implemented the original DeRemer and Pennello algorithm, but I'm rusty
enough on the subject that I found the later papers heavy going. Does
anyone know if Fred Ives published a more detailed paper later? The
August'87 paper mentions a paper submitted to TOPLAS, but if it was
accepted, I've missed it.


The point of all this is that I'm thinking of implementing either the
Park, Choe and Chang algorithm or the Ives algorithm, and I want as clear
an explanation as I can get. Any pointers or suggestions will be
appreciated!
----
Tom Rushworth (604) 733-0731 [FAX: 733-0634] e-mail: tbr@tfic.bc.ca {VE7TBR}
                              Timberline Forest Inventory Consultants
--


Post a followup to this message

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