…if your regexes are, you know, <i>regular</i>. 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.<p>This is a perfectly valid thing to do, but it <i>is</i> 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.<p>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.