6 ms·
Russ's articles are an excellent write-up and explanation. However, many finite-state automata regex implementations have existed for years (e.g. Java http://c
by toddc 15y ago
Russ's articles are an excellent write-up and explanation.
However, many finite-state automata regex implementations have existed for years (e.g. Java http://cs.au.dk/~amoeller/automaton http://cs.au.dk/~amoeller/automaton) without the backtracking feature, of course. Also of interest is the benchmark data at: http://tusker.org/regex/regex_benchmark.html http://tusker.org/regex/regex_benchmark.html
- mdwrigh2 15y ago> However, many finite-state automata regex implementations have existed for years If you read his write-up on RegEx matching, you'll see notes that Thompson wrote an implementation in the mid-60s, so he definitely doesn't claim they're new. What he does claim is that most regex libraries don't use them, even when the regex they're matching to doesn't require backtracking.