4 ms·

Derivative parsing http://mjtsai.com/blog/2010/12/13/derivative-parsing/ http://mjtsai.com/blog/2010/12/13/derivative-parsing/ looks interesting. It has severa

• _tef 16y ago
  It has several bad properties too. The algorithm they outline is exponential. The challenge to make it run in cubic time will certainly turn it into a GLR or an Earley parser. (They can be formed from each other) To me: it is just another way of looking at Dotted LR-Items used within earley parser. Earley parsers keep a state made up of grammar rules with a dot indicating where in the rule the parser is at. (I wrote an earley recognizer that uses a derivative style interface to grammar rules.) It has novelty, and some utility but it is not the holy grail you are looking for.
  • anamax 16y ago
    > The algorithm they outline is exponential. They claim that it's actually roughly linear (given some fairly obvious optimizations) and provide a table of measurements that support said claim. http://arxiv.org/PS_cache/arxiv/pdf/1010/1010.5023v1.pdf http://arxiv.org/PS_cache/arxiv/pdf/1010/1010.5023v1.pdf Number of tokens Parsing time 4,944 10 ms 42,346 43 ms 390,553 326 ms 5,049,213 3.9 s 22,155,402 17.1 s