On: Derivatives of Regular Expressions (2007)

[abecedarius]

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.

Here's something like your code in Python: https://github.com/darius/regexercise_solutions/blob/master/... and transformed into Thompson's algorithm: 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 → abecedarius]

Woah I think you just answered the exact question I asked 1 minute ago ? :)

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 → chubot]

Yep! 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 (some of this code is incorrect) and https://github.com/darius/sketchbook/tree/master/lex.