14

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?

2
  • 1
    @BartKiers: isn't the parser generated by the parser-generator no more complex or generic than the generator itself, though? To put it another way, if the parser-generator can generate code complex enough to parse something, why can't it just generate the code, compile, and execute the code in memory to parse it immediately? Isn't that equivalent to just parsing it directly? (it probably isn't, because parser-generators do exist, i just don't know why)
    – Li Haoyi
    Jan 8, 2012 at 19:18
  • 1
    With some effort, it is possible to obtain the tables generated by lex and yacc (flex and bison) and use them in a non-standard skeleton. The biggest problem is hooking up the user supply actions. Jan 8, 2012 at 19:27

1 Answer 1

16

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.

4
  • 2
    Thanks, this is very informative! Would it be correct to say that code-generating parsers are an optimization that you can do because the grammar you are parsing typically does not change at run-time, and can therefore be hard-coded into the program? Does this sort of thing still apply for languages like LISP, where you would be able to compose the AST of a parser dynamically at run time? (p.s. I have had no education on lexers/parses or formal language theory, I'm just trying to grok the general principles behind the way things are, and code-generation is not a step you see that often)
    – Li Haoyi
    Jan 9, 2012 at 15:12
  • @LiHaoyi: Most optimizations have an assumption about constancy-of-circumstances behind them. The whole point of partial evaluation is that while PE may be expensive to run once, F'(y) is typically a lot cheaper than F(x,y), and as long as x [the grammar] stays constant you can safely use F'(y). This is even true for lisp: it has a "constant" syntax called S-expressions.
    – Ira Baxter
    Jan 10, 2012 at 1:15
  • 2
    Somewhat as an epilogue, I've recently learned how to use the Parser Combinator library provided by Scala. My understanding is that there exist similar libraries in other languages (e.g. PyParsing, (F)Parsec) that let you do a similar thing, all without code generation. How do these fit into your answer? Do they do the preprocessing step as an initialization thing at run-time, or do they suffer a performance penalty not having preprocessing at all?
    – Li Haoyi
    Feb 2, 2012 at 11:20
  • I don't know much about such libraries. Yes, you can do parsing using dynamic descriptions of your language; check out Earley parsers. The point is that if you do so, your parser won't be as efficent as one that has been "precompiled". This may not matter for many applications that only read small documents on an occasional basis. But if the application reads huge documents often (any source code processing tool such as compilers), or it is used by very many people, then a dynamic parsing technique is inefficient and you shouldn't do it, even if it convenient at the time you code it.
    – Ira Baxter
    Feb 2, 2012 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.