Author tim.peters
Date 2006-07-02.13:13:38
SpamBayes Score
Marked as misclassified
Logged In: YES 

Yes, it's easy to provoke exponential-time behavior.  For a
simple example, the regexp


takes O(3**n) time to fail to match strings of the form

"a"*n + "b"

Python's matcher is a backtracking engine, much like Perl's,
and most other languages' non-POSIX re facilities.  There's
nary a DFA in sight ;-)  Jeffrey Friedl's thick O'Reilly
book "Mastering Regular Expressions" is mostly about the
pragmatics of using such engines efficiently:

Note that there's no current hope that this will change: 
because of gimmicks like backreferences, these aren't
CompSci's idea of regular expressions, and no "thoroughly
efficient" implementation technique is known.  For example,
this teensy regexp:


matches strings of a's whose length isn't prime, and finds a
non-trivial factor when the length is composite.  For
harder-to-solve but messier examples:
Date User Action Args
2007-08-23 14:40:58adminlinkissue1515829 messages
2007-08-23 14:40:58admincreate