Recursive Descent vs. Generated Parsers - Efficiency

Question

How do hand-written recursive descent parsers (which are inevitably LL(k)) compare to generated LALR parsers in terms of performance?

I know that LALR parsers are able to handle far more grammars than LL(k); however it's my intention to write my parser by hand, and recursive descent seems the most appropriate choice. Is it possible to write any other kind by hand (reasonably readably) out of interest?

N.B. I am using a functional language with tail-call optimisation (F#), so [well-tailored] recursion won't be as much of an issue as in other languages.

Answer 1

I think a lot depends on the language you are trying to parse. Another part of performance which sometimes gets forgotten is the lexical analysis (scanning) part - it is significant for performance as it deals with characters rather than symbols. Recursive descent is a good first iteration at writing a parser, and it makes following the parsed language's logic quite natural. I think that if the parsed language fits (no left recursion) you should start with recursive descent. Choosing LALR for performance at this stage seems to be premature optimization. You can write a chart parser by hand, but I doubt this is what you mean. Writing an LALR parser by hand is possible but tedious.

Answer 2

Deciding between LALR and LL for performance reasons at this point sounds like a premature optimization. Parsing time is rarely the bottleneck in a compiler. If I were you, I'd choose based on whether you are more comfortable defining your grammar bottom-up or top-down.

Personally, I find LALR grammars easy to work with, and F#'s fsyacc integration (which is how I learned parsing) makes it very easy to integrate yacc into your project.