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

Question

这是 this question 的后续.

看看这个模式:

(o(?1)?o)

它匹配 o 的任何序列长度为2n，n≥1。
It works, see regex101.com (添加单词边界以更好地演示)。
问题是: 为什么？

在下文中，字符串(匹配或不匹配)的描述将只是一个粗体数字或一个描述长度的粗体术语，如 2n .

分解(添加空格):

( 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 ，但是 2n ，因为我会将模式描述为 * 一个未定义的数字 o o ，相互堆叠。

可视化:

无递归， 2 是一场比赛:

oo

一次递归， 4 是一场比赛:

o  o
 oo

到目前为止，很容易。

两次递归。显然是错误的，因为模式不匹配 6 :

o    o
 o  o
  oo

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

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

但据 regular-expressions.info :

(?P<name>[abc])(?1)(?P>name) matches three letters like (?P<name>[abc])[abc][abc] does.

和

[abc])(?1){3} [...] is equivalent to ([abc])[abc]{3}

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

有人可以解释并想象为什么这个模式匹配 2n 没有别的？

编辑:

在评论中提到:

I doubt that referencing a capture group inside of itself is actually a supported case.

regular-expressions.info does mention the technique:

If you place a call inside the group that it calls, you'll have a recursive capturing group.

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

见 regex demo without word boundaries .

为什么要添加 (?>...)在上面的例子中？ Each recursion level in PHP recursive regexes is atomic ，与 Perl 不同，一旦前一级别失败，引擎不会返回到下一级别。

添加单词边界时，第一个 o最后 o匹配之前/之后不能有任何其他单词字符。所以， ooo won't match然后。

见 Recursive Regular Expressions一步一步解释和 Word Boundary: \b 在 rexegg.com 也是如此。

Why does oooooo not get matched as a whole but as oooo and 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 个递归级别也失败了，因为它无法匹配 o 的必要数量。 s

这一直持续到可以匹配所需数量 o 的水平。 s。

见 regex debugger :