Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!iecc!compilers-sender From: jsp@milton.u.washington.edu (Jeff Prothero) Newsgroups: comp.compilers Subject: Recursive Descent Parsers and YACC Keywords: parse, yacc, performance Message-ID: <9011232019.AA14958@milton.u.washington.edu> Date: 23 Nov 90 20:19:14 GMT Sender: compilers-sender@iecc.cambridge.ma.us Reply-To: Jeff Prothero Organization: Compilers Central Lines: 32 Approved: compilers@iecc.cambridge.ma.us 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 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.