News for hackers. Stuff that matters.
Re:Parsing: the solved problem that isn't by anamax on Tuesday March 15, 2011 @10:02AM (#2327452)
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.

Re:Parsing: the solved problem that isn't by _tef on Tuesday March 15, 2011 @10:18AM (#2327521)
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.

Re:Parsing: the solved problem that isn't by anamax on Wednesday March 16, 2011 @03:15AM (#2331159)
> 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

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