Re:Regular Expression Matching Can Be Simple and Fast (2007)
by FreakLegion on Tuesday April 14, 2015 @10:26PM
(#9378566)
I don't know about Perl proper, but PCRE does have an automaton option (which the docs call a DFA but, if I remember correctly, is actually an NFA).
In practice, the vast majority of production regexen don't require backreferences or generalized assertions, so automata are an attractive option. This is particularly true for security applications (e.g. firewalls/NIDS) and public-facing services like Google Code Search. I wouldn't be surprised if people were attacking Snort boxes via PCRE, for example.
Re:Regular Expression Matching Can Be Simple and Fast (2007)
by humanarity on Tuesday April 14, 2015 @11:09PM
(#9378690)
You can add some irregularity to the NFA construction. It's no longer "regular" but you can decorate it with some things like lookbacks, remembering multiple matches and more, and still get the benefit of the NFA. I remember adding a few such features a couple years ago.
This is a perfectly valid thing to do, but it is changing the power of regexes significantly. I feel the article makes this fact easy to overlook—I certainly did until I took a class on automata.
But yes, presumably Perl could use an NFA-based algorithm if given a regex that is actually regular. One of my professors attributed the fact that it doesn't to old patent issues, but I have not been able to find a good source for that. It's also possible that it's just a case of worse is better: backtracking is fast enough 99% of the time, and if performance really matters, perhaps you shouldn't be using regexes anyhow.