We present two novel approaches to parsing context-free lan- guages. The first approach is based on an extension of Brzozowski's derivative from regular expressions to context-free grammars. The sec- ond approach is based on a generalization of the derivative to parser combinators. The payoff of these techniques is a small (less than 250 lines of code), easy-to-implement parsing library capable of parsing ar- bitrary context-free grammars into lazy parse forests. Implementations for both Scala and Haskell are provided. Preliminary experiments with S-Expressions parsed millions of tokens per second, which suggests this technique is efficient enough for use in practice.
['Matthew Might', 'David Darais']
Yacc is dead