Re: Recursive Descent Parsers and YACC

melling@psuvax1.cs.psu.edu (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? Is there
>enough of a difference to consider using a RDP in a commercial C compiler?


I would tend to believe that table driven parsers (YACC) are faster in
execution than recursive descent parsers. The stack and function call
overhead alone can get to be pretty hairy, especially in deeply recursive
parses.


What is faster, in my experience, is the speed in which you can get a parser
running. Trying to coax a grammer that YACC likes (conflict-free) is
downright a pain, but the recursive descent parser generators I've worked
on/with have much laxer restrictions on the grammar than LR(1). In theory,
one could have a non-deterministic, backtracking RD parser (seen one or two
done in Prolog), but most generators at least require the grammar to be
deterministic (is this the same as LR(1)?


If you want to get a parser up quickly, use an Early's algorithm-based
parser. It will run slow, but it runs the first time, giving you time to
massage the grammar for a faster parser type.


--

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