re.search much slower then grep on some regular expressions

[sjdevnull at yahoo.com]

On Jul 5, 11:13 am, Mark Dickinson <dicki... at gmail.com> wrote:
> Apparently, grep and Tcl convert a regex to a finite state machine.
...
> But not all PCREs can be converted to a finite state machine
...
> Part of the problem is a lack of agreement on what
> 'regular expression' means.   Strictly speaking, PCREs aren't
> regular expressions at all, for some values of the term
> 'regular expression'.  See
>
> http://en.wikipedia.org/wiki/Regular_expression

Formally, there's no lack of agreement that I'm aware of.  Anyone
formally defining it will use something along the lines of what
wikipedia specifies (with "Regular expressions in this sense can
express the regular languages, exactly the class of languages accepted
by finite state automata.").  Colloquially it's used to mean "any text-
matching scheme that looks vaguely like sed/grep regexes".

PCREs are certainly not "real" regular expressions, but they are
colloquially.