代码之家 › 专栏 › 技术社区 › Daniel Vandersluis

为什么这个递归regex只在一个字符重复2^n-1次时匹配?

recursive-regex palindrome pcre regex

Daniel Vandersluis · 技术社区 · 14 年前

读后 polygenelubricants 关于高级正则表达式技术(特别是 How does this Java regex detect palindromes? ,我决定尝试创建自己的pcre regex来解析回文,使用递归(在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的字符串 ⁿ 时间(即空字符串, 一 , aa , aaaa , aaaaaaaa , 一 ^十六 )

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

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

2 回复 | 直到 14 年前

polygenelubricants 14 年前

man page

"a" "aba" "abcba" "abcdcba"
    ^(.|(.)(?1)\2)$
“ABCBA” :

在顶层,第一个字符是匹配的,但由于它不在字符串的结尾,第一个选项失败;第二个选项然后递归开始。对子模式1的递归调用成功匹配下一个字符( "b" )(注意开头并且行尾测试不是递归的一部分)。

回到顶层,下一个角色( "c" )和什么比较子模式2匹配,即 “A” . 这失败了。因为递归被视为一个原子群,现在没有回溯点, 所以整个比赛都失败了。(此时,Perl能够- 输入递归并尝试第二个选项。)但是,如果模式是按照另一个顺序用备选方案编写的,事情是不同:
    ^((.)(?1)\2|.)$
这一次,首先尝试递归替代方法,并继续递归,直到字符用完,此时递归失败。但这次我们有另一个选择更高水平。这是最大的区别:在前一个案例中, 剩下的替代方案处于更深的递归级别,PCRE无法使用。

改变模式以匹配所有回文字符串,而不仅仅是那些字符数为奇数的字符,很容易改变模式如下:
    ^((.)(?1)\2|.?)$
再一次, 这在Perl中有效,但在PCRE中无效,原因也是一样的。 . 当更深的递归与单个字符匹配时,它不能再次输入以匹配空字符串。解决办法是把这两种情况分开,把奇数和偶数写出来作为备选方案。在更高层次:
    ^(?:((.)(?1)\2|)|((.)(?3)\4|.))$
警告!!!!

上面的回文匹配模式仅在主题字符串不是以短于整个字符串。例如,尽管 “ABCBA” 是否正确匹配,如果主题是 "ababa" ,pcre找到回文 “阿坝” 开始时, 然后在顶级失败,因为字符串的结尾不在后面。再一次,它不能跳回到递归中去尝试其他的替代方法, 所以整个比赛都失败了。

其他参考资料

regular-expressions.info/Atomic grouping
- (?>â¦) 在某种程度上是原子分组语法
- 旁观者 (?=â¦) , (?!â¦) , (?<=â¦) , (?<!â¦) ,都是原子的
- Possessive 量词(例如 a*+ )也是原子的
- PCRE递归子模式和子例程调用也是原子的

仔细看看这个图案

原子性参数是正确的,但也许它并不能很明显地解释为什么模式会像观察到的那样运行。让我们仔细看看这一切是如何适应的:

我们将使用第一种模式:

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

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

1 表示字符在第一个替换字符中被捕获到组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” ( as seen on ideone.com )但是,它不能匹配 “阿巴巴” ,也不能匹配 “AAAAA” (参见手册页上的警告!),因为PCRE中的子模式递归是原子的。

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

jaytea 14 年前

如果希望使用完全功能的PCRE表达式来匹配回文,可以使用以下内容:

^?(?)=(1)?(2)\ 2)$)*+?2?美元/