There are exactly two reasons that regular expression parsing "needs" to be slow. First, we have the "ad hoc extensions for doing this inefficiently and in a l

There are exactly two reasons that regular expression parsing "needs" to be slow. First, we have the "ad hoc extensions for doing this inefficiently and in a limited fashion", and second, we have subexpression capture. Backreferences (the former) are generally only useful in situations where you really ought to be using some other construct. The backreferences are the part that's NP-complete. Subexpression capture is great, and at least that can be done in (low-order) polynomial time with a nondeterministic automaton approach. So really, the only problem is the backreferences.