logo标签列表

递归的 PHP 正则表达式

phpregexrecursion
25

编辑：我选择了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

请有人解释一下输出的第三行和第五行是什么意思吗？ 我尝试追踪引擎可能要走的路径，但我肯定想错了。为什么引擎会将"aaaa"匹配为"aaa"？是什么让它如此急切？我想我对匹配树的顺序有错觉。

我意识到

#(?:a|a(?R)a)*#

这种方式有点可行，但我的问题是为什么另一种模式不行。

非常感谢！

添加一些锚点（如 ^，$ 或 \b），它应该可以做到你想要的。我猜 PCRE 在没有锚定时会进行一些影响结果的优化。在 Perl 中，此模式始终匹配所有长度超过 1 的完整长度。 - Qtax
@Qtax，我应该补充一下，我也尝试过使用锚点。但是没有成功。例如，$regex='#^(a(?:(?1)|a?)a)#'; 在这个表达式中，(?1)是一个递归语句，它访问第一个括号中的表达式（或匹配，如果Wiseguy是正确的），因此排除了插入符号锚点。 - zx81
此问题已添加到Stack Overflow正则表达式FAQ，位于“控制字符和递归”下。 - aliteralmind
4个回答
13

非常好（且困难）的问题！

首先，使用 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）。对于问题中的另一个更长的结果字符串，可以进行类似（尽管要长得多）的步骤序列。

3
从 PCRE 手册（http://www.pcre.org/pcre.txt）中了解到，被作为子例程调用的子模式（无论是否递归调用）在 PCRE 中始终被视为原子组。这与 Python 相似，但不同于 Perl。 - Qtax
@Qtax “与 Perl 不同”，真是太好了。此外，我更喜欢你的官方链接。 :-) - Wiseguy
@Qtax等人：我确信在Perl中(?R)的行为也是原子性的。你们为什么认为不是呢？所有引用都是指PCRE，并没有说明Perl有所不同。 - Borodin
我收回之前的说法 - Perl文档中提到：请注意，此模式的行为与等效的PCRE或Python构造形式不同。在Perl中，您可以回溯到递归组中，在PCRE和Python中，递归到组被视为原子。但这让我想知道，这是否解释了PCRE引擎不回溯以使.?匹配零长度字符串的原因？ - Borodin
1
@playful：RegexBuddy有一个调试器，但不幸的是，它目前还不支持递归表达式。因此，为了更好地处理PHP下的这些（和其他）递归表达式，我使用preg_replace_callback()函数并递归调用它，并使用静态变量跟踪递归深度，并在每个深度级别打印匹配信息。我为FluxBB论坛项目设计了一个递归BBCode解析器，它使用类似的递归表达式技术，所以我以前做过这个。 - ridgerunner
显示剩余9条评论
12

重要提示：本文介绍了PHP中的递归正则表达式（使用PCRE库）。在Perl本身中，递归正则表达式的工作方式有所不同。

注意：这是按照可以概念化的顺序解释的。正则表达式引擎实际上是反向执行的；它会向下深入到基本情况，然后反向执行回来。

由于外层的a已经明确定义，因此它将匹配两个a之间的a，或前一个递归匹配的整个模式在两个a之间的内容。因此，它只能匹配奇数个a（中间一个加上两个的倍数）。

当长度为三时，aaa是当前递归的匹配模式，因此在第四个递归中，它正在寻找两个a之间的a（即aaa）或前一个递归匹配的模式在两个a之间的内容（即a+aaa+a）。显然，当字符串长度不够时，它无法匹配五个a，因此它所能找到的最长匹配是三个。

长度为六的情况类似，因为它只能匹配“默认”的aaa，或前一个递归的匹配在两个a之间的内容（即a+aaaaa+a）。

然而，并不是所有奇数长度都能匹配。

由于您正在进行递归匹配，因此只能匹配字面上的aaa或a +（上一次递归匹配）+ a。因此，每次连续的匹配都将比上次的匹配多两个a，否则将返回到aaa。

