Path: utzoo!utgpu!watserv1!watmath!att!ima!iecc!compilers-sender From: pardo@cs.washington.edu (David Keppel) Newsgroups: comp.compilers Subject: Re: Recursive Descent Parsers and YACC Keywords: parse, yacc, design, question Message-ID: <13758@june.cs.washington.edu> Date: 16 Nov 90 21:03:27 GMT References: Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: pardo@cs.washington.edu (David Keppel) Organization: University of Washington, Computer Science, Seattle Lines: 44 Approved: compilers@iecc.cambridge.ma.us 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.