正则表达式PREG_BACKTRACK_LIMIT_ERROR在提取真正长的文本时不贪婪

Question

我有一串表格：

一些TextOpeningReally真的很长Text...ClosingMore TextClosingEven更多的文本

我想提取非常长的文本..。从带有正则表达式的字符串中。直到第一次关门。

如果我执行这样的正则表达式：

$pMatch = "'\[Opening\](.+)\[Closing\]'si";

这给了我：

真的很长的Text...ClosingMore文本

我也可以使它不像这样贪婪：

$pMatch = "'\[Opening\](.+?)\[Closing\]'si";

它可以给出正确的输出：

非常长的短信..。

然而，如果我把“真的很长的文字.”对于实际非常长的文本，它不起作用，相反，我收到了一个PREG_BACKTRACK_LIMIT_ERROR。如果使用贪婪的正则表达式，则不会出现错误。我只是得到了错误的输出，就像在第一种情况下。

我使用正则表达式已经有一段时间了，但这一次让我很困惑。是否有一种方法可以使其与正则表达式一起工作，还是正则表达式不适合此任务？

下面是用于再现问题的PHP代码：

<?php

  $sShortString = "Some Text[Opening]Really Really Long Text...[Closing]More Text[Closing]Even More Text";
  $sLongString = "Some Text[Opening]".str_repeat("BLAH", 1000000)."[Closing]More Text[Closing]Even More Text";

  $pGreedyMatch = "'\[Opening\](.+)\[Closing\]'si";
  $pNonGreedyMatch = "'\[Opening\](.+?)\[Closing\]'si";

  header("Content-Type: text/plain");

  if (preg_match($pGreedyMatch, $sShortString, $aMatch)) {
    echo "Greedy Match:\n";
    print_r($aMatch);
  }

  if (preg_match($pNonGreedyMatch, $sShortString, $aMatch)) {
    echo "Non-Greedy Match:\n";
    print_r($aMatch);
  }

  if (preg_match($pGreedyMatch, $sLongString, $aMatch)) {
    echo "Greedy Match:\n";
    echo "Length: ".strlen($aMatch[1])."\n";
  }

  if (preg_match($pNonGreedyMatch, $sLongString, $aMatch)) {
    echo "Non-Greedy Match:\n";
    echo strlen($aMatch[1]);
  } else {
    echo "Non-Greedy Doesn't Match!\n";
  }

  $iLastError = preg_last_error();
  if ($iLastError == PREG_BACKTRACK_LIMIT_ERROR) {
    echo "It's because the backtrack limit was exceeded!\n";
  }

?>

我得到了输出：

Greedy Match:
Array
(
    [0] => [Opening]Really Really Long Text...[Closing]More Text[Closing]
    [1] => Really Really Long Text...[Closing]More Text
)
Non-Greedy Match:
Array
(
    [0] => [Opening]Really Really Long Text...[Closing]
    [1] => Really Really Long Text...
)
Greedy Match:
Length: 4000018
Non-Greedy Doesn't Match!
It's because the backtrack limit was exceeded!

我已经通过使用贪婪的正则表达式并使用额外的代码从结束后的文本中删除了它。我想更好地理解幕后发生了什么，为什么需要做这么多的回溯，以及是否有一种方法可以修改正则表达式以使其执行任务。

我真的很感激你的洞察力！

Answer 1

一个非贪婪的量词是有代价的，因为每次它读取一个字符时，它都要检查模式的末尾。

在上面的模式中，每次.在(.+?)中匹配时，它都会检查下面的字符是否与[Closing]匹配。每次发生这种情况时，如果不匹配，就必须回溯并继续搜索。这就是为什么回溯限制用尽了。

可以这样重写模式：

'\[Opening\]([^\[]*(?:\[(?!Closing)[^\[]*)*)(*SKIP)\[Closing\]'si

让我们一片一片地研究这个模式来理解它。

( 1)我们以\[Opening\]为起点。此模式与开始标记匹配。

2)由于我们的模式本身没有重复，因此使用()(*SKIP)指令作为进一步的优化。这意味着，如果我们不匹配的模式，那么我们将重新启动我们的搜索结束时，我们正在寻找。默认行为将再次开始搜索下一个字符。

为了更好地理解这一点，假设我们的字符串是sometimes we get [Close to matching。当我们到达[时，我们先扫描[Clos，然后才得出结论，这实际上不是我们想要的模式。通常，我们会回溯，然后重新开始查看Close。然而，(*SKIP)允许我们继续在e to matc搜索。

3)在括号中，我们从模式[^\[]*开始，它允许我们匹配尽可能多的不是[的字符。^表示没有，\[用于[，而[]将其包围为字符集。*允许它重复尽可能多的次数。

4)现在，我们有了(?:)*。()允许我们指定一个字符串，?:表示它不会被保存，而*允许它重复我们想要的次数(包括根本不保存)。

5)该字符串中的第一个字符是\[，也就是我们期望作为结束标记的一部分的[。

6)接下来是(?!Closing\])。(?!)是负前瞻。查找意味着解析器将查看下一个字符，或者匹配或不匹配而不使用这些字符。这允许我们匹配一些东西，只要它不是Closing]，而不实际使用它。

7)我们有另一个[^\[]*，它允许我们在无法向前看的情况下继续吃字符。这允许我们在获得类似[Clos的内容后继续使用字符串。

8)最后，我们的正则表达式以\[Closing\]结束。