在长度为七（匹配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
作者Jeffrey Friedl所说的“the (?R) construct makes a recursive reference to the entire regular expression”的意思是，正则表达式引擎会尽可能多地替换整个模式以代替(?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 是最终结果。

那个短语听起来对我很准确。"在这一点上的整个表达式"是此时已匹配的全部内容。实际上，当它匹配 "aaa" 时，它会将该匹配项替换为 "(?R)" 并再次运行以查看是否匹配。如果确实匹配（在这种情况下，它将是 "aaaaa"），则将“那个”匹配项放在“(?R)”的位置并再次运行，以此类推。 - Wiseguy
@Borodin，这就是我一开始所说的“整个模式的前一个匹配项”。请看我刚才的评论。你认为我该如何重新表述？ - Wiseguy
@Borodin 为了清晰明了起见，我将“前一个匹配项”更改为“上一次迭代的匹配项”。你认为这样已经足够消除歧义了吗？ - Wiseguy
1
@Borodin 哦，好的。我是在向您解释如何手动解决问题 - 从基本情况开始，使用结果进行下一步执行。在编程方面，它会一直向下深入到基本情况，然后再往回走。这是引起困惑的原因吗？（另外，我将把“迭代”术语更改为“递归”。） - Wiseguy
2
@playful 《精通正则表达式》是用Perl语言编写的，建议使用Perl进行实验。;-) - Qtax
显示剩余6条评论
4

好的，我终于有了它。

我把正确答案授予了ridgerunner，因为他让我找到了解决方案的路径，但我也想写一篇完整的答案来回答特定问题，以便其他人也能完全理解这个例子。

首先是解决方案，然后是一些注意事项。

A. 解决方案

以下是引擎执行的步骤摘要。应该从上到下阅读这些步骤，它们没有编号。递归深度显示在左列中，从零上升到四再返回零。为方便起见，在右上角显示表达式。为了易读性，匹配的“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 a。

我认为递归的深度 0 会作为 a - - a 进行匹配，深度 1 会作为 - a a - 进行匹配。

但实际上，深度 1 首先作为 - a a a 进行匹配。

因此，深度 0 没有任何地方可以继续完成匹配：

a [D1: a a a]

然后呢？我们的字符用完了，但表达式还没有结束。

因此，深度1被舍弃了。请注意，不再通过退回字符来尝试深度1，这会导致我们找到另一个深度1匹配项：a a -

这是因为递归匹配是原子性的。一旦深度匹配成功，就要么全部保留，要么全部舍弃。

一旦深度1被舍弃，深度0就会移到交替器的另一侧，并返回匹配项：a a a

2. 清晰的来源

对我最有帮助的是ridgerunner给出的示例。在他的示例中，他展示了如何跟踪引擎的路径，这恰好是我想理解的。

按照这种方法，我追踪了我们特定示例的引擎全路径。按我的记录，路径长度为25步，因此比上面的摘要要长得多。但总结对我追踪的路径是准确的。

在此对其他所有做出贡献的人表示感谢，特别是Wiseguy的非常有趣的演示。我仍然想知道是否可能我遗漏了什么，Wiseguy的答案是否等同！

-5
经过大量实验，我认为 PHP 正则表达式引擎有问题。在 Perl 下完全相同的代码可以正常工作，并且按照我的预期匹配所有字符串。
递归正则表达式对想象力有很大的挑战，但在我看来，/a(?:(?R)|a?)a/ 应该将 aaaa 匹配为一个包含第二个 a..a 对的 a..a 对，之后第二次递归失败，然后备选的 /a?/ 作为空字符串匹配。
确实，PCRE（或PHP如何使用它）存在问题。http://ideone.com/TibRz 显然应该匹配所有情况，但实际并没有。 - Qtax
@Borodin，感谢你在Perl上进行了测试。情节越来越复杂了。并且，“是的”，就像你说的那样关于aaaa...这就是我写的方式，结果让我感到惊讶。我之前一直很难专注于PHP手册上关于这个主题的页面，但我想今天我会再试一次。:) 最诚挚的祝福 http://php.net/manual/zh/regexp.reference.recursive.php - zx81
5
正则表达式引擎并没有出错，它精确地匹配了被要求匹配的内容。请查看我的答案，以逐步讲解正在发生的情况。 - ridgerunner
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接