Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!rutgers!usc!zaphod.mps.ohio-state.edu!ncar!husc6!spdcc!iecc!compilers-sender
From: grosch@gmdka.uucp (Josef Grosch)
Newsgroups: comp.compilers
Subject: Recursive Descent Parsers and YACC
Keywords: parse, yacc, design, question
Message-ID: <9011221247.AA18998@gmdka.uucp>
Date: 22 Nov 90 14:47:29 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: Josef Grosch <grosch@gmdka.uucp>
Organization: Compilers Central
Lines: 26
Approved: compilers@iecc.cambridge.ma.us
Organisation: GMD Forschungsstelle, Karlsruhe, Germany

Michael D Mellinger writes:
[Can someone give me an estimate on how much faster parsing can be made by
writing a recursive-descent parser instead of using Yacc and Lex?]

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.
However, as pure parsing takes only 5 to 10 % of the whole compilation time,
it is not the bottle neck and does not matter too much.
Scanning is much more time critical, as it takes 30 to 50 %.
Therefore Lex can not be used for high speed compilers.
Scanner generators like Rex and flex are up to 5 times faster.

Josef Grosch
---
grosch@gmdka.uucp
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.