Eleven years on, this remains one of my favorite papers!
There's a pretty variant of this idea introduced in 1995 by Valentin Antimirov called partial derivatives of regular expressions. His idea was to replace the single derivative with a set of partial derivatives that add up to the whole derivative. This simplifies the derivative algorithm quite a bit, and makes it possible to write amazingly concise and efficient regular expression matchers.
E.g., here's an implementation of a regular expression compiler that uses Antimirov derivatives to take a regexp and build a table-driven matcher in about 50 lines of code:
Curiously, in Ken Thompson's 1968 paper on his regex matcher https://www.fing.edu.uy/inco/cursos/intropln/material/p419-t... he says it works by taking Brzozowski derivatives. This was a headscratcher to me since his code seems completely different from the derivative-based regex matchers I'd seen. The answer is, it takes Antimirov derivatives, which didn't have a name yet.
There's a pretty variant of this idea introduced in 1995 by Valentin Antimirov called partial derivatives of regular expressions. His idea was to replace the single derivative with a set of partial derivatives that add up to the whole derivative. This simplifies the derivative algorithm quite a bit, and makes it possible to write amazingly concise and efficient regular expression matchers.
E.g., here's an implementation of a regular expression compiler that uses Antimirov derivatives to take a regexp and build a table-driven matcher in about 50 lines of code:
http://semantic-domain.blogspot.com/2013/11/antimirov-deriva...