3 ms·

Curiously, 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/inc

Curiously, 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 ago
Woah 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 ago
  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 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.