>编辑：我选择了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中的递归正则表达式(使用PCRE库(。递归正则表达式在 Perl 本身中的工作方式略有不同。
注意：这是按照您可以概念化的顺序解释的。正则表达式引擎向后执行此操作;它潜入基本情况并返回。
由于您的外部a明确存在，因此它将匹配两个a之间的a，或者两个a之间的整个模式的先前递归匹配。因此，它只会匹配奇数 a s(中间 1 加 2 的倍数(。
在长度为 3 时，aaa是当前递归的匹配模式，因此在第四次递归时，它正在查找两个a递归 s(即 aaa(之间的a或两个递归a之间的匹配模式(即 a + aaa + a(。显然，当字符串不是那么长时，它无法匹配五a秒，因此它可以进行的最长匹配是三秒。
长度为 6 的类似处理，因为它只能匹配"默认"aaa或前一个递归的匹配项，周围有 a s(即 a + aaaaa + a (。
但是，它并不匹配所有奇数长度。
由于您是递归匹配的，因此您只能匹配文字aaa或a +(prev 递归匹配(+ a 。因此，每场连续的比赛将始终比前一场比赛长两a秒，否则它将平底船并回落到aaa。
在长度为7(与aaaaaaa匹配(时，前一个递归的匹配是后备aaa。所以这一次，即使有七个a，也只会匹配三个(aaa(或五个(a+aaa+a(。
当循环到更长的长度(在本例中为 80(时，请查看模式(仅显示匹配项，而不显示输入(：
no match
aa
aaa
aaa
aaaaa
aaa
aaaaa
aaaaaaa
aaaaaaaaa
aaa
aaaaa
aaaaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaa
aaaaa
aaaaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaa
aaaaa
aaaaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaa
aaaaa
aaaaaaa
aaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
这是怎么回事？好吧，我会告诉你！:-)
当递归匹配比输入字符串长一个字符时，它会回到aaa，正如我们所看到的。在此之后的每次迭代中，模式都会重新开始匹配比前一个匹配的字符多两个字符。每次迭代，输入的长度增加 1，但匹配的长度增加 2。当匹配大小最终赶上并超过输入字符串的长度时，它会重新回到aaa。等等。
或者查看，在这里我们可以看到每次迭代中输入与匹配长度相比有多少个字符：
(input len.) - (match len.) = (difference)
1 - 0 = 1
2 - 2 = 0
3 - 3 = 0
4 - 3 = 1
5 - 5 = 0
6 - 3 = 3
7 - 5 = 2
8 - 7 = 1
9 - 9 = 0
10 - 3 = 7
11 - 5 = 6
12 - 7 = 5
13 - 9 = 4
14 - 11 = 3
15 - 13 = 2
16 - 15 = 1
17 - 17 = 0
18 - 3 = 15
19 - 5 = 14
20 - 7 = 13
21 - 9 = 12
22 - 11 = 11
23 - 13 = 10
24 - 15 = 9
25 - 17 = 8
26 - 19 = 7
27 - 21 = 6
28 - 23 = 5
29 - 25 = 4
30 - 27 = 3
31 - 29 = 2
32 - 31 = 1
33 - 33 = 0
34 - 3 = 31
35 - 5 = 30
36 - 7 = 29
37 - 9 = 28
38 - 11 = 27
39 - 13 = 26
40 - 15 = 25
41 - 17 = 24
42 - 19 = 23
43 - 21 = 22
44 - 23 = 21
45 - 25 = 20
46 - 27 = 19
47 - 29 = 18
48 - 31 = 17
49 - 33 = 16
50 - 35 = 15
51 - 37 = 14
52 - 39 = 13
53 - 41 = 12
54 - 43 = 11
55 - 45 = 10
56 - 47 = 9
57 - 49 = 8
58 - 51 = 7
59 - 53 = 6
60 - 55 = 5
61 - 57 = 4
62 - 59 = 3
63 - 61 = 2
64 - 63 = 1
65 - 65 = 0
66 - 3 = 63
67 - 5 = 62
68 - 7 = 61
69 - 9 = 60
70 - 11 = 59
71 - 13 = 58
72 - 15 = 57
73 - 17 = 56
74 - 19 = 55
75 - 21 = 54
76 - 23 = 53
77 - 25 = 52
78 - 27 = 51
79 - 29 = 50
80 - 31 = 49
出于现在应该有意义的原因，这发生在 2 的倍数上。
用手一步通过
我稍微简化了此示例的原始模式。记住这一点。我们将回到这个问题。
a((?R)|a)a
作者杰弗里·弗里德尔所说的">(？R( 构造对整个正则表达式进行递归引用"是正则表达式引擎将尽可能多地替换整个模式来代替(?R)。
a((?R)|a)a # this
a((a((?R)|a)a)|a)a # becomes this
a((a((a((?R)|a)a)|a)a)|a)a # becomes this
# and so on...
在手工追踪时，您可以从内到外工作。在(?R)|a中，a是你的基本情况。所以我们将从这个开始。
a(a)a
如果它与输入字符串匹配，则将该匹配项 ( aaa ( 带回原始表达式并将其放在 (?R) 的位置。
a(aaa|a)a
如果输入字符串与我们的递归值匹配，则将匹配项 ( aaaaa ( 替换回原始表达式以再次递归。
a(aaaaa|a)a
重复此操作，直到无法使用上一次递归的结果匹配输入。
例
输入：aaaaaa
正则表达式：a((?R)|a)a
从基本情况开始，aaa .
输入是否与此值匹配？是：aaa
通过在原始表达式中放入aaa递归：
a(aaa|a)a
输入是否与我们的递归值匹配？是：aaaaa
通过在原始表达式中放入aaaaa递归：
a(aaaaa|a)a
输入是否与我们的递归值匹配？编号：aaaaaaa
然后我们到此为止。上面的表达式可以重写为(为简单起见(：
aaaaaaa|aaa
由于它不匹配aaaaaaa，因此必须匹配aaa。我们完成了，aaa是最终结果。
好的，我终于有了。
当Ridgerunner让我走上解决方案的道路时，我将正确答案授予了ridgerunner，但我也想写一个特定问题的完整答案，以防其他人也想完全理解这个例子。
首先是解决方案，然后是一些注释。
A. 解决方案
以下是引擎遵循的步骤摘要。应从上到下阅读这些步骤。它们没有编号。递归深度显示在左列中，从零上升到 for，再回到零。为方便起见，表达式显示在右上角。为了便于阅读，匹配的"a"显示在字符串中的位置(显示在最顶部(。
STRING EXPRESSION
a a a a a(?:(?R|a?))a
Depth Match Token
0 a first a from depth 0. Next step in the expression: depth 1.
1 a first a from depth 1. Next step in the expression: depth 2.
2 a first a from depth 2. Next step in the expression: depth 3.
3 a first a from depth 3. Next step in the expression: depth 4.
4 depth 4 fails to match anything. Back to depth 3 @ alternation.
3 depth 3 fails to match rest of expression, back to depth 2
2 a a depth 2 completes as a/empty/a, back to depth 1
1 a[a a] a/[detph 2]a fails to complete, discard depth 2, back to alternation
1 a first a from depth 1
1 a a a from alternation
1 a a a depth 1 completes, back to depth 0
0 a[a a a] depth 0 fails to complete, discard depth 1, back to alternation
0 a first a from depth 0
0 a a a from alternation
0 a a a expression ends with successful match
B. 注释
1. 混乱的根源
这对我来说是违反直觉的。
我们正试图匹配一个 a a a
我假设递归的深度 0 将匹配为 - - a并且深度 1 将匹配为 - a a -
但实际上深度 1 第一次匹配为 - a a a a
所以深度 0 无处可去完成比赛：
a [D1: a a a]
。然后呢？我们没有字符，但表达还没有结束。
因此，深度 1 被丢弃。请注意，不会通过返回字符再次尝试深度 1，这将导致我们进入不同的深度 1 匹配 - a a -
这是因为递归匹配是原子的。一旦深度匹配，它要么全有，要么全无，要么全部保留，要么丢弃。
丢弃深度 1 后，深度 0 移动到交替的另一侧，并返回匹配项：一 一 一
2. 清晰度的来源
对我帮助最大的是山脊跑者给出的例子。在他的示例中，他展示了如何跟踪引擎的路径，这正是我想了解的。
按照这种方法，我为我们的特定示例跟踪了引擎的完整路径。据我所知，路径有 25 个步骤长，因此比上面的摘要要长得多。但摘要对我追踪的路径是准确的。
非常感谢其他所有做出贡献的人，特别是Wiseguy的非常有趣的演讲。我仍然想知道我是否以某种方式错过了什么，而 Wiseguy 的答案可能是一样的！
经过大量的实验，我认为PHP正则表达式引擎坏了。Perl 下完全相同的代码工作正常，并且像我期望的那样从头到尾匹配您的所有字符串。
递归正则表达式很难想象，但在我看来，/a(?:(?R)|a?)a/应该将aaaa匹配为a..a对包含第二个a..a对，之后第二次递归失败，备用/a？/作为空字符串匹配。