这个 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 模式不同的是，有没有lookbehind（但它确实使用条件）。

另请注意，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)$)
 )*

Almost good，除了 \2 （记录的捕获）最初不为空。它只是无法匹配任何东西。如果记录的捕获不存在，我们需要它匹配空。这就是条件表达式的渗透方式。

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

因此我们的表达式变为

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

Now it matches the 回文的前半部分。下半场怎么样？嗯，第一半部分匹配后，记录的捕获 \2 将包含第二半部分。所以让我们把它放在最后。

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

我们还想处理奇数长度的回文。上半场和下半场之间会有一个自由角色。

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

这很有效除非在一种情况下——只有 1 个字符。这又是由于 \2 没有匹配任何内容。所以

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

Answer 2

我想提出我自己的解决方案。
这是我不久前编写的一个正则表达式，用于使用 PCRE/PCRE2 解决匹配回文

^((\w)(((\w)(?5)\5?)*|(?1)|\w?)\2)$

示例：
https://regex101.com/r/xvZ1H0/1