Derivative Parsing
Matthew Might and David Darais (via Lambda):
This work introduces parsers based on the derivative of context-free languages and upon the derivative of parser combinators. Parsers based on derivatives meet all of the aforementioned requirements: they accept arbitrary grammars, they produce parse forests efficiently (and lazily), and they are easy to implement (less than 250 lines of Scala code for the complete library). Derivative-based parsers also avoid the precompilation overhead of traditional parser generators; this cost is amortized (and memoised) across the parse itself. In addition, derivative-based parsers can be modified mid-parse, which makes it conceivable that a language could to modify its own syntax at compile- or run-time.
An interesting approach. The paper is actually called “Yacc Is Dead,” which I think is true in the sense that for a variety of pragmatic reasons most programmers today do not write their parsers using Yacc-style generators.
Update: Might has as follow-up blog post.
