Derivative parsing http://mjtsai.com/blog/2010/12/13/derivative-parsing/ looks interesting.
It has several nice properties, including being composable and incremental. And it supports modifying the grammar on the fly.
It has several nice properties, including being composable and incremental. And it supports modifying the grammar on the fly.
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.
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
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