5 ms·
Summary of parsing with derivatives (Brzozowski 1964) for the unfamiliar (like me): For example, with respect to the character f, the derivative of the lan
by heydenberk 10y ago
Summary of parsing with derivatives (Brzozowski 1964) for the unfamiliar (like me):
For example, with respect to the character f, the derivative
of the language for which [[L]] = {foo, frak, bar} is
Df (L) = {oo, rak}. Because foo and frak start with the
character f and bar does not, we keep only foo and frak
and then remove their initial characters, leaving oo and rak.
We repeat this process with each character in the input
until it is exhausted. If, after every derivative has been performed,
the resulting set of words contains the empty word,
then there is some word in the original language consisting
of exactly the input characters, and the language accepts
the input. All f this processing takes place at parse time, so
there is no parser-generation phase.
The specific algorithm they build off (Might 2011) has extended this to memoize repeated derivations of the same arguments and to allow for lazy evaluation in the case of recursion.
But this algorithm was implemented in a mind-bendingly-slow way:
For example, they report
that a 31-line Python file took three minutes to parse!
They prove that the worst case is actually cubic time and provide a concise cubic-time implementation in Racket: https://bitbucket.org/ucombinator/derp-3 https://bitbucket.org/ucombinator/derp-3
Their implementation is orders of magnitude faster of prior PWD implementations, but still orders of magnitude slower than a Bison parser of the same grammar, which they attribute to language choice (C vs Racket).
Please correct me if I'm wrong about any of this! Summarizing research like this helps me understand it, but that doesn't mean I actually understand it.
- justinpombrio 10y agoYeah, that's accurate! I'm glad we finally know the running time for parsing with derivatives. Let me add some more background, about stuff that I would expect to be covered in this paper's related work section, except that it doesn't have one... Most well-known parsing algorithms that handle arbitrary CFGs run in cubic time, so this paper's O(n^3) running time is about the best you would expect. Some other parsing algorithms that also handle arbitrary CFGs in cubic time include CYK[1], Early[2], and GLR[3]. I used to be excited about parsing with derivatives because of its simplicity, but CYK and Early parsers are both actually simpler than parsing with derivatives, once you've thrown this paper's optimizations in. [1] https://en.wikipedia.org/wiki/CYK_algorithm https://en.wikipedia.org/wiki/CYK_algorithm [2] https://en.wikipedia.org/wiki/Earley_parser https://en.wikipedia.org/wiki/Earley_parser [3] https://en.wikipedia.org/wiki/GLR_parser https://en.wikipedia.org/wiki/GLR_parser [EDIT: Previously, I stated "CFGs, in general, can't be parsed in better than cubic time.", which is incorrect. Thanks, pacala.]
- pacala 10y agoCFG parsing can be done better than O(n^3), reducing to Boolean matrix multiplication, which is about O(n^2.37). http://theory.stanford.edu/~virgi/cs367/papers/valiantcfg.pdf http://theory.stanford.edu/~virgi/cs367/papers/valiantcfg.pd... https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... Agreed that CYK and Earley are rather simple to implement. Though Earley has an edge, as its best case is O(n), whereas CYK is O(n^2) best case.
- justinpombrio 10y ago> CFG parsing can be done better than O(n^3), reducing to Boolean matrix multiplication, which is about O(n^2.37). Is there a known lower bound on running time to parse CFGs, like O(n^2)?
- DannyBee 10y agoIt is known that any fast CFG parsing algorithm can be turned into a fast boolean matrix multiplication algorithm. So if CFG parsing was n^2, so is boolean matrix multiplication :) See http://arxiv.org/abs/cs/0112018 http://arxiv.org/abs/cs/0112018
- yxhuvud 10y agoOne important note is that this holds for general grammars that can contain everything. If the grammar is restricted somehow, for example to lr(k) then the best complexity is linear (there are even parsers that manage both LR(n) in linear time and general parsing in cubic).
- moefh 10y agoI'm confused by this argument. To show that > if CFG parsing was n^2, so is boolean matrix multiplication wouldn't you need to show that any boolean matrix multiplication can be turned into CFG parsing (and not the converse)?
- gumby 10y agoThanks for looking that up. I had not realized that Boyer-Moore is an optimized subset of derivative parsing.
- mattmight 10y agoI'm one of the paper authors. That's a great summary. Thanks! We're hopeful that this new algorithm already makes PwD practical enough for many use cases, and we have significant further improvements in progress. Stay tuned!