Re: Space-efficient LR parser table representations

tom@travis.csd.harris.com (Tom Horsley)
3 Dec 91 13:46:30 GMT

          From comp.compilers
Related articles
Space-efficient LR parser table representations dimitren+@A.NL.CS.CMU.EDU (1991-12-02)
Re: Space-efficient LR parser table representations tom@travis.csd.harris.com (1991-12-03)
Re: Space-efficient LR parser table representations arnold@terminus.gatech.edu (1991-12-10)
| List of all articles for this month |
Newsgroups: comp.compilers
From: tom@travis.csd.harris.com (Tom Horsley)
Keywords: parse, optimize, LALR
Organization: Harris Computer Systems Division
References: 91-12-008
Date: 3 Dec 91 13:46:30 GMT

There was a TOPLAS article a few years ago which described a series of
algorithms for extensively compressing parse tables:


      "Optimization of Parser Tables for Portable Compilers"
      by Peter Dencker, Karl Durre, and Johannes Heuft
      ACM Transactions on Programming Languages and Systems
      Volume 6 Number 4, October 1984


I implemented the algorithm and got some very impressive table compressions
(very much in agreement with the statistics reported in the above paper,
although I do not remember the precise numbers). The generated parsers
do take somewhat longer to run due to the multiple table lookups it does
to decode the tables.
--
domain: tahorsley@csd.harris.com USMail: Tom Horsley
    uucp: ...!uunet!hcx1!tahorsley 511 Kingbird Circle
                                                                                              Delray Beach, FL 33444
--

Post a followup to this message

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