PHP:意外的PREG_BACKTRACK_LIMIT_ERROR

Question

function recursiveSplit($string, $layer) {
    $err = preg_match_all("/\{(([^{}]*|(?R))*)\}/",$string,$matches);
    echo "Elementi trovati: $err<br>";
    if($err == FALSE) echo "preg_match_all ERROR<br>";

    // iterate thru matches and continue recursive split
    if (count($matches) > 1) {
        for ($i = 0; $i < count($matches[1]); $i++) {
            if (is_string($matches[1][$i])) {
                if (strlen($matches[1][$i]) > 0) {
                    echo "<pre>Layer ".$layer.":   ".$matches[1][$i]."</pre><br />";
                    recursiveSplit($matches[1][$i], $layer + 1);
                }
            }
        }
    }
}

$buffer = "{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa{aaaaaaaaaaaaaaaaaa{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}";
recursiveSplit($buffer, 0);

输出

Elementi trovati: 
preg_match_all ERROR
Backtrack limit was exhausted!

这段代码给了我一个PREG_BACKTRACK_LIMIT_ERROR错误...但回溯限制设置为100.000.000。

这是我第一次使用正则表达式，我真的不知道如何解决它。

非常感谢你，马可

Answer 1

catastrophic backtracking的另一个经典案例。今天一定是my lucky day。

/\{(([^{}]*|(?R))*)\}/

仅当大括号嵌套正确时才匹配。当然，它们不在你的字符串中。

现在的问题是，您的正则表达式需要找出可以用106个a构建的所有可能的字符串组合，因为您有嵌套的量词((...)*)*)。它(如果我错了，请纠正我)应该在106!附近的某个地方，

114628056373470835453434738414834942870388487424139673389282723476762012382449946252660360871841673476016298287096435143747350528228224302506311680000000000000000000000000

这很容易打败你的PREG_BACKTRACK_LIMIT。

如果你使用possessive quantifiers来确保你永远不会回到你已经匹配的非大括号中，那么你应该没问题：

/\{(([^{}]*+|(?R))*)\}/