News for hackers. Stuff that matters.
Re:How Google Code Search Worked by toddc on Thursday January 19, 2012 @07:44PM (#3487721)
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) without the backtracking feature, of course. Also of interest is the benchmark data at: http://tusker.org/regex/regex_benchmark.html

Re:How Google Code Search Worked by mdwrigh2 on Thursday January 19, 2012 @10:36PM (#3488189)
> 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.