8 ms·
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 derivati
by neel_k 8y ago
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:
http://semantic-domain.blogspot.com/2013/11/antimirov-derivatives-for-regular.html http://semantic-domain.blogspot.com/2013/11/antimirov-deriva...
- deleted 8y ago[deleted]
- abecedarius 8y agoCuriously, in Ken Thompson's 1968 paper on his regex matcher https://www.fing.edu.uy/inco/cursos/intropln/material/p419-thompson.pdf 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. Here's something like your code in Python: https://github.com/darius/regexercise_solutions/blob/master/star.py https://github.com/darius/regexercise_solutions/blob/master/... and transformed into Thompson's algorithm: https://github.com/darius/regexercise_solutions/blob/master/star_thompsonlike.py https://github.com/darius/regexercise_solutions/blob/master/... (I've never read Antimirov's paper past the first page or two; I wrote these things while digging into Thompson.)
- chubot 8y agoWoah I think you just answered the exact question I asked 1 minute ago ? :) https://news.ycombinator.com/item?id=18434228 https://news.ycombinator.com/item?id=18434228 I don't know what an Antimirov derivative is, will check it out ... Thanks for the links to code!
- abecedarius 8y agoYep! As mentioned in the comments, the logic you get this way isn't exactly the same as Thompson's, but it's very close. You're welcome. FWIW I drafted a lot of variations while messing with this: https://github.com/darius/sketchbook/tree/master/regex https://github.com/darius/sketchbook/tree/master/regex (some of this code is incorrect) and https://github.com/darius/sketchbook/tree/master/lex https://github.com/darius/sketchbook/tree/master/lex.