Runaway Regular Expressions: Catastrophic Backtracking

This article explains why some regular expressions take years to match against certain strings. A common culprit are nested repetition operators like in (x+x+)+y.