PHP：递归模式 - 手册

递归模式

考虑匹配括号内字符串的问题，允许无限嵌套括号。不使用递归，最好的方法是使用匹配到某个固定嵌套深度的模式。不可能处理任意嵌套深度。 Perl 5.6 提供了一个实验性工具，允许正则表达式递归（以及其他功能）。特殊项 (?R) 用于递归的特定情况。此 PCRE 模式解决了括号问题（假设 PCRE_EXTENDED 选项已设置，因此会忽略空格）： \( ( (?>[^()]+) | (?R) )* \)

首先它匹配一个左括号。然后它匹配任意数量的子字符串，这些子字符串可以是：非括号字符序列，或模式本身的递归匹配（即正确括号的子字符串）。最后是一个右括号。

此特定示例模式包含嵌套的无限重复，因此在将模式应用于不匹配的字符串时，使用一次性子模式匹配非括号字符串非常重要。例如，当它应用于 (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa() 时，它会快速产生“无匹配”。但是，如果没有使用一次性子模式，匹配将运行很长时间，因为 + 和 * 重复可以以多种不同的方式分割主题，并且所有这些都必须在报告失败之前进行测试。

为任何捕获子模式设置的值是递归最外层设置子模式值的那些值。如果上面的模式与 (ab(cd)ef) 匹配，则捕获括号的值为“ef”，这是顶层获取的最后一个值。如果添加了额外的括号，得到 \( ( ( (?>[^()]+) | (?R) )* ) \)，则它们捕获的字符串为“ab(cd)ef”，即顶层括号的内容。如果模式中包含超过 15 个捕获括号，则 PCRE 必须获取额外的内存来存储递归期间的数据，它通过使用 pcre_malloc 来完成此操作，并在之后使用 pcre_free 来释放它。如果无法获取内存，它只会保存前 15 个捕获括号的数据，因为无法从递归中给出内存不足错误。

(?1)、(?2) 等也可以用于递归子模式。也可以使用命名子模式：(?P>name) 或 (?&name)。

如果递归子模式引用的语法（通过编号或名称）在它所引用的括号之外使用，则它的作用类似于编程语言中的子例程。之前的示例指出模式 (sens|respons)e and \1ibility 匹配“sense and sensibility”和“response and responsibility”，但不匹配“sense and responsibility”。如果改为使用模式 (sens|respons)e and (?1)ibility，它也会匹配“sense and responsibility”以及其他两个字符串。但是，此类引用必须位于它们所引用的子模式之后。

主题字符串的最大长度是整数变量可以容纳的最大正数。但是，PCRE 使用递归来处理子模式和无限重复。这意味着可用的堆栈空间可能会限制某些模式可以处理的主题字符串的大小。

改进此页面

了解如何改进此页面 • 提交拉取请求 • 报告错误

＋添加注释

用户贡献的注释 8 个注释

上

下

horvath at webarticum dot hu ¶

11 年前

使用 (?R) 项，您只能链接到完整模式，因为它几乎等同于 (?0)。 您不能使用锚点、断言等，并且只能检查字符串是否包含有效层次结构。

这是错误的：^\(((?>[^()]+)|(?R))*\)$

但是，您可以将完整表达式括起来，并将 (?R) 替换为相对链接 (?-2)。 这使得它可以重复使用。 因此，您可以检查复杂的表达式，例如
<?php

$bracket_system = "(\\(((?>[^()]+)|(?-2))*\\))"; // (可重复使用)
$bracket_systems = "((?>[^()]+)?$bracket_system)*(?>[^()]+)?"; // (可重复使用)
$equation = "$bracket_systems=$bracket_systems"; // 等式两边都必须包含有效的括号系统
var_dump(preg_match("/^$equation\$/","a*(a-(2a+2))=4(a+3)-2(a-(a-2))")); // 输出 'int(1)'
var_dump(preg_match("/^$equation\$/","a*(a-(2a+2)=4(a+3)-2(a-(a-2)))")); // 输出 'int(0)'

?>

您也可以使用 'u' 修饰符捕获多字节引号（如果您使用 UTF-8），例如
<?php

$quoted = "(»((?>[^»«]+)|(?-2))*«)"; // (可重复使用)
$prompt = "[\\w ]+: $quoted";
var_dump(preg_match("/^$prompt\$/u","Your name: »write here«")); // 输出 'int(1)'

?>

上

下

emanueledelgrande at email dot it ¶

14 年前

正则表达式中的递归是允许解析具有无限深度的嵌套标签的 HTML 代码的唯一方法。
似乎它还没有成为一种广泛的做法； 网上关于正则表达式递归的内容并不多，到目前为止，此手册页上还没有发布任何用户贡献的注释。
我使用复杂的模式进行了一些测试，以获取具有特定属性或命名空间的标签，只研究子模式的递归而不是整个模式。
这是一个示例，它可以为具有递归下降的快速 LL 解析器提供支持 (http://en.wikipedia.org/wiki/Recursive_descent_parser)

$pattern = "/<([\w]+)([^>]*?) (([\s]*\/>)| (>((([^<]*?|<\!\-\-.*?\-\->)| (?R))*)<\/\\1[\s]*>))/xsm";

preg_match 或 preg_match_all 函数调用在平均 (x)HTML 文档上的性能相当快，可能会促使您选择这种方式，而不是经典的 DOM 对象方法，后者有很多限制，并且它们的解决方法通常性能很差。
我在一个简短的函数中发布了一个示例应用程序（很容易转换为 OOP），它返回一个对象数组


<?php
// 测试函数：
function parse($html) {
 // 我将模式分成了两行，以避免 PHP.net 表单中的长行警报：
 $pattern = "/<([\w]+)([^>]*?)(([\s]*\/>)|".
 "(>((([^<]*?|<\!\-\-.*?\-\->)|(?R))*)<\/\\1[\s]*>))/sm";
 preg_match_all($pattern, $html, $matches, PREG_OFFSET_CAPTURE);
 $elements = array();
 
 foreach ($matches[0] as $key => $match) {
 $elements[] = (object)array(
 'node' => $match[0],
 'offset' => $match[1],
 'tagname' => $matches[1][$key][0],
 'attributes' => isset($matches[2][$key][0]) ? $matches[2][$key][0] : '',
 'omittag' => ($matches[4][$key][1] > -1), // 布尔值
 'inner_html' => isset($matches[6][$key][0]) ? $matches[6][$key][0] : ''
 );
 }
 return $elements;
}

// 作为示例的随机 html 节点：
$html = <<<EOD
<div id="airport">
 <div geo:position="1.234324,3.455546" class="index">
 <!-- 注释测试：
 <div class="index_top" />
 -->
 <div class="element decorator">
 <ul class="lister">
 <li onclick="javascript:item.showAttribute('desc');">
 <h3 class="outline">
 <a href="https://php.net/manual/en/regexp.reference.recursive.php" onclick="openPopup()">链接</a>
 </h3>
 <div class="description">示例描述</div>
 </li>
 </ul>
 </div>
 <div class="clean-line"></div>
 </div>
</div>
<div id="omittag_test" rel="rootChild" />
EOD;

// 应用程序：
$elements = parse($html);

if (count($elements) > 0) {
 echo "找到元素：<b>".count($elements)."</b><br />";
 
 foreach ($elements as $element) {
 echo "<p>Tpl 节点：<pre>".htmlentities($element->node)."</pre>
 标签名：<tt>".$element->tagname."</tt><br />
 属性：<tt>".$element->attributes."</tt><br />
 Omittag：<tt>".($element->omittag ? 'true' : 'false')."</tt><br />
 内部 HTML：<pre>".htmlentities($element->inner_html)."</pre></p>";
 }
}
?>

上

下

Onyxagargaryll ¶

13 年前

这是一种根据字符串的定界符创建多维数组的方法，即我们要分析...

"一些文本 (aaa(b(c1)(c2)d)e)(test) 更多文本"

... 作为多维层。

<?php
$string = "一些文本 (aaa(b(c1)(c2)d)e)(test) 更多文本";

/*
 * 通过字符串的开始和结束定界符对其进行多维分析
 */
function recursiveSplit($string, $layer) {
 preg_match_all("/\((([^()]*|(?R))*)\)/",$string,$matches);
 // 遍历匹配项并继续递归拆分
 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.": ".$matches[1][$i]."</pre><br />";
 recursiveSplit($matches[1][$i], $layer + 1);
 }
 }
 }
 }
}

