关于用于递归模式的php regexp

Question

我有这个代码:

$string="some text {@block}outside{@block}inside{@}outside{@} other text";

function catchPattern($string,$layer){
  preg_match_all(
    "/\{@block\}".
      "(".
        "(".
           "[^()]*|(?R)".
        ")*".
      ")".
    "\{@\}/",$string,$nodes);
  if(count($nodes)>1){
    for($i=0;$i<count($nodes[1]); $i++){
      if(is_string($nodes[1][$i])){
        if(strlen($nodes[1][$i])>0){
          echo "<pre>Layer ".$layer.":   ".$nodes[1][$i]."</pre><br />";
          catchPattern($nodes[1][$i],$layer+1);
        }
      }
    }
  }
}

catchPattern($string,0);

这给了我这个输出:

Layer 0:   outside{@block}inside{@}outside

Layer 1:   inside

一切都还可以!但是如果我改变一个字符串和正则表达式:

$string="some text {@block}outside{@block}inside{@end}outside{@end} other text";

function catchPattern($string,$layer){
  preg_match_all(
    "/\{@block\}".
      "(".
        "(".
           "[^()]*|(?R)".
        ")*".
      ")".
    "\{@end\}/",$string,$nodes);
  if(count($nodes)>1){
    for($i=0;$i<count($nodes[1]); $i++){
      if(is_string($nodes[1][$i])){
        if(strlen($nodes[1][$i])>0){
          echo "<pre>Layer ".$layer.":   ".$nodes[1][$i]."</pre><br />";
          catchPattern($nodes[1][$i],$layer+1);
        }
      }
    }
  }
}

catchPattern($string,0);

我没有得到任何输出.为什么？我期待相同的输出.

Answer 1

问题是回溯限制已经耗尽.您始终可以修改回溯限制.但是,对于我遇到的情况,重写正则表达式是更好的解决方案.

您无论如何都无法修改现有的正则表达式并期望使其正常工作,尤其是对于递归正则表达式.您似乎将现有的括号匹配正则表达式并进行修改.你的正则表达式有一些问题:

• [^()]*:没有理由()在{@block}{@end}部分内部排除文本.但更严重的问题是它匹配{}.引擎将一直到最近()或字符串的末尾,无法匹配,然后回溯.这就是达到回溯限制的原因.

  这可以通过将此部分更改[^{}]为禁用{}内部来修复{@block}{@end}.{@block}{@end}由于递归,嵌套仍将匹配.

  请注意,这将完全禁止{}在其中指定为文本{@block}{@end}.根据转义方案,可以修改正则表达式以允许这种情况.

  我也会改变的量词[^{}]从*到+,因为没有理由在整个集团的量词来匹配一个空字符串([^{}]+|(?R))是*.

  /\{@block\}((?:[^{}]+|(?R))*)\{@end\}/
  

• 在上面的修改之后,第二个问题是无效的输入字符串.量词的默认行为是将执行回溯,直到找到匹配或所有可能性都用完为止.因此,在这些情况下,您将达到回溯限制.

  由于[^{}]+可以匹配的内容和递归正则表达式可以匹配的是互斥¹,因此正则表达式不是模糊的,可以匹配而无需回溯.我们可以通过使用占有量词来告诉引擎不要回溯,这是正常的量词,+后面加上了.

最终的解决方案是:

/\{@block\}((?:[^{}]++|(?R))*+)\{@end\}/

演示

脚注

¹:很明显,因为文本匹配[^{}]+永远不会开始{,而与递归正则表达式匹配的文本必须以{.