David Nolen on Parsing With Derivatives

Meetup: http://bit.ly/2czxK6R
Paper: http://bit.ly/2cRG1j0
Slides: http://bit.ly/2cqiMLx
Video: https://youtu.be/FKiEsJiTMtI

-----------------------------------------------------------------------------------------------------------
Sponsored by Two Sigma (@twosigma) & hosted at Twitter NYC
-----------------------------------------------------------------------------------------------
Description
------------------
We present a functional approach to parsing unrestricted context-free grammars based on Brzozowski's derivative of regular expressions. If we consider context-free grammars as recursive regular expressions, Brzozowski's equational theory extends without modification to context-free grammars (and it generalizes to parser combinators). The supporting actors in this story are three concepts familiar to functional programmers - laziness, memoization and fixed points; these allow Brzozowski's original equations to be transliterated into purely functional code in...