Matching Regexps 200 Times Faster

Re:Matching Regexps 200 Times Faster by JonChesterfield on Tuesday March 18, 2025 @04:55PM (#43404987)

No backreference support in the state machine, disappointing https://github.com/oracle/graal/blob/master/regex/README.md

[ Parent | on HN ]

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

[ Parent | on HN ]

Re:Matching Regexps 200 Times Faster by HackerThemAll on Wednesday March 19, 2025 @04:54PM (#43417224)

and lack of backreferences makes them fast, but crippled.

[ Parent | on HN ]