It should be noted that none of them build out complete DFAs in the general case. Building a DFA is worst case exponential time and space, and they can in practice be expensive even when not hitting the worst case.
Instead, they use different techniques. RE2 and the regex crate, for example, use a hybrid NFA/DFA that does subset construction at search time. Outside of pathological cases, it provides the speed of a DFA without needing to build the whole thing up front.
Hyperscan is also built on finite automata. GNU grep uses finite automata in many cases too.
PCRE is the pinnacle of deceptive advertising. It is emphatically not Perl-Compatible.
Source: I used to write Perl for a living, and I have battle scars from (¹) above.
To me, it was inconceivable that you could release a major language and not only not have regular expressions built into the language like Perl, but not even have it in the standard library. Crazy.
Rust has a different target problem space, a different standard library philosophy, a package management system, and exists in a world where adding external dependencies is trivial.
Java didn’t have any of those excuses.
The Rust regex crate is also DFA based and safe for untrusted inputs.
In fact for both .NET v5 and v7, they specifically did work to improve the performance of regexes. For example there is a new non-backtracking option. https://devblogs.microsoft.com/dotnet/regular-expression-imp...
You're very wrong, backreferences in general can't be translated to finite automata (NFA is short for nondeterministic finite automaton). See these comments:
> resistant to catastrophic backtracking despite features which normally translate to nfa
I interpret this as you equating NFA with backtracking engines, which would be incorrect. Is my interpretation wrong?
Stephen has put incredible work into having an alternative implementation in .net 7.
For anyone interested in regex engine inner workings and optimizations, including SIMD, the blog post is fantastic.
The design philosophy behind RE2 for those unfamiliar with the library: https://github.com/google/re2/wiki/WhyRE2