Why parser-generators instead of just configurable-parsers?

Question

The title sums it up. Presumably anything that can be done with source-code-generating parser-generators (which essentially hard-code the grammar-to-be-parsed into the program) can be done with a configurable parser (which would maintain the grammar-to-be-parsed soft-coded as a data structure).

I suppose the hard-coded code-generated-parser will have a performance bonus with one less level of indirection, but the messiness of having to compile and run it (or to exec() it in dynamic languages) and the overall clunkiness of code-generation seems quite a big downside. Are there any other benefits of code-generating your parsers that I'm not aware of?

Most of the places I see code generation used is to work around limitations in the meta-programming ability of the languages (i.e. web frameworks, AOP, interfacing with databases), but the whole lex-parse thing seems pretty straightforward and static, not needing any of the extra metaprogramming dynamism that you get from code-generation. What gives? Is the performance benefit that great?

Answer 1

If all you want is a parser that you can configure by handing it grammar rules, that can be accomplished. An Earley parser will parse any context-free language given just a set of rules. The price is significant execution time: O(N^3), where N is the length of the input. If N is large (as it is for many parseable entities), you can end with Very Slow parsing.

And this is the reason for a parser generator (PG). If you parse a lot of documents, Slow Parsing is bad news. Compilers are one program where people parse a lot of documents, and no programmer (or his manager) wants the programmer waiting for the compiler. There's lots of other things to parse: SQL querys, JSON documents, ... all of which have this "Nobody is willing to wait" property.

What PGs do is to take many decisions that would have to occur at runtime (e.g., for an Earley parser), and precompute those results at parser-generation time. So an LALR(1) PG (e.g., Bison) will produce parsers that run in O(N) time, and that's obviously a lot faster in practical circumstances. (ANTLR does something similar for LL(k) parsers). If you want full context free parsing that is usually linear, you can use a variant of LR parsing called GLR parsing; this buys you the convienience of an "configurable" (Earley) parser, with much better typical performance.

This idea of precomputing in advance is generally known as partial evaluation, that is, given a function F(x,y), and knowledge that x is always a certain constant x_0, compute a new function F'(y)=F(x0,y) in which decisions and computations solely dependent on the value of x are precomputed. F' usually runs a lot faster than F. In our case, F is something like generic parsing (e.g., an Earley parser), x is a grammar argument with x0 being a specific grammar, and F' is some parser infrastructure P and additional code/tables computed by the PG such that F'=PG(x)+P.

In the comments to your question, there seems to be some interest in why one doesn't just run the parser generator in effect at runtime. The simple answer is, it pays a significant part of the overhead cost you want to get rid of at runtime.