Python 3 - Second Edition

28.6    Catastrophic Backtracking

Finally, let’s look at a problem with modern matching algorithms for regular expressions: In the worst case, they have exponential runtime complexity. Consider the following regular expression:

regex = re.compile(r"P(y+)+thon")  

This regular expression matches strings that contain the name Python with any sequence of consecutive ys. It therefore matches Python as well as Pyyython or Pyyyyyyython.

Within the regular expression, the matching of the y sequence is implemented via the subexpression (y+)+, which allows any number of repetitions of a group of ys that can be repeated any number of times. This specific expression is meaningless in practice, but it serves here as a simple example of a more complex nesting ...