20

この質問は、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 n -1回繰り返された場合にのみこの再帰正規表現が一致するのはなぜですか？またideone.comを参照）が、ネストされた参照/ポジティブ先読みパターンが表示されますこの質問ではできます。

4

2 に答える 2

28

正規表現を構築して理解しようとしましょう。まず、回文は、反対方向の同じ文字シーケンスで開始および終了する必要があります。

^(.)(.)(.) ... \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)\2|))$)
 )*.?\2$

これは、1 つのケース (文字が 1 つしかない場合)を除いてうまく機能します。これもまた、\2何も一致しないためです。そう

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.
于 2010-09-19T20:56:09.493 に答える