[Python-Dev] regexp in Python

Fredrik Lundh fredrik at pythonware.com
Fri Mar 23 12:15:53 CET 2007

Bartlomiej Wolowiec wrote:

> For some time I'm interested in regular expressions and Finite State Machine.
> Recently, I saw that Python uses "Secret Labs' Regular Expression Engine",
> which very often works too slow. Its pesymistic time complexity is O(2^n),
> although other solutions, with time complexity O(n*m) ( O(n*m^2), m is the
> length of the regular expression and n is the length of the text,
> introduction to problem: http://swtch.com/~rsc/regexp/regexp1.html )

that article almost completely ignores all the subtle capturing and left-
to-right semantics that a perl-style engine requires, though.  trust me,
this is a much larger can of worms than you might expect.  but if you're
ready to open it, feel free to hack away.

> major part of regular expressions

the contrived example you used has nothing whatsoever to do with
"major part of regular expressions" as seen in the wild, though.  I'd
be much more interested in optimizations that focuses on patterns
you've found in real code.


More information about the Python-Dev mailing list