recursiveSplit($string, 0);

/*

输出：

层 0: aaa(b(c1)(c2)d)e

层 1: b(c1)(c2)d

层 2: c1

层 2: c2

层 0: test
*/
?>

上

下

匿名 ¶

8 年前

sass 解析示例

<?php

$data = 'a { b { 1 } c { d { 2 } } }';

preg_match('/a (?<R>\{(?:[^{}]+|(?&R))*\})/', $data, $m);
preg_match('/b (?<R>\{(?:[^{}]+|(?&R))*\})/', $data, $m);
preg_match('/c (?<R>\{(?:[^{}]+|(?&R))*\})/', $data, $m);
preg_match('/d (?<R>\{(?:[^{}]+|(?&R))*\})/', $data, $m);

/*
Array (
 [0] => a { b { 1 } c { d { 2 } } }
 [R] => { b { 1 } c { d { 2 } } }
 [1] => { b { 1 } c { d { 2 } } }
)
Array (
 [0] => b { 1 }
 [R] => { 1 }
 [1] => { 1 }
)
Array (
 [0] => c { d { 2 } }
 [R] => { d { 2 } }
 [1] => { d { 2 } }
)
Array (
 [0] => d { 2 }
 [R] => { 2 }
 [1] => { 2 }
)
*/

