What is the performance of SPARK-based parsers?

SPARK-based parsers are more slow 开发者_C百科than PLY-based ones, AFAIK. But how much slower? Are they suitable for industrial-strength compilers? If you have something else to say about pros and cons of SPARK, I'll be glad to hear.

---

The speed of these parsers is mostly a property of the grammar they support. SPARK supports Earley grammars and PLY supports LALR(1) grammars. There is a great deal of information available about the pros and cons of each style of grammar, so I will just provide a quick overview here.

The biggest difference between Earley and LALR parsers is how they deal with overlap and ambiguities within the grammar.

LALR(k) parsing is deterministic. It can only handle overlap in the grammar that can be resolved within k tokens of lookahead. The upside is that grammars compatible with LALR parsers have a worst case run time of O(n).

Earley parsing is very similar to the more common GLR parsing. They can handle both unlimited lookahead as well as ambiguities, but they do so by splitting the parse tree into multiple paths at every point of overlap or ambiguity. This can cause a great deal more work for the parser, and as a result Earley/GLR parsing has a worst-case run time of O(n^3).

Which you use depends on what you want to do. LALR parsers are perferable for their speed, but Earley parsers allow for far more flexible grammars than LALR parsers do. Due to ambiguities in the language, C++ cannot be parsed by a LALR parser. It requires an Earley/GLR parser, and is an example of why you would want to use an Earley/GLR parser over an LALR parser.