编辑:我选择了 ridgerunner 的答案,因为它包含解决问题所需的信息。但我也想为特定问题添加一个完全充实的解决方案,以防其他人也想完全理解这个例子。您会在下方某处找到它。
这个问题是关于阐明递归表达式的 PHP 正则表达式引擎的行为。 (如果您知道如何在不使用递归 PHP 正则表达式的情况下正确匹配下面的字符串,那非常酷,但这不是问题所在。)
a(?:(?R)|a?)a
这是一个简单的表达式,旨在匹配字符“a”或什么都不匹配,嵌套在字符“a”的一个或多个嵌套中。例如,aa、aaa、aaaa、aaaaa。您不需要为此使用递归:
aa*a
会很好用。但重点是使用递归。
这是一段代码,您可以运行它来测试我的失败模式:
<?php
$tries=array('a','aa','aaa','aaaa','aaaaa','aaaaaa');
$regex='#a(?:(?R)|a?)a#';
foreach ($tries as $try) {
echo $try." : ";
if (preg_match($regex,$try,$hit)) echo $hit[0]."<br />";
else echo 'no match<br />';
}
?>
在这个模式中,两个“a”构成了一个交替。在交替中,我们要么匹配整个模式的递归(两个“a”构成一个交替),要么匹配字符“a”,可选为空。
在我看来,对于“aaaa”,这应该匹配“aaaa”。
但这是输出:
a : no match
aa : aa
aaa : aaa
aaaa : aaa
aaaaa : aaaaa
aaaaaa : aaa
有人可以解释输出的第三行和第五行发生了什么吗? 我试过追踪我想象引擎必须走的路径,但我一定是想象错了。为什么引擎返回“aaa”作为“aaaa”的匹配项?是什么让它如此渴望?我一定是在想象匹配树的顺序错误。
我意识到
#(?:a|a(?R)a)*#
有点效果,但我的问题是为什么其他模式没有效果。
非常感谢!
最佳答案
优秀(且困难)的问题!
首先,使用 PCRE 正则表达式引擎,(?R)
的行为就像一个原子组(与 Perl 不同?)。一旦匹配(或不匹配),递归调用内发生的匹配就是最终的(递归调用内保存的所有回溯面包屑都将被丢弃)。但是,正则表达式引擎确实保存了整个 (?R)
表达式匹配的内容,并且可以将其返回并尝试其他替代方案以实现整体匹配。为了描述正在发生的事情,让我们稍微更改您的示例,以便更容易讨论和跟踪每一步匹配的内容。代替:aaaa
作为主题文本,让我们使用:abcd
。让我们将正则表达式从 '#a(?:(?R)|a?)a#'
更改为:'#.(?:(?R)|.?).# '
。正则表达式引擎匹配行为相同。
匹配正则表达式:/.(?:(?R)|.?)./
到:"abcd"
answer = r'''
Step Depth Regex Subject Comment
1 0 .(?:(?R)|.?). abcd Dot matches "a". Advance pointers.
^ ^
2 0 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 1).
^ ^
3 1 .(?:(?R)|.?). abcd Dot matches "b". Advance pointers.
^ ^
4 1 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 2).
^ ^
5 2 .(?:(?R)|.?). abcd Dot matches "c". Advance pointers.
^ ^
6 2 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 3).
^ ^
7 3 .(?:(?R)|.?). abcd Dot matches "d". Advance pointers.
^ ^
8 3 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 4).
^ ^
9 4 .(?:(?R)|.?). abcd Dot fails to match end of string.
^ ^ DEPTH 4 (?R) FAILS. Return to step 8 depth 3.
Give back text consumed by depth 4 (?R) = ""
10 3 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches EOS.
^ ^ Advance regex pointer.
11 3 .(?:(?R)|.?). abcd Required dot fails to match end of string.
^ ^ DEPTH 3 (?R) FAILS. Return to step 6 depth 2
Give back text consumed by depth3 (?R) = "d"
12 2 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches "d".
^ ^ Advance pointers.
13 2 .(?:(?R)|.?). abcd Required dot fails to match end of string.
^ ^ Backtrack to step 12 depth 2
14 2 .(?:(?R)|.?). abcd Match zero "d" (give it back).
^ ^ Advance regex pointer.
15 2 .(?:(?R)|.?). abcd Dot matches "d". Advance pointers.
^ ^ DEPTH 2 (?R) SUCCEEDS.
Return to step 4 depth 1
16 1 .(?:(?R)|.?). abcd Required dot fails to match end of string.
^ ^ Backtrack to try other alternative. Give back
text consumed by depth 2 (?R) = "cd"
17 1 .(?:(?R)|.?). abcd Optional dot matches "c". Advance pointers.
^ ^
18 1 .(?:(?R)|.?). abcd Required dot matches "d". Advance pointers.
^ ^ DEPTH 1 (?R) SUCCEEDS.
Return to step 2 depth 0
19 0 .(?:(?R)|.?). abcd Required dot fails to match end of string.
^ ^ Backtrack to try other alternative. Give back
text consumed by depth 1 (?R) = "bcd"
20 0 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches "b".
^ ^ Advance pointers.
21 0 .(?:(?R)|.?). abcd Dot matches "c". Advance pointers.
^ ^ SUCCESSFUL MATCH of "abc"
'''
正则表达式引擎没有任何问题。正确的匹配是 abc
(或 aaa
用于原始问题。)可以对其他较长的结果字符串进行类似(尽管更长)的步骤序列。
关于php - 递归 PHP 正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8440911/