in reply to Re^3: Perl regexp matching is slow??
in thread Perl regexp matching is slow??

The quote that sums it up most obviously is:
What does all this mean to you, as a user? Absolutely nothing. As a user, you don't care if it's regular, nonregular, unregular, irregular, or incontinent. So long as you know what you can expect from it (something this chapter will show you), you know all you need to care about.
This isn't true at all. The choice of whether to use real regular languages or not has direct implications for the efficiency of the matching. The reality is that you can expect very little from backtracking regex implementations as far as performance guarantees go.

But even more important is the comment about tweaking NFAs in ad hoc ways:
As a programmer, if you have a true (mathematically speaking) NFA regex engine, it is a relatively small task to add support for backreferences. A DFA's engine's design precludes the adding of this support, but an NFA's common implementation makes it trivial. In doing so, you create a more powerful tool, but you also make it decidedly nonregular (mathematically speaking). What does this mean? At most, that you should probably stop calling it an NFA, and start using the phrase “nonregular expressions,” since that describes (mathematically speaking) the new situation.
Tweaking the NFA implementation and extending the regex syntax means a lot more than that. For one thing it means that you've now created situations where some regexes can't be matched efficiently. It is a very big deal if you are treating regular expressions as describing the strings rather than describing the algorithms (see my much larger comment elsewhere in this thread). Also the comment about having a "true (mathematically speaking) NFA regex engine" is complete nonsense. He's talking about a backtracking implementation, which the word NFA has nothing to do with (mathematically speaking).