Re: fast table generators (David Keppel)
Mon, 21 Sep 1992 19:54:12 GMT

          From comp.compilers

Related articles
fast table generators (1992-09-19)
Re: fast table generators (1992-09-20)
Re: fast table generators (1992-09-21)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (David Keppel)
Organization: Computer Science & Engineering, U. of Washington, Seattle
Date: Mon, 21 Sep 1992 19:54:12 GMT
References: 92-09-119
Keywords: parse, LR(1), performance, bibliography (Richard L. Goerwitz) writes:
>[I've written LR(1)-family table generators, they always run slow.
> Any practical implementation books?]

If you're looking for big-O speedeups, I don't know, but if you're looking
for clever implementations, consider merged coded and data in the tables.
(The first paper is relevant because the code generator is a parser).

3 Citations Follow:
%A Chris W. Fraser
%A Robert R. Henry
%T Hard-Coding Bottom-Up Code Generation Tables to Save Time and Space
%J Software \- Practice and Experience
%V 21
%N 1
%D January 1991
%P 1-12

%A Frank G. Pagan
%T Comparative Efficiency of General and Residual Parsers
%J SIGPLAN Notices
%V 25
%N 4
%D April 1990
%P 59-68
%X * Focus on partial evaluation of parsers generating pure code.
  * Hand traslation of Pascal and C.
  * Time (2-10X faster) and size (0.5-1.25 larger).
  * View as explicit partial evaluation of parser wrt to grammar
(doesn't state that it is also partial evaluation of interpreter wrt a

%A Thomas J. Pennello
%T Very Fast LR Parsing
%J Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction;
%V 21
%N 7
%D July 1986
%P 145-151
%X * Partial evaluation of the table interpreter with resepct to each
element of the table (not presented as such).
  * Speedup: on a VAX-like machine, 40,000 to 500,000 lines per minute.
On an 80286, 37,000 to 240,000 lines per minute.
  * FSM converted to assembly language.
  * 2-4X increase in table size.

Hope these help.

        ;-D oN ( "You got code in my data." "You got data in my code!" ) Pardo

Post a followup to this message

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