Yes, you may have an exponential space problem but lets be precise about that: the regular expression is compiled to a graph, and in the worst case that graph m

Yes, you may have an exponential space problem but lets be precise about that: the regular expression is compiled to a graph, and in the worst case that graph may occupy exponential space. In other words if you do hit the worst case, your could will fail at compile time (of the regexp). The alternative is your regexp may take exponential time if it is given a pathological input. Unfortunately when this happens depends on the backtracking algorithm used, and worse still often happens on regexp's that wouldn't have used exponential space (they are very rare). So what you end up with is a program with hidden bugs: there are inputs that make your program effectively go infinite and fail at random times, but your tests almost certainly won't find them. This has bitten me several times. I'll take a program that fails when unconditionally when tested over a program that fails at random in production any time. PHP 7 managed to make the situation worse. They decided they would solve the randomly hanging problem by adding a step limit to the regexp execution. When the regexp hit the step limit the regexp appeared to return no matches. So you effectively ended up with the situation where the regexp engine returned no matches. So when you took a program that worked on PHP 5, on PHP 7 it would mysteriously misbehave at random times. But not in the easily diagnosable way PHP 5 would hang - in an infinite loop at the point the problem occurred. No - the program would proceed on it's merry way until 1000's of statements later the fact that it missed a match would rear it's ugly head, usually in the most obtuse manner.