News for hackers. Stuff that matters.
Re:Efficiency of regular expressions by amalcon on Friday January 21, 2011 @10:40AM (#2127629)
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.

There are no comments on this comment yet.