这种PCRE模式如何检测回文？

Question

_{这个问题是在PCRE模式中使用前瞻,嵌套引用和条件来匹配所有回文的教育演示,包括PCRE手册页中给出的递归模式无法匹配的回文.}

在PHP代码段中检查此PCRE模式:

$palindrome = '/(?x)
^
  (?:
      (.) (?=
              .*
              (
                \1
                (?(2) \2 | )
              )
              $
          )
  )*
  .?
  \2?
$


/';

这种模式似乎可以检测到回文,如本测试案例所示(另见ideone.com):

$tests = array(
  # palindromes
  '',
  'a',
  'aa',
  'aaa',
  'aba',
  'aaaa',
  'abba',
  'aaaaa',
  'abcba',
  'ababa',

  # non-palindromes
  'aab',
  'abab',
  'xyz',
);

foreach ($tests as $test) {
  echo sprintf("%s '%s'\n", preg_match($palindrome, $test), $test);  
}

那么这种模式如何运作？

---

笔记

此模式使用嵌套引用,这是此Java正则表达式如何检测回文中使用的类似技术？,但与Java模式不同,没有外观(但确实使用了条件).

另请注意,PCRE 手册页提供了一个递归模式以匹配一些回文:

# the recursive pattern to detect some palindromes from PCRE man page
^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

手册页警告说这个递归模式无法检测到所有回文(参见:为什么这个递归正则表达式仅在字符重复2 ⁿ -1次时才匹配？并且也在ideone.com上),但是嵌套参考/正向前瞻模式呈现在这个问题可以.

Answer 1

让我们试着通过构造它来理解正则表达式.首先,回文必须以相反的方向以相同的字符序列开始和结束:

^(.)(.)(.) ... \3\2\1$

我们想重写这个,以便...只跟随有限长度的模式,以便我们可以将它转换为*.这可以通过前瞻来实现:

^(.)(?=.*\1$)
 (.)(?=.*\2\1$)
 (.)(?=.*\3\2\1$) ...

但仍然有不寻常的部分.如果我们能够"记录"以前捕获的群组怎么办？如果有可能我们可以将其重写为:

^(.)(?=.*(?<record>\1\k<record>)$)   # \1     = \1 + (empty)
 (.)(?=.*(?<record>\2\k<record>)$)   # \2\1   = \2 + \1
 (.)(?=.*(?<record>\3\k<record>)$)   # \3\2\1 = \3 + \2\1
 ...

可以转换为

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

几乎不错,除了\2(记录的捕获)最初不是空的.它将无法匹配任何东西.如果记录的捕获不存在,我们需要它匹配空.这就是条件表达式的方式.

(?(2)\2|)   # matches \2 if it exist, empty otherwise.

所以我们的表达成了

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

现在它匹配回文的前半部分.下半场怎么样？那么,在上半场匹配后,记录的捕获\2将包含下半场.所以,让我们把它放在最后.

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

我们也想照顾奇长的回文.在第1和第2半之间会有一个自由的角色.

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

这工作不错,除了在一种情况-当仅有1个字符.这也是因为\2没有匹配.所以

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.