Recursive Descent Parsers and YACC

grosch@gmdka.uucp (Josef Grosch) writes:
>I did a comparison of generated parsers on a SUN 3 with MC 68020 processor
>(excluding scanning):
>
>tool speed (tokens per second)
>
>Yacc 16,000
>Lalr - our LALR(1) parser generator 35,000
>Ell - our LL(1) recursive descent parser generator 55,000
>
>Pure parsing can be made faster by a factor of 2, 3, or more compared to Yacc.


Note that "LALR(1) parser generator" doesn't have to mean "table driven".
Don't have the reference handy, but someone (I believe MetaWare's Tom
Penello?) has obtained big speedups by using procedural implementations of
the LALR(1) tables. Robert Henry has done much the same thing with code
generation tables in CODEGEN (UW technical report), and observed that table
compression and lookup techniques are essentially application-independent,
and that a general tool could be developed to factor, compress, and
implement tables, including generating fast procedural implementations.


Seems to me procedural table implementations bring us full circle: We
started with fast random code, then switched to slower table-driven code as
an aid to portability and code maintainablility. Now that we can generate
the unportable, unmaintainable code automatically from declarative
specifications, the speed consideration is coming to the fore again. No?


Jeff Prothero
jsp@u.washington.edu
--

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