Recursive Descent Parsers and YACC

Josef Grosch <grosch@gmdka.uucp>
Thu, 22 Nov 90 13:47:29 -0100

          From comp.compilers

Related articles
[2 earlier articles]
Re: Recursive Descent Parsers and YACC grimlok@hubcap.clemson.edu (1990-11-16)
Re: Recursive Descent Parsers and YACC Bruce.Hoult@actrix.co.nz (1990-11-18)
Re: Recursive Descent Parsers and YACC dave@labtam.labtam.oz.au (1990-11-20)
Re: Recursive Descent Parsers and YACC hankd@ecn.purdue.edu (1990-11-17)
Re: Recursive Descent Parsers and YACC henry@zoo.toronto.edu (1990-11-17)
Re: Recursive Descent Parsers and YACC mailrus!sharkey!hela!iti.org!dhw@uunet.UU.NETid AA (1990-11-20)
Recursive Descent Parsers and YACC grosch@gmdka.uucp (Josef Grosch) (1990-11-22)
Re: Recursive Descent Parsers and YACC grimlok@hubcap.clemson.edu (1990-11-23)
Recursive Descent Parsers and YACC jsp@milton.u.washington.edu (Jeff Prothero) (1990-11-23)
Re: Recursive Descent Parsers and YACC melling@psuvax1.cs.psu.edu (1990-11-26)
Re: Recursive Descent Parsers and YACC moss@cs.umass.edu (1990-11-26)
Re: Recursive Descent Parsers and YACC aycock@cpsc.ucalgary.ca (1990-11-26)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Josef Grosch <grosch@gmdka.uucp>
Keywords: parse, yacc, design, question
Organisation: GMD Forschungsstelle, Karlsruhe, Germany
Organization: Compilers Central
Date: Thu, 22 Nov 90 13:47:29 -0100

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


Post a followup to this message

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