3 ms·

…if your regexes are, you know, regular. Which Perl-style regular expressions most definitely are not. So it's not a matter of just implementing the regexes you

by tikhonj 12y ago

…if your regexes are, you know, regular. Which Perl-style regular expressions most definitely are not. So it's not a matter of just implementing the regexes you know faster, but limiting them to a subset of features first. 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.

emmab 12y ago
Automatically downgrade to a more general implementation if those features are used. Add a flag to assert that a regex is actually regular and should use the fast implementation.
FreakLegion 12y ago
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.
humanarity 12y ago
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.

by tikhonj 12y ago

emmab 12y ago

Automatically downgrade to a more general implementation if those features are used. Add a flag to assert that a regex is actually regular and should use the fast implementation.

FreakLegion 12y ago

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.

humanarity 12y ago

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.