6

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

我想出的是:

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

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

不幸的是,正如您在www.ideone.com/a9T3F中看到的那样,它似乎并没有那样工作。相反,只有 2 n - 1 个(即空字符串、aaaaaaaaaaaa 15)重复字符的字符串与正则表达式匹配。

奇怪的是,如果我修改我的模式以使递归是可选的(即^(([a-z])(?1)?\2|[a-z]?)$,请参阅www.ideone.com/D6lJR,它只匹配具有重复 2 n次字符的字符串(即空字符串、aaaaaaaaaaaaaaaa 16) .

为什么我的正则表达式没有按我期望的方式工作?

对于那些渴望建议不要使用正则表达式的人的注意事项:
这个问题的重点是学习如何正确使用递归正则表达式。我知道这不是确定字符串是否为回文的有效方法,如果出于某种原因必须确定生产代码中的回文,我不会使用递归正则表达式;我只是有兴趣了解更多关于正则表达式的高级方面。

4

2 回答 2

8

您观察到的现象是由于 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"在开头找到回文,然后在顶层失败,因为字符串的结尾没有跟随。再一次,它无法跳回递归尝试其他替代方案,因此整个匹配失败。

其他参考资料

  • 正则表达式.info/原子分组
    • (?>…)在某种意义上是原子分组语法
    • 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 n -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 n -1 次时”。它确实可以匹配"abcba"如 ideone.com 上所见)。但是,它不能匹配"ababa",也不能匹配"aaaaa"(参见手册页上的警告!),因为 PCRE 中的子模式递归是原子的。

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

于 2010-09-18T04:37:13.007 回答
1

如果您想要一个功能齐全的 PCRE 表达式来匹配回文,您可以使用以下内容:

/^(?:(.)(?=.*(\1(?(2)\2))$))*+.?\2?$/

于 2010-09-19T17:29:25.863 回答