上

下

mzvarik at gmail dot com ¶

3 年前

这个正则表达式可用于解析 IF 条件。

$str = '
(IF_MYVAR)我的变量被打印
(OR_MYVARTWO)我的第二个变量被打印
(OR_ANOTHER)如果使用 OR，则不必每次都使用 END
(ELSE)无论如何兄弟(END)

(IF_BLUE)某物 (IF_SUPERB)超级(END) 蓝色 - 这是一个简单的 IF 条件(END)
';

function isCondition($k) {
// 在这里添加你的用户条件
$conds = [];
$conds['BLUE'] = true;
$conds['MYVARTWO'] = true;
$conds['ELSE'] = true; // 始终为 true
return $conds[$k];
}

function findConditions($str) {
    
$pattern = '~ \(if_([^\)]+)\) ((?: (?!\((end|if_)). | (?R) )*+) \(end\) ~xis';
    
$str = preg_replace_callback($pattern, function($m) {
        
$k = $m[1];
$v = $m[2];
$v = findConditions($v) ?: $v;
        
$ors = preg_split('~(?=\((OR_[^\)]+|ELSE))~is', $v);
        
$v = array_shift($ors); // 主体
                
if (isCondition($k)) return findConditions($v);
else {
foreach ($ors as $or) {
list($k, $v) = explode(")", $or, 2);
$k = substr($k, 1);
if (isCondition($k)) return findConditions($v);
            }
        }
return ''; // 没有匹配的条件
}, $str);
return $str;
};

// 将输出：无论如何兄弟 \n\n 某物蓝色
echo findConditions($str);

上

下

jonah at nucleussystems dot com ¶

13 年前

出现了意外的行为，在我的某些代码中引入了非常难以追踪的错误。这与 preg_match_all 的 PREG_OFFSET_CAPTURE 标志有关。当捕获子匹配的偏移量时，它的偏移量是相对于其父级给出的。例如，如果递归地从以下字符串中提取 < 和 > 之间的值

<这是一个 <字符串>>

你会得到一个看起来像这样的数组

数组
(
[0] => 数组
    (
[0] => 数组
        (
[0] => <这是一个 <字符串>>
            [1] => 0
        )
[1] => 数组
        (
[0] => 这是一个 <字符串>
            [1] => 1
        )
    )
[1] => 数组
    (
[0] => 数组
        (
[0] => <字符串>
            [1] => 0
        )
[1] => 数组
        (
[0] => 字符串
            [1] => 1
        )
    )
)

请注意，最后一个索引中的偏移量为 1，而不是我们期望的 12。解决此问题的最佳方法是使用递归函数遍历结果，并添加父级的偏移量。

上

下

-1

Daniel Klein ¶

12 年前

在递归子模式中，非互斥备选方案的顺序很重要。
<?php
$pattern = '/^(?<octet>[01]?\d?\d|2[0-4]\d|25[0-5])(?:\.(?P>octet)){3}$/';
?>

您可能期望此模式匹配任何以点分十进制表示法（例如“123.45.67.89”）表示的 IP 地址。此模式旨在匹配以下范围内的四个八位字节：0-9、00-99 和 000-255，每个八位字节之间用单个点分隔。但是，只有第一个八位字节可以包含 200-255 之间的值；其余八位字节的值只能小于 200。原因是，如果模式的其余部分失败，则不会回溯递归以查找备选匹配。子模式的第一部分将匹配任何 200-255 八位字节的前两位数字。然后，模式的其余部分将失败，因为八位字节中的第三位数字与“\.”或“$”都不匹配。

<?php
var_export(preg_match($pattern, '255.123.45.67')); // 1 (true)
var_export(preg_match($pattern, '255.200.45.67')); // 0 (false)
var_export(preg_match($pattern, '255.123.45.200')); // 0 (false)
?>

