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. </F> _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
