这个递归正则表达式究竟是如何工作的? [英] How exactly does this recursive regex work?

问题描述

这是

This is a followup to this question.

Have a look at this pattern:

(o(?1)?o)

It matches any sequence of o with a length of 2ⁿ, with n ≥ 1.
It works, see regex101.com (word boundaries added for better demonstration).
The question is: Why?

In the following, the description of a string (match or not) will simply be a bolded number or a bolded term that describes the length, like 2ⁿ.

Broken down (with added whitespaces):

( 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.

I don't understand why this doesn't match 2n, but 2ⁿ, because I would describe the pattern as *an undefined number of o o, stacked into each other.

Visualization:

No recursion, 2 is a match:

oo

One recursion, 4 is a match:

o  o
 oo

So far, so easy.

Two recursions. Obviously wrong because the pattern does not match 6:

o    o
 o  o
  oo

But why? It seems to fit the pattern.

I conclude that it's not simply the plain pattern that is repeated because otherwise 6 would have to match.

But according to regular-expressions.info:

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

and

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

So it does seem to simply rematch the regex code without an information about the previous match of the capture group.

Can someone explain and maybe visualize why this pattern matches 2ⁿ and nothing else?

Edit:

It was mentioned in the comments:

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.

解决方案

You understand recursion correctly. Word boundaries baffle you here. The \b around the pattern require the regex engine to only match the string if it is not preceded and followed with word chars.

See how the recursion goes here:

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

(?1) is then replaced with (o(?1)?o):

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

Then again:

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

See the regex demo without word boundaries.

Why adding (?>...) in the example above? Each recursion level in PHP recursive regexes is atomic, unlike Perl, and once a preceding level fails, the engine does not go back to the following one.

When you add word boundaries, the first o and last o matched cannot have any other word chars before/after. So, ooo won't match then.

See Recursive Regular Expressions explained step by step and Word Boundary: \b at rexegg.com, too.

Why does oooooo not get matched as a whole but as oooo and oo?

Again, each recursion level is atomic. oooooo is matched like this:

• (o(?1)?o) matches the first o
• (?1)? gets expanded and the pattern is now (o(?>o(?1)?o)?o) and it matches the second o in the input
• It goes on until (o(?>o(?>o(?>o(?>o(?>o(?>o(?1)?o)?o)?o)?o)?o)?o)?o) that does not match the input any longer, backtracking happens, we go to the 6th level,
• The whole 6th recursion level also fails since it cannot match the necessary amount of os
• This goes on until the level that can match the necessary amount of os.

See the regex debugger:

这篇关于这个递归正则表达式究竟是如何工作的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！