|fast table generators firstname.lastname@example.org (1992-09-19)|
|Re: fast table generators email@example.com (1992-09-20)|
|Re: fast table generators firstname.lastname@example.org (1992-09-21)|
|From:||email@example.com (David Keppel)|
|Organization:||Computer Science & Engineering, U. of Washington, Seattle|
|Date:||Mon, 21 Sep 1992 19:54:12 GMT|
|Keywords:||parse, LR(1), performance, bibliography|
firstname.lastname@example.org (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
%D January 1991
%A Frank G. Pagan
%T Comparative Efficiency of General and Residual Parsers
%J SIGPLAN Notices
%D April 1990
%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;
%D July 1986
%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
Return to the
Search the comp.compilers archives again.