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.
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