Re: LL(1) vs LALR(1) parsers

David Keppel writes:


>%A Thomas J. Pennello
>%T Very Fast LR Parsing
>%J Proceedings of the SIGPLAN 1986 Symposium on Compiler Construction;
>SIGPLAN Notices
>%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 (though not described as such).
> * 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.


> ;-D on ( Parsetial Evaluation ) Pardo


Note that Penello's LR parser did not actually include *actions* or
error recovery... Someone I know actually implemented Penello's scheme
inside of Bison, and this sped up the generated parser on a cut-down C
(used in a local compiler class) grammar from 300% to 600% (on
pre-tokenized input). On the other hand, the generated parsers were
enormous since Penello's scheme encodes most of the parsing tables in
instruction state.
--
*** Patrick G. Bridges bridges@cs.arizona.edu ***
--

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