Monday, December 13, 2010 [Tweets] [Favorites]

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

Stay up-to-date by subscribing to the Comments RSS Feed for this post.

Leave a Comment