正则表达式引擎如何解析带有递归子模式的正则表达式？

Question

这个正则表达式匹配回文字符串：^((.)(?1)\2|.?)$ 我无法理解它是如何工作的。 什么时候递归结束，当正则表达式从递归子模式中断并转到"|.?"部分？

谢谢。

编辑：很抱歉我没有解释\ 2和(?1) (?1) - 引用第一个子模式（引用自身） \ 2 - 回溯到第二个子模式的匹配项，即(.) 上面的示例使用PHP编写。可以匹配“abba”（没有中间的回文字符）和“abcba”- 具有中间的非对称字符

- alexy2k

---

这个问题可能更适合在程序员社区讨论，因为它并不是一个“实际”的问题。 - Jeff

.? 可能是用于奇数长度的字符串。 - nhahtdh

抱歉，我可以知道(?1)和\2是什么吗？ - Alvin Wong

Perl拥有比PCRE更好的调试工具，可以尝试：echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x' - ninjalj

@AlvinWong：(?1)=递归到第1组，\2=回溯到第2组匹配 - ninjalj

Answer 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;
}

- Barmar

Answer 2

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

^表示字符串的开头，$表示字符串的结尾。现在我们来看看它们之间更有趣的内容：

注：这是一个正则表达式，可以匹配回文字符串。

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

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

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

递归匹配工作原理：

• 整个字符串必须是回文的才能通过，由^和$断言。我们不能从任意位置开始匹配。
• 如果字符串<= 1个字符，则通过。
• 如果字符串> 2个字符，则仅由第一部分决定是否接受。如果匹配，则将其从两端削减。
• 如果剩余部分匹配，则只能通过两端削减，或者如果其长度<= 1则通过。

- nhahtdh

---

感谢回复。我已经编辑了原帖并加入了更多的解释。\2不是长度。 - alexy2k

"\2" 不是长度，但它确保表达式至少有两个字符长，因为单个字符无法同时匹配 "(.)" 和反向引用 "\2"。 - Sam Mussmann

每次递归都是因为第一部分而发生的，它会处理已去除两个末尾字符的字符串。最终，它会缩小到0或1个字符，然后第二部分匹配，递归停止。 - Barmar

我承认这有点令人困惑。我已经编辑了我的帖子，但我不确定它是否更清晰了。 - nhahtdh

答案已接受。谢谢！我承认我仍然有理解困难，也许我需要学习自动机。 还有一个问题：当一个函数调用自身时，它在到达“底部”状态（比如，在计算阶乘时为1）时返回，并将其乘以先前的调用结果，但是这里何时到达有限状态呢？如果有意义的话，正则表达式引擎何时会“现在我逆序匹配‘\2’，一个接一个地进行匹配”？ - alexy2k

@alexy2k: 我不知道正则表达式引擎是如何工作的。我想它会愚蠢地先进入递归匹配 (?1)，然后它将匹配 \2（因为在通用正则表达式中，你不会知道是否存在更多的递归组）。这更像是猜测，所以不要太认真对待这个评论。 - nhahtdh

Answer 3

我还没有找到适用于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 的第二个分支，当它失败时，它会回溯，直到最终成功。

- ninjalj

---

为什么在这个调试中，有六个 OPEN1 但是对应的却有八个 CLOSE1？难道不应该也是六个 CLOSE1 吗？ - revo