What is a good source of runtime/stack space analysis for recursive descent parsers?

Question

I'd like to understand more about the runtime of recursive descent parsers. I'm also interested in the stack space used by recursive descent parsers (and the trade-offs between runtime and stack space). What are some good sources of information?

I've read through the wikipedia article and searched around the web but I haven't found anything that goes into detail.

Answer 1

Runtimes for the recursive descent parsing is pretty fast; generally one uses machine CALL/RET instructions to implement the recursion. Hand written versions that don't backtrack or look ahead should generally be very fast. But what matters isn't the time to parse a token stream; what matters is time spent processing characters to construct tokens, and/or semantic checking/code generation. Why are you worried about this?

The stack space is determined fundamentally by the deepest nesting required to parse the program. If your parser accepts (...) in expressions, and somebody writes an expression with 50,000 nested parens, a recursive descent parse will recurse 50,000 times. You can prevent this behavior (almost everybody does) by making an arbitrary rule about how deeply the recursion for the parser can be. I've found that 100 levels will let you process amazingly complex programs.