# Parsing with Derivatives: A Functional Pearl (@ ICFP 2011)

### Matthew Might, David Darais, Daniel Spiewak

I only read the recognition part, but it seems parsing follows without too much work. The derivative of a formal language $L$ with respect to a character $c$ is the language of all $l$ such that $c + l \in L$. The utility of this simple (apparently classical) construct becomes clear once you look at the constructors of regular languages and see that it's very simple to compute, and once you have it recognition is basically solved. Extending it to context-free languages is not trivial: this is the meat of the paper, as I understand. But it can be solved with three simple modifications that seem like "hacks" when you read them, but then you realize that the combination of the three -- laziness, memoization and fixed points -- actually solve the problem.