> Matching regular expressions can be done in linear time.

Unfortunately, the expression "regular expression" has been so abused in the context of programming that, unless otherwise specified, we cannot expect it to correspond to the well-defined regular expression that is used in formal language theory.

For example, statements such as "you can use regular expressions to parse HTML" and "regexps aren't regular" (mentioned in this thread) are now acceptable. I wish people would at least say "extended regular expressions", but it's a lost cause.

My "point" was a joke about PCRE, the present regexp engine in Python and most other open source languages.

The answer I got (in addition to a couple of good introductory lectures I should send to people :-) ) seems to be that is sucks. :-(