[Python-ideas] Regular expression algorithms
jcarlson at uci.edu
Thu Apr 12 18:04:57 CEST 2007
Adam Atlas <adam at atlas.st> wrote:
> Has anyone seen this article?
Yes, it has been posted in the sourceforge tracker as a feature request,
in python-dev, and now here.
> Are its criticisms of Python's regex algorithm accurate?
In the worst-case, yes, Python's regular expression runs in O(2^n) time
(where n is the length of the string you are searching). However, as
stated in the sourceforge entry, and has been stated in other places,
one has to write a fairly useless regular expression to get it into the
O(2^n) running time. For many cases, Python's regular expression engine
is quite competitive with the Thompson NFA.
> If so, might
> it be possible to revise Python's `re` module to use this sort of
> algorithm? I noticed it says that this approach doesn't work if the
> pattern contains backreferences, but maybe the module could at least
> sort of self-optimize by switching to this method when no backrefs
> are used.
It is possible, but only if someone takes the time to offer a patch.
One thing to remember is that as stated in the documentation for
Python's re module, certain operators are "greedy", that is, a* will
pick up as many a's as it possibly can. Where as a base Thompson NFA
will move on to the next state as early as possible, making a* with
Thompson analagous to a*? in the Python (and others') regular expression
engine. Yes, the Thompson NFA can be modified to also be greedy, but
that is a particular characteristic of Python's engine that a Thompson
NFA based engine will have to emulate (along with groups, named
references, etc., which are a PITA for non-recursive engines).
More information about the Python-ideas