这个递归正则表达式是如何工作的？

Question

这是对这个问题的跟进。

请看这个模式：

(o(?1)?o)

它匹配任何由o组成，长度为2ⁿ，n≥1的序列。
它可行，请看regex101.com（为更好地演示添加了单词边界）。
问题是：为什么？ 在接下来的内容中，字符串的描述（匹配或不匹配）将简单地是一个粗体数字或描述长度的粗体术语，如2ⁿ。

分解如下（添加了空格）：

( o (?1)? o )
(           ) # Capture group 1
  o       o   # Matches an o each at the start and the end of the group
              # -> the pattern matches from the outside to the inside.
    (?1)?     # Again the regex of group 1, or nothing.
              # -> Again one 'o' at the start and one at the end. Or nothing.

我不明白为什么这里不是匹配2n，而是2的n次方。因为我会将该模式描述为多个未定义数量的“oo”叠在一起。

可视化：

没有递归，“2”是一个匹配：

oo

一次递归，4是一个匹配：

o  o
 oo

到目前为止，还是很容易的。

两个递归。显然是错误的，因为模式与6不匹配：

o    o
 o  o
  oo

但是为什么呢？它似乎符合模式。

我得出结论，这不仅仅是重复了简单的模式，否则6将会匹配。

但是根据regular-expressions.info：

“(?P[abc])(?1)(?P>name)”匹配三个字母，就像“(?P[abc])[abc][abc]”一样。

并且

“[abc])(?1){3}”等同于“([abc])[abc]{3}”

因此，它似乎只是重新匹配正则表达式代码，而没有关于捕获组先前匹配的信息。

有人能解释一下，可能还能可视化说明为什么这种模式匹配2n而不是其他任何东西吗？

编辑：

评论中提到：

我怀疑在自身内部引用捕获组实际上是一种受支持的情况。

regular-expressions.info确实提到了这种技术：

如果您在所调用的组内放置调用，您将拥有一个递归捕获组。

- Imanuel

---

你正确理解了递归。在这里，单词的分界线让你感到困惑。看这里，6个“o”被匹配得很好。 - Wiktor Stribiżew

很有趣。你说得对，这让我感到困惑。在单词边界方面，6、8、12和16之间有什么区别？我稍后会编辑这个问题。 - Imanuel

Answer 1

你正确理解了递归。但是这里的单词边界让你困惑了。模式周围的\b需要正则表达式引擎仅在字符串前后没有单词字符时才匹配该字符串。

看看这里的递归如何进行：

( o      (?1)?         o )  => oo

(?1) 然后被替换为 (o(?1)?o):

( o   (?>o(?1)?o)?     o )  => oo or oooo

再说一遍：

(o (?>o(?>o(?1)?o)?o)?  o) => oo, oooo, oooooo

请查看没有单词边界的正则表达式演示。

为什么在上面的示例中添加(?>...)？PHP递归正则表达式中的每个递归级别都是原子的,与Perl不同,一旦先前的级别失败，引擎就不会返回到后续级别。

当你添加了单词边界时，第一个匹配的o和最后一个匹配的o之前/之后不能有其他单词字符。所以，ooo不会匹配。

请看rexegg.com上逐步解释的递归正则表达式和单词边界：\b。

为什么oooooo不能被作为一个整体匹配，而是匹配成oooo和oo？

同样，每个递归级别都是原子的。 oooooo匹配如下：

• (o(?1)?o)匹配第一个o
• (?1)?被展开，模式现在是(o(?>o(?1)?o)?o)，它匹配输入中的第二个o
• 一直进行下去，直到(o(?>o(?>o(?>o(?>o(?>o(?>o(?1)?o)?o)?o)?o)?o)?o)?o)不再匹配输入，回溯发生，我们进入第6层，
• 整个第6递归级别也失败了，因为它无法匹配必要数量的os
• 这将继续进行，直到可以匹配必要数量的os的级别。

请参见正则表达式调试器：

- Wiktor Stribiżew

---

我仍然很难理解，为什么6个“o”被匹配为4 + 2，而7个“o”被匹配为6？ - Sebastian Proske

@SebastianProske：检查这个调试器 - 递归结构左侧的第一个o捕获输入字符串中的所有o。然后必须在每个深度级别上容纳每个最终的o。引擎以这种方式在主子模式内回溯。 - Wiktor Stribiżew

@SebastianProske: 这也与每个递归深度是原子性有关（http://www.rexegg.com/regex-recursion.html）：由于`(?1)`之前的第一个`o`匹配了字符串中的所有`o`，因此最后一个`o`没有地方匹配，因为在倒数第二个递归级别中没有更多的文本。 - Wiktor Stribiżew

谢谢，我终于把它全部搞清楚了。我已经将我所采取的步骤作为答案添加了进去 - 但你的回答绝对值得我点赞。 - Sebastian Proske

Answer 2

这更多或少是Wiktors答案的跟进 - 即使删除单词边界，我仍然很难弄清楚为什么oooooo（6）被匹配为oooo和oo，而ooooooo（7）被匹配为oooooo。

以下是详细的工作原理：

在展开递归模式时，内部递归是原子的。使用我们的模式可以将其展开为

(?>o(?>o(?>o(?>o(?>oo)?o)?o)?o)?o)

实际模式中这个过程会再次展开，但是这并不影响解释。

以下是字符串匹配的方法 - 首先匹配oooooo（6个字符）。

(?>o(?>o(?>o(?>o(?>oo)?o)?o)?o)?o)
o   |ooooo                          <- first o gets matched by first atomic group
o   o   |oooo                       <- second o accordingly
o   o   o   |ooo                    <- third o accordingly
o   o   o   o   |oo                 <- fourth o accordingly
o   o   o   o   oo|                 <- fifth/sixth o by the innermost atomic group
                     ^              <- there is no more o to match, so backtracking starts - innermost ag is not matched, cursor positioned after 4th character
o   o   o   o   xx   o   |o         <- fifth o matches, fourth ag is successfully matched (thus no backtracking into it)
o   o   o   o   xx   o   o|         <- sixth o matches, third ag is successfully matched (thus no backtracking into it)
                           ^        <- no more o, backtracking again - third ag can't be backtracked in, so backtracking into second ag (with matching 3rd 0 times)
o   o                      |oo<oo   <- third and fourth o close second and first atomic group -> match returned  (4 os)

现在是ooooooo (7)

(?>o(?>o(?>o(?>o(?>oo)?o)?o)?o)?o)    
o   |oooooo                         <- first o gets matched by first atomic group
o   o   |ooooo                      <- second o accordingly
o   o   o   |oooo                   <- third o accordingly
o   o   o   o   |ooo                <- fourth o accordingly
o   o   o   o   oo|o                <- fifth/sixth o by the innermost atomic group
o   o   o   o   oo  o|              <- fourth ag is matched successfully (thus no backtracking into it)
                         ^          <- no more o, so backtracking starts here, no backtracking into fourth ag, try again 3rd
o   o   o                |ooo<o     <- 3rd ag can be closed, as well as second and first -> match returned (6 os)

- Sebastian Proske