为什么这个递归正则表达式只匹配一个字符重复2 ^ n - 1次？

Question

在阅读了polygenelubricants关于高级正则表达式技术的系列文章后(特别是这个Java正则表达式如何检测回文？),我决定尝试创建自己的PCRE正则表达式来解析回文,使用递归(在PHP中).

我想出的是:

^(([a-z])(?1)\2|[a-z]?)$

我对这个表达式的理解是它应该匹配零个或一个字符(每个小于2个字符的字符串隐含一个回文,以及在递归中考虑奇数长度的回文),或者两个相同的字符分开通过模式的递归.

不幸的是,它似乎没有那样工作,你可以在www.ideone.com/a9T3F上看到.取而代之的是,只有2的弦^ñ - 1(.即空字符串,a,aaa,aaaaaaa,一¹⁵)重复字符匹配正则表达式.

奇怪的是,如果我改变我的模式,这样的递归是可选的(即^(([a-z])(?1)?\2|[a-z]?)$,见www.ideone.com/D6lJR,它只匹配反复2字符串^ñ倍(即空字符串,a,aa,aaaa,aaaaaaaa,一¹⁶) .

为什么我的正则表达式没有像我期望的那样工作？

注意那些渴望建议不使用正则表达式的人:
这个问题的关键是学习如何正确使用递归正则表达式.我知道这不是确定字符串是否是回文的有效方法,如果由于某种原因必须确定生产代码中的回文,我就不会使用递归正则表达式; 我只是想了解有关正则表达式高级方面的更多信息.

Answer 1

您观察到的现象是由于PCRE子模式递归是原子的,与Perl不同.该手册页实际上非常详细地介绍了这个问题:

在PCRE中(与Python类似,但与Perl不同),递归子模式调用 始终被视为原子组.也就是说,一旦它匹配了一些主题字符串,它就永远不会被重新输入,即使它包含未经验证的替代品并且存在随后的匹配失败.

这可以通过以下方式,其意图匹配包含奇数个字符的字符串回文来说明(例如, "a","aba","abcba","abcdcba"):

    ^(.|(.)(?1)\2)$

这个想法是它匹配单个字符,或者围绕子回文的两个相同字符.在Perl中,这种模式有效; 在PCRE中,如果模式超过三个字符则不会.

考虑主题字符串"abcba":

在顶层,第一个字符匹配,但因为它不在字符串的末尾,所以第一个字符匹配失败; 第二种方法是采用并且递归开始.对子模式1的递归调用成功匹配下一个字符("b").(注意,行测试的开始和结束不是递归的一部分).

回到顶层,将下一个字符("c")与匹配的子模式2进行比较,即"a".这失败了.因为递归被视为原子组,所以现在没有回溯点,因此整个匹配失败.(此时,Perl能够重新进入递归并尝试第二种方法.)但是,如果模式是使用其他顺序的替代方式编写的,则情况有所不同:

    ^((.)(?1)\2|.)$

这次,首先尝试递归替代,并继续递归直到字符用完,此时递归失败.但这一次我们确实有另一种选择,可以在更高层次上尝试.这是一个很大的区别:在前一种情况下,剩下的替代方案是在更深的递归级别,PCRE无法使用.

要更改模式以便匹配所有回文字符串,而不仅仅是那些具有奇数字符的字符串,则很有可能将模式更改为:

    ^((.)(?1)\2|.?)$

同样,这适用于Perl,但不适用于PCRE,并且出于同样的原因.当更深的递归匹配单个字符时,不能再次输入以匹配空字符串.解决方案是将两种情况分开,并将奇数和偶数情况作为更高级别的替代方案写出来:

    ^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

警告!!!

上述回文匹配模式仅在主题字符串不是以比整个字符串短的回文开始时才起作用.例如,虽然"abcba"正确匹配,但如果主题是"ababa",PCRE "aba"在开始时找到回文,则在顶层失败,因为字符串的末尾不跟随.再次,它不能跳回到递归尝试其他替代方案,因此整个匹配失败.

其他参考

• regular-expressions.info/Atomic分组
  • (?>…) 某种风格是原子分组语法
  • Lookarounds (?=…),(?!…),(?<=…),(?<!…),都是原子
  • 占有量词(例如a*+)也是原子的
  • PCRE递归子模式和子程序调用也是原子的

仔细看看这个模式

原子性论证是正确的,但也许并不清楚它是如何解释为什么模式表现得如所观察到的那样.让我们仔细看看这一切是如何适合的:

我们将使用第一种模式:

^(([a-z])(?1)\2|[a-z]?)$

我将使用以下表示法来表示递归:

• 1 表示角色在第一个替代中被捕获到组2中
• 2 表示该角色与第二个替代品匹配
  • 或者,如果2不是字符以上,零重复选项?获行使
• \ 表示该字符在第一个备用中通过对第2组的反向引用进行匹配
• _ 表示递归分支的底部
  • 即使有其他替代方案,也不会重新进入该分支!

现在让我们考虑"aaa"输入:

      _
1 1 1 2 
a a a   # This is the first bottom of the recursion,
        # now we go back to the third 1 and try to match \.
        # This fails, so the third 1 becomes 2.
    _
1 1 2
a a a   # Now we go back to the second 1 and try to match \.
        # This fails, so the second 1 becomes 2.
  _
1 2
a a a   # The second level matched! now we go back to the first level...

_____
1 2 \
a a a   # Now the first 1 can match \, and entire pattern matches!!

现在考虑"aaaaa":

          _
1 1 1 1 1 2
a a a a a  # Fifth 1 can't match \, so it becomes 2. 
        _
1 1 1 1 2
a a a a a  # Fourth 1 can't match \, so it becomes 2.
    _____
1 1 1 2 /
a a a a a  # Here's a crucial point. The third 1 successfully matched.
           # Now we're back to the second 1 and try to match \, but this fails.
           # However, since PCRE recursion is atomic, the third 1 will NOT be
           # reentered to try 2. Instead, we try 2 on the second 1.
_____
1 2 \
a a a a a  # Anchors don't match, so the first 1 becomes 2, and then also the
           # anchors don't match, so the pattern fails to match.

请注意,一旦递归级别与第一个替代项匹配,将来将不会尝试第二个替代(即使这样做可能导致可能匹配),因为PCRE子模式递归是原子的.

现在考虑"aa":

    _
1 1 2 
a a
  _
1 2
a a  # The second level matched by taking the one repetition option on ?.
     # We now go back to the first level, and we can't match \.
     # Since PCRE recursion is atomic, we can't go back to the second level
     # to try the zero repetition option on ?.
_    
2
a a  # Anchors don't match, trying zero option on ? also doesn't help,
     # so the pattern fails to match!

请注意,一旦递归级别与?第二个替代项的一次重复匹配,将来不会尝试零重复选项(即使这样做可能导致可能匹配),因为PCRE子模式递归是原子的.

现在让我们考虑一下 aaaaaaa

              _
1 1 1 1 1 1 1 2  
a a a a a a a 
            _
1 1 1 1 1 1 2  
a a a a a a a 
        _____
1 1 1 1 1 2 \  
a a a a a a a  # A crucial point: the fifth level matched and now the fourth
               # level can't match \, but it does NOT reenter the fifth level to
               # try 2. Instead, the fourth level tries 2.
    _____    
1 1 1 2 \  
a a a a a a a 
  _________    
1 1 1 2 \ \ 
a a a a a a a 
_____________    
1 1 1 2 \ \ \
a a a a a a a  # Entire pattern is a match! 

请注意,即使PCRE子模式递归是原子的,它仍然可以成功匹配由重复2 ⁿ -1次的字符组成的回文.

现在,只是为了好玩,让我们试试"abcba":

          _
1 1 1 1 1 2
a b c b a
        _
1 1 1 1 2
a b c b a

1 1 1 2 
a b c b a   # Third level attempts \, but c does not match a!
            # So we go back to third 1 and try 2.
  _____
1 1 2 \ 
a b c b a 
_________
1 1 2 \ \
a b c b a   # Entire pattern is a match!

也就是说,模式不仅仅匹配"仅当字符重复2 ⁿ -1次"时.它确实可以匹配"abcba"(如ideone.com上所见).但它不能匹配"ababa",也不能匹配"aaaaa"(参见手册页上的警告!),因为PCRE中的子模式递归是原子的.

您可以应用此相同的跟踪过程来解释任何输入上模式的行为.