Monday, December 13, 2010

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.

Comments RSS · Twitter

Leave a Comment