この正規表現は、回文に一致します。
^((.)(?1)\2|.?)$
それがどのように機能するかについて頭を包むことはできません。再帰はいつ終了し、いつ正規表現が再帰サブパターンから外れて"|.?"部分に移動しますか?
ありがとう。
編集：申し訳ありませんが説明しませんでし\2た(?1)
(?1)- 最初のサブパターン (それ自体) を参照
\2- 2 番目のサブパターンの一致への逆参照。(.)
PHPで書かれた上記の例。"abba" (中間回文文字なし) と "abcba" の両方に一致 - 中間の非反射文字を持ちます
正規表現は、基本的に次の擬似コードと同等です。
palin(str) {
if (length(str) >= 2) {
first = str[0];
last = str[length(str)-1];
return first == last && palin(substr(str, 1, length(str)-2));
} else
// empty and single-char trivially palindromes
return true;
}
^((.)(?1)\2|.?)$
およびは、文字列の開始^と$終了をそれぞれアサートします。その間のコンテンツを見てみましょう。これはもっと興味深いものです。
((.)(?1)\2|.?)
1------------1 // Capturing group 1
2-2 // Capturing group 2
最初の部分(.)(?1)\2を見ると、任意の文字と一致しようとし、最後に同じ文字が一致することがわかります（バックリファレンス\2。これは、によって一致する文字を参照し(.)ます）。途中で、キャプチャグループ1全体に対して再帰的に一致します。文字列が少なくとも2文字である必要がある暗黙のアサーション（(.)最初に1文字を一致させ、最後に同じ文字を一致させることによって引き起こされる）があることに注意してください。 \2。最初の部分の目的は、文字列の同じ端を再帰的に切り刻むことです。
2番目の部分.?を見ると、1文字または0文字に一致することがわかります。これは、文字列の最初の長さが0または1の場合、または再帰一致の残りが0または1文字の場合にのみ一致します。2番目の部分の目的は、文字列が両端から切り取られた後、空の文字列または単一の孤独な文字を一致させることです。
再帰的マッチングは機能します：
^ます$。ランダムな位置からマッチングを開始することはできません。PCRE正規表現用の優れたデバッグユーティリティは見つかりませんでした。私が見つけたのは、バイトコードをダンプする方法でした。
$ pcretest -b
PCRE version 7.6 2008-01-28
re> /^((.)(?1)\2|.?)$/x
------------------------------------------------------------------
0 39 Bra
3 ^
4 26 CBra 1
9 6 CBra 2
14 Any
15 6 Ket
18 6 Once
21 4 Recurse
24 6 Ket
27 \2
30 5 Alt
33 Any?
35 31 Ket
38 $
39 39 Ket
42 End
------------------------------------------------------------------
PerlにはPCREよりも優れたデバッグツールがあります。試してみてくださいecho 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x'。これにより、PCREのものと同様のバイトコードが得られるだけでなく、各ステップ、および各ステップでの入力の消費部分と残りの部分も表示されます。
Compiling REx "^((.)(?1)\2|.?)$"
Final program:
1: BOL (2)
2: OPEN1 (4)
4: BRANCH (15)
5: OPEN2 (7)
7: REG_ANY (8)
8: CLOSE2 (10)
10: GOSUB1[-8] (13)
13: REF2 (19)
15: BRANCH (FAIL)
16: CURLY {0,1} (19)
18: REG_ANY (0)
19: CLOSE1 (21)
21: EOL (22)
22: END (0)
floating ""$ at 0..2147483647 (checking floating) anchored(BOL) minlen 0
Guessing start of match in sv for REx "^((.)(?1)\2|.?)$" against "12321"
Found floating substr ""$ at offset 5...
Guessed: match at offset 0
Matching REx "^((.)(?1)\2|.?)$" against "12321"
0 <> <12321> | 1:BOL(2)
0 <> <12321> | 2:OPEN1(4)
0 <> <12321> | 4:BRANCH(15)
0 <> <12321> | 5: OPEN2(7)
0 <> <12321> | 7: REG_ANY(8)
1 <1> <2321> | 8: CLOSE2(10)
1 <1> <2321> | 10: GOSUB1[-8](13)
1 <1> <2321> | 2: OPEN1(4)
1 <1> <2321> | 4: BRANCH(15)
1 <1> <2321> | 5: OPEN2(7)
1 <1> <2321> | 7: REG_ANY(8)
2 <12> <321> | 8: CLOSE2(10)
2 <12> <321> | 10: GOSUB1[-8](13)
2 <12> <321> | 2: OPEN1(4)
2 <12> <321> | 4: BRANCH(15)
2 <12> <321> | 5: OPEN2(7)
2 <12> <321> | 7: REG_ANY(8)
3 <123> <21> | 8: CLOSE2(10)
3 <123> <21> | 10: GOSUB1[-8](13)
3 <123> <21> | 2: OPEN1(4)
3 <123> <21> | 4: BRANCH(15)
3 <123> <21> | 5: OPEN2(7)
3 <123> <21> | 7: REG_ANY(8)
4 <1232> <1> | 8: CLOSE2(10)
4 <1232> <1> | 10: GOSUB1[-8](13)
4 <1232> <1> | 2: OPEN1(4)
4 <1232> <1> | 4: BRANCH(15)
4 <1232> <1> | 5: OPEN2(7)
4 <1232> <1> | 7: REG_ANY(8)
5 <12321> <> | 8: CLOSE2(10)
5 <12321> <> | 10: GOSUB1[-8](13)
5 <12321> <> | 2: OPEN1(4)
5 <12321> <> | 4: BRANCH(15)
5 <12321> <> | 5: OPEN2(7)
5 <12321> <> | 7: REG_ANY(8)
failed...
5 <12321> <> | 15: BRANCH(19)
5 <12321> <> | 16: CURLY {0,1}(19)
REG_ANY can match 0 times out of 1...
5 <12321> <> | 19: CLOSE1(21)
EVAL trying tail ... 9d86dd8
5 <12321> <> | 13: REF2(19)
failed...
failed...
BRANCH failed...
4 <1232> <1> | 15: BRANCH(19)
4 <1232> <1> | 16: CURLY {0,1}(19)
REG_ANY can match 1 times out of 1...
5 <12321> <> | 19: CLOSE1(21)
EVAL trying tail ... 9d86d70
5 <12321> <> | 13: REF2(19)
failed...
4 <1232> <1> | 19: CLOSE1(21)
EVAL trying tail ... 9d86d70
4 <1232> <1> | 13: REF2(19)
failed...
failed...
BRANCH failed...
3 <123> <21> | 15: BRANCH(19)
3 <123> <21> | 16: CURLY {0,1}(19)
REG_ANY can match 1 times out of 1...
4 <1232> <1> | 19: CLOSE1(21)
EVAL trying tail ... 9d86d08
4 <1232> <1> | 13: REF2(19)
failed...
3 <123> <21> | 19: CLOSE1(21)
EVAL trying tail ... 9d86d08
3 <123> <21> | 13: REF2(19)
failed...
failed...
BRANCH failed...
2 <12> <321> | 15: BRANCH(19)
2 <12> <321> | 16: CURLY {0,1}(19)
REG_ANY can match 1 times out of 1...
3 <123> <21> | 19: CLOSE1(21)
EVAL trying tail ... 9d86ca0
3 <123> <21> | 13: REF2(19)
4 <1232> <1> | 19: CLOSE1(21)
EVAL trying tail ... 0
4 <1232> <1> | 13: REF2(19)
5 <12321> <> | 19: CLOSE1(21)
5 <12321> <> | 21: EOL(22)
5 <12321> <> | 22: END(0)
Match successful!
Freeing REx: "^((.)(?1)\2|.?)$"
ご覧のとおり、Perlは最初に(.)失敗するまですべての入力を繰り返し消費し、次にバックトラックを開始して、交互から2番目のブランチを試行し.?、最初の部分の残りの部分\2が失敗すると、最終的に成功するまでバックトラックします。