这个正则表达式匹配回文：
^((.)(?1)\2|.?)$
无法理解它是如何工作的。递归什么时候结束，什么时候正则表达式从递归子模式中中断并进入"|.?"部分？
谢谢。
编辑：对不起，我没有解释\2和(?1)
(?1)- 指第一个子模式（对自身）
\2- 反向引用第二个子模式的匹配，即(.)
上面的例子是用 PHP 编写的。匹配“abba”（没有中间回文字符）和“abcba” - 有一个中间的非反射字符
问问题
806 次
3 回答
4
^((.)(?1)\2|.?)$
^和分别断言字符串的$开头和结尾。让我们看一下中间的内容，比较有趣：
((.)(?1)\2|.?)
1------------1 // Capturing group 1
2-2 // Capturing group 2
看第一部分(.)(?1)\2，我们可以看到它会尝试匹配任何字符，并且最后是相同的字符（反向引用\2，它指的是匹配的字符(.)）。中间，它会递归匹配整个捕获组 1。请注意，有一个隐式断言（由(.)开头\2匹配一个字符并在结尾匹配相同字符引起）要求字符串至少为 2 个字符. 第一部分的目的是递归地切断字符串的相同末端。
查看第二部分.?，我们可以看到它将匹配一个或 0 个字符。仅当字符串最初的长度为 0 或 1，或者在递归匹配的剩余部分为 0 或 1 个字符之后，才会匹配。第二部分的目的是匹配空字符串或字符串从两端截断后的单个孤独字符。
递归匹配的工作原理：
- 整个字符串必须是回文才能通过，由
^and断言$。我们不能从任何随机位置开始匹配。 - 如果字符串 <= 1 个字符，则通过。
- 如果字符串大于 2 个字符，是否接受仅由第一部分决定。如果匹配，它将被 2 端切断。
- 剩余的如果匹配，只能被 2 端切断，或者如果其长度 <= 1 则通过。
于 2012-07-26T15:27:29.843 回答
4
正则表达式本质上等同于以下伪代码：
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;
}
于 2012-07-26T16:25:55.190 回答
1
我还没有为 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，当失败时它回溯，直到它最终成功。
于 2012-07-26T23:32:19.877 回答