Recursive Descent Parsers and YACC

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
--

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