3 ms·
It's certainly not the only one. Rust's regex crate (of which I'm the author) and Go's regexp package both use finite automata. It should be noted that none of
by burntsushi 4y ago
It's certainly not the only one. Rust's regex crate (of which I'm the author) and Go's regexp package both use finite automata.
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.