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

Question

这是这个问题的后续内容.

看看这个模式:

(o(?1)?o)

它匹配任何o长度为2 ^n的序列,其中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 ⁿ,因为我会将模式描述为*未定义的数字o o,相互堆叠.

可视化:

没有递归,2是匹配:

oo

一次递归,4是匹配:

o  o
 oo

到目前为止,这么容易.

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

o    o
 o  o
  oo

但为什么？它似乎符合这种模式.

我的结论是,这不仅仅是重复的普通模式,因为否则6必须匹配.

但根据regular-expressions.info:

(?P<name>[abc])(?1)(?P>name)像三个字母一样匹配(?P<name>[abc])[abc][abc].

和

[abc])(?1){3} [...]相当于 ([abc])[abc]{3}

因此,它似乎只是重新匹配正则表达式代码而没有关于捕获组的上一个匹配的信息.

有人可以解释并可能想象出为什么这个模式匹配2 ⁿ而不是别的吗？

编辑:

评论中提到:

我怀疑引用自身内部的捕获组实际上是一个支持的案例.

regular-expressions.info确实提到了这个技术:

如果您在其调用的组内发出呼叫,您将拥有一个递归捕获组.

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

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

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

添加单词边界时，第一个o和最后一个o匹配的前后不能有任何其他单词字符。那么，ooo 就不会匹配了。

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

为什么oooooo不是整体匹配而是 asoooo和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)不再与输入匹配，发生回溯，我们进入第六层，
• o整个第六个递归级别也失败了，因为它无法匹配所需的s数量
• 这一直持续到可以匹配必要数量的 s 的级别o。

查看正则表达式调试器：