这个正则表达式匹配回文: ^((.)(?1)\2|.?)$
正则表达式引擎如何用递归子模式解析正则表达式?
无法围绕它如何工作。 什么时候递归结束,当正则表达式从递归子模式中断开并转到"|.?"
部分?
谢谢。
编辑:对不起,我没有解释\2
和(?1)
(?1)
- 指第一个子模式(自身)
\2
- 向后引用的匹配第二子模式,这是(.)
上面的例子用PHP编写。同时匹配“ABBA”(无中旬回文字符)和“ABCBA” - 有一个中间的非反射特性
这个正则表达式匹配回文: ^((.)(?1)\2|.?)$
正则表达式引擎如何用递归子模式解析正则表达式?
无法围绕它如何工作。 什么时候递归结束,当正则表达式从递归子模式中断开并转到"|.?"
部分?
谢谢。
编辑:对不起,我没有解释\2
和(?1)
(?1)
- 指第一个子模式(自身)
\2
- 向后引用的匹配第二子模式,这是(.)
上面的例子用PHP编写。同时匹配“ABBA”(无中旬回文字符)和“ABCBA” - 有一个中间的非反射特性
^((.)(?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个字符后,才会匹配。第二部分的目的是在两端截断字符串后匹配空字符串或单个孤立字符。
递归匹配的工作原理:
^
和$
断言。我们无法从任何随机位置开始匹配。正则表达式基本上等同于下面的伪代码:
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;
}
我还没有发现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
的其余部分,当它失败时回溯,直到它最终成功为止。
为什么在这个调试中,有六个'OPEN1',但相应的八个'CLOSE1'?它是否也不是六个'CLOSE1'? – revo 2016-06-27 21:59:11
这可能会在程序员更好,因为这真的不是一个“实际”的问题。 – Jeff 2012-07-26 15:10:10
'。?'可能用于奇数长度的字符串。 – nhahtdh 2012-07-26 15:11:44
对不起,但我可以知道'(?1)'和'\ 2'是什么? – 2012-07-26 15:23:24