正确的模式是
<?php
$pattern = '/^(?<octet>25[0-5]|2[0-4]\d|[01]?\d?\d)(?:\.(?P>octet)){3}$/';
?>

请注意，前两个备选方案是互斥的，因此它们的顺序无关紧要。但是，第三个备选方案是非互斥的，它现在将仅在头两个备选方案失败时匹配。

<?php
var_export(preg_match($pattern, '255.123.45.67')); // 1 (true)
var_export(preg_match($pattern, '255.200.45.67')); // 1 (true)
var_export(preg_match($pattern, '255.123.45.200')); // 1 (true)
?>

上

下

-1

horvath at webarticum dot hu ¶

11 年前

以下是一些可重复使用的模式。我使用带“x”修饰符的注释来提高可读性。

您还可以编写一个函数，该函数为指定的括号/引号对生成模式。

<?php

/* normal paretheses */
$simple_pattern = "( (?#root pattern)
 ( (?#text or expression)
 (?>[^\\(\\)]+) (?#text)
 |
 \\((?-2)\\) (?#expression and recursion)
 )*
)";

$simple_okay_text = "5( 2a + (b - c) ) - a * ( 2b - (c * 3(b - (c + a) ) ) )";
$simple_bad_text = "5( 2)a + (b - c) ) - )a * ( ((2b - (c * 3(b - (c + a) ) ) )";

echo "Simple pattern results:\n";
var_dump(preg_match("/^$simple_pattern\$/x",$simple_okay_text));
var_dump(preg_match("/^$simple_pattern\$/x",$simple_bad_text));
echo "\n----------\n";

/* some brackets */
$full_pattern = "( (?#root pattern)
 ( (?#text or expression)
 (?>[^\\(\\)\\{\\}\\[\\]<>]+) (?#text not contains brackets)
 |
 (
 [\\(\\{\\[<] (?#start bracket)
 (?(?<=\\()(?-3)\\)| (?#if normal)
 (?(?<=\\{)(?-3)\\}| (?#if coursed)
 (?(?<=\\[)(?-3)\\]| (?#if squared)
 (?1)\\> (?#else so if tag)
 ))) (?#close nested-but-logically-the-some-level subpatterns)
 )
 )*
)";

$full_okay_text = "5( 2a + [b - c] ) - a * ( 2b - {c * 3<b - (c + a) > } )";
$full_bad_text = "5[ 2a + [b - c} ) - a * ( 2b - [c * 3(b - c + a) ) ) }";

echo "Full pattern results:\n";
var_dump(preg_match("/^$full_pattern\$/x",$simple_okay_text));
var_dump(preg_match("/^$full_pattern\$/x",$full_okay_text));
var_dump(preg_match("/^$full_pattern\$/x",$full_bad_text));
echo "\n----------\n";

/* some brackets and quotes */
$extrafull_pattern = "( (?#root pattern)
 ( (?#text or expression)
 (?>[^\\(\\)\\{\\}\\[\\]<>'\"]+) (?#text not contains brackets and quotes)
 |
 (
 ([\\(\\{\\[<'\"]) (?#start bracket)
 (?(?<=\\()(?-4)\\)| (?#if normal)
 (?(?<=\\{)(?-4)\\}| (?#if coursed)
 (?(?<=\\[)(?-4)\\]| (?#if squared)
 (?(?<=\\<)(?-4)\\>| (?#if tag)
 ['\"] (?#else so if static)
 )))) (?#close nested-but-logically-the-some-level subpatterns)
 )
 )*
)";

$extrafull_okay_text = "5( 2a + ['b' - c] ) - a * ( 2b - \"{c * 3<b - (c + a) > }\" )";
$extrafull_bad_text = "5( 2a + ['b' - c] ) - a * ( 2b - \"{c * 3<b - (c + a) > }\" )";

echo "Extra-full pattern results:\n";
var_dump(preg_match("/^$extrafull_pattern\$/x",$simple_okay_text));
var_dump(preg_match("/^$extrafull_pattern\$/x",$full_okay_text));
var_dump(preg_match("/^$extrafull_pattern\$/x",$extrafull_okay_text));
var_dump(preg_match("/^$extrafull_pattern\$/x",$extrafull_bad_text));

/*

Outputs:

Simple pattern results:
int(0)
int(0)

----------
Full pattern results:
int(0)
int(0)
int(0)

----------
Extra-full pattern results:
int(0)
int(0)
int(0)
int(0)

*/

?>

＋添加注释