News for hackers. Stuff that matters.
Re:Matching Regexps 200 Times Faster by conradludgate on Wednesday March 19, 2025 @03:02AM (#43408977)
Backreferences are not part of the original regular expression theories. Regular expressions are supposed to be equivalent to DFAs, but backrefs upgrade their status to full Turing machines.

Algorithms for running regexes as non-deterministic finite automata just happen to be easy to add backrefs too, but it completely breaks the DFA principle.

Interesting video on "How regexes got catastrophic": https://youtu.be/gITmP0IWff0

There are no comments on this comment yet.