…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.