正则表达式引擎如何解析具有递归子模式的正则表达式以匹配回文？

问题描述 投票：0回答：4

这个正则表达式匹配回文： 

^((.)(?1)\2|.?)$

我无法理解它是如何工作的。 递归何时结束，以及正则表达式何时从递归子模式中断并转到 

"|.?"
部分？

编辑：抱歉我没有解释

\2
和
(?1)

(?1)
- 指第一个子模式（对其自身）

\2
- 向后引用第二个子模式的匹配，即 
(.)

上面的例子是用 PHP 编写的。匹配“abba”（无中间回文字符）和“abcba” - 具有中间的非反射字符。

php regex recursion pcre palindrome
4个回答
4
投票

^((.)(?1)\2|.?)$

^
和
$
分别断言字符串的开头和结尾。我们看看中间的内容，比较有趣：

((.)(?1)\2|.?)
1------------1 // Capturing group 1
 2-2           // Capturing group 2

看第一部分

(.)(?1)\2
，我们可以看到它会尝试匹配任何字符，以及末尾的相同字符（反向引用
\2
，指的是
(.)
匹配的字符）。在中间，它将递归匹配整个捕获组 1。请注意，有一个隐式断言（由 
(.)
匹配开头的一个字符和 
\2
匹配结尾的相同字符引起）需要字符串至少 2 个字符。第一部分的目的是递归地砍掉字符串的相同末端。

看第二部分

.?
，我们可以看到它会匹配1个或0个字符。仅当字符串最初长度为 0 或 1，或者递归匹配的剩余部分为 0 或 1 个字符时，才会匹配。第二部分的目的是匹配空字符串或字符串从两端截断后的单个孤独字符。

递归匹配的工作原理：

  • 整个字符串必须是回文才能传递，由 
    ^
    和 
    $
    断言。我们无法从任意位置开始匹配。
  • 如果字符串是 <= 1 character, it passes.
  • 如果字符串大于2个字符，则仅由第一部分决定是否接受。如果匹配的话就会被两端砍断。
  • 剩下的如果匹配，只能被两端切碎，如果长度为<= 1.
    • 则通过
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;
}
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
的剩余部分，当失败时它会回溯，直到终于成功了。

0
投票

细分：（演示）

$regex = <<<REGEX
/
^       #start of string
(       #start capture group 1
 (      #start capture group 2 
  .     #match any non-newline character
 )      #end capture group2
 (?1)   #repeat the expression of capture group 1
 \2     #match the character from capture group 2
 |      #or
 .?     #the middle character (if odd length input string) or no character (if even length input string)
)       #end capture group 1
$       #end of string
/x
REGEX;

遍历

redder
（解释不包括正则表达式引擎对不令人满意的尝试进行回溯）：

  1. 匹配字符串的开头

    ^((.)(?1)\2|.?)$
^

  2. 获取外部字符，并使用组 1 作为子模式递归中间字符：

    ^((.)(?1)\2|.?)$
   r      r
      ^^-> edde

  3. 获取外部字符，并使用组 1 作为子模式递归中间字符：

    ^((.)(?1)\2|.?)$
   e      e
      ^^-> dd

  4. 获取外部字符，并使用组 1 作为子模式递归中间字符：

    ^((.)(?1)\2|.?)$
   d      d
      ^^- (zero-width position)

  5. 匹配字符串中间的零宽度位置：

    ^((.)(?1)\2|.?)$
            ^^- (zero-width position)

  6. 匹配字符串结尾：

    ^((.)(?1)\2|.?)$
               ^

遍历

kayak
（解释不包括正则表达式引擎对不令人满意的尝试进行回溯）：

  1. 匹配字符串的开头

    ^((.)(?1)\2|.?)$
^

  2. 获取外部字符，并使用组 1 作为子模式递归中间字符：

    ^((.)(?1)\2|.?)$
   k      k
      ^^-> aya

  3. 获取外部字符，并使用组 1 作为子模式递归中间字符：

    ^((.)(?1)\2|.?)$
   a      a
      ^^-> y

  4. 匹配字符串中间的单个字符：

    ^((.)(?1)\2|.?)$
            y

  5. 匹配字符串结尾：

    ^((.)(?1)\2|.?)$
               ^
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.