Re: Recursive Descent Parsers and YACC

melling@psuvax1.cs.psu.edu (Michael D Mellinger) writes:
>[How much faster is parsing with Recursive Descent instead of YACC?]


See also:


%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 * Concise and good introduction to partial evaluation
  * 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).


%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.
  * 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.


On a machine with fast procedure call and so forth, I GUESS that these
schemes win on the basis of better register allocation. I don't know
of any fundamental big-oh differences between YACC-style and recursive
descent.


;-D oN ( YACCity-YACC -- Don't Parse Back ) Pardo
--
pardo@cs.washington.edu
        {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
--

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