使用原子分组的困惑——它与Ruby正则表达式中的分组有何不同？

Question

我已经查看了Atomic Grouping和rubyinfo的文档，有些问题浮现在我的脑海中：

1. 为什么会叫做 "原子分组"？相较于一般分组，它具备怎样的 “原子性”?
2. 原子分组与一般分组有何不同？
3. 为什么原子分组被称为非捕获分组?

我尝试了下面的代码来理解，但对输出结果以及它们在同一字符串上的不同处理方式感到困惑。

irb(main):001:0> /a(?>bc|b)c/ =~ "abbcdabcc"
=> 5
irb(main):004:0> $~
=> #<MatchData "abcc">
irb(main):005:0> /a(bc|b)c/ =~ "abcdabcc"
=> 0
irb(main):006:0> $~
=> #<MatchData "abc" 1:"b">

- Arup Rakshit

---

你有阅读过你链接的原子分组文档或命名捕获文档吗？ - mu is too short

@muistooshort 是的，我看过了。但是我需要先澄清基础知识，这样可以让我更好地开始学习。我想知道当我有grouping时，我们为什么需要atomic grouping，它能做什么一般的grouping不能做到的事情。你能帮助我澄清这些基本概念吗？ - Arup Rakshit

此问题已添加到Stack Overflow正则表达式FAQ，位于“分组”下。 - aliteralmind

Answer 1

() 拥有一些属性（包括 (?!pattern), (?=pattern), 等等，还有普通的 (pattern)），但是它们所有的共同特征都是 分组，这使得任意的模式成为了一个单元（单元是我自己的术语），在重复中非常有用。

普通捕获 (pattern) 具有 捕获 和 分组 的属性。捕获意味着文本匹配内部的模式将被捕获，以便您可以在匹配或替换中使用反向引用。非捕获组 (?:pattern) 没有捕获属性，因此与 (pattern) 相比，它会节省一些空间并加速匹配，因为它不存储与模式匹配的字符串的起始和结束索引。

原子组 (?>pattern) 也具有非捕获属性，因此不会捕获文本匹配的位置。

与捕获或非捕获组相比，原子组添加了 原子 特性。在这里，原子意味着：在当前位置，查找匹配模式内的第一个序列（由引擎根据给定模式的匹配方式定义），并保持它（因此不允许回溯）。

没有原子性的组将允许回溯-它仍然会找到第一个序列，然后如果匹配失败，则会回溯并查找下一个序列，直到找到整个正则表达式的匹配或所有可能性都耗尽为止。

示例

输入字符串：bbabbbabbbbc
模式：/(?>.*)c/

.* 的第一次匹配是由于贪婪量词 * 而得到的，为 bbabbbabbbbc。它将保留此匹配，禁止匹配 c。匹配器将在下一个位置重试到字符串的末尾，并发生相同的事情。因此，根本没有匹配正则表达式。

---

输入字符串：bbabbbabbbbc
模式：/((?>.*)|b*)[ac]/，用于测试 /(((?>.*))|(b*))[ac]/

这个正则表达式有三个匹配项，分别是 bba，bbba，bbbbc。如果使用带有捕获组的第二个正则表达式进行调试，可以看到所有的匹配都是由于匹配内部的 b* 而得到的。

您可以在这里看到回溯行为。

• 没有原子分组的情况下，字符串将只有一个匹配项，即整个字符串，因为在末尾回溯以匹配 [ac]。请注意，引擎将回到 .* 退回1个字符进行回溯，因为它仍然有其他可能性。

Pattern: /(.*|b*)[ac]/
bbabbbabbbbc
^             -- Start matching. Look at first item in alternation: .*
bbabbbabbbbc
            ^ -- First match of .*, due to greedy quantifier
bbabbbabbbbc
            X -- [ac] cannot match
              -- Backtrack to ()      
bbabbbabbbbc
           ^  -- Continue explore other possibility with .*
              -- Step back 1 character
bbabbbabbbbc
            ^ -- [ac] matches, end of regex, a match is found

使用原子分组，所有可能性的 .* 都被切断并限制在第一个匹配上。所以在贪婪地匹配整个字符串后失败，引擎必须去匹配 b* 模式，这里成功地找到了正则表达式的一个匹配。

Pattern: /((?>.*)|b*)[ac]/
bbabbbabbbbc
^             -- Start matching. Look at first item in alternation: (?>.*)
bbabbbabbbbc
            ^ -- First match of .*, due to greedy quantifier
              -- The atomic grouping will disallow .* to be backtracked and rematched
bbabbbabbbbc
            X -- [ac] cannot match
              -- Backtrack to ()
              -- (?>.*) is atomic, check the next possibility by alternation: b*
bbabbbabbbbc
^             -- Starting to rematch with b*
bbabbbabbbbc
  ^           -- First match with b*, due to greedy quantifier
bbabbbabbbbc
   ^          -- [ac] matches, end of regex, a match is found

接下来的比赛将从这里继续进行。

- nhahtdh

---

你给出了一个完美的例子，现在为了更清晰，能否在同样的例子中加入如果它是“非原子”匹配的情况？ - Arup Rakshit

@RubyTheBang：我实际上正在编写它。请检查第二个示例，看看是否能够澄清事情。 - nhahtdh

是的，我刚刚完成了。你最后一部分能不能更加可视化 - 看到和清晰地了解正则表达式如何使用输入字符串生成输出的模式 - <MatchData "bbabbbabbbbc" 1:"bbabbbabbbb">。只是想看看在回溯期间正则表达式如何改变它的决策（意味着它如何决定哪个接受和哪个拒绝，以及何时拒绝，如何覆盖并寻找下一个正确的模式）。 - Arup Rakshit

Answer 2

最近我不得不向别人解释原子组，我想我可以调整并分享这个例子。

考虑 /the (big|small|biggest) (cat|dog|bird)/

粗体匹配

• the big dog
• the small bird
• the biggest dog
• the small cat

DEMO

对于第一行，正则表达式引擎会找到the 。 然后它会继续查找我们的形容词（big，small，biggest），找到big。 匹配了big之后，它就继续查找并找到了空格。 然后它查看我们的宠物（cat，dog，bird），找到cat，跳过它，找到了dog。

对于第二行，我们的正则表达式会找到the。 它会继续查找并查看big，跳过它，查找并找到small。 它找到了空格，跳过cat和dog因为它们不匹配，然后找到bird。

对于第三行，我们的正则表达式会找到the， 它继续查找并找到big，它满足立即要求，然后继续执行。 它无法找到空格，所以它回溯（将位置倒回到它最后做出的选择）。 它跳过big，跳过small，并找到了也满足立即要求的biggest。 然后它找到了空格。 它跳过cat，匹配了dog。

对于第四行，我们的正则表达式会找到the。 它会继续查找并查看big，跳过它，查找并找到small。 然后它找到了空格。 它查看并匹配了cat。

---

考虑 /the (?>big|small|biggest) (cat|dog|bird)/

注意形容词上的?>原子组。

匹配结果为粗体所示

• the big dog
• the small bird
• the biggest dog
• the small cat

DEMO

对于第一行，第二行和第四行，我们将得到相同的结果。

对于第三行，我们的正则表达式会找到the ， 然后继续查找匹配big，它满足立即需求，并继续。 它找不到空格，但是原子组作为引擎做出的最后选择，不允许重新检查那个选择（禁止回溯）。 由于它无法做出新的选择，匹配必须失败，因为我们简单的表达式没有其他选择。

---

This is only a basic summary. An engine wouldn't need to look at the entirety of "cat" to know that it doesn't match "dog", merely looking at the "c" is enough. When trying to match "bird", the "c" in "cat" and the "d" in dog are enough to tell the engine to examine other options.

However if you had ..."(cat|snake)|dog|bird", the engine would also, of course, need to examine snake before it dropped to the previous group and examined dog and bird.

There are also plenty of choices an engine can't decide without going past what may not seem like a match, which is what results in backtracking. If you have "(red)?cat|dog|bird", The engine will look at "r", back out, notice the "?" quantifier, ignore the subgroup "(red)", and look for a match.

- Regular Jo

---

这个例子让我终于理解了这个概念，非常简单易懂。谢谢！ - Benny Bottema

Answer 3

“原子组”是指正则表达式永远不会回溯的组。因此，在您的第一个示例/a(?>bc|b)c/中，如果组中的bc选择匹配，则它将永远不会回溯并尝试选取b。如果您稍微修改第一个示例以匹配"abcdabcc"，则可以看到它仍然匹配字符串结尾的"abcc"而不是开头的"abc"。如果您不使用原子组，则可能回溯到bc并尝试b，从而最终匹配字符串开头的"abc"。

至于问题二，它有何不同，那只是对您的第一个问题的另一种表述。

最后，原子组并不被称为非捕获组。那不是它们的替代名称。非捕获组是不捕获其内容的组。通常，当您使用正则表达式匹配字符串时，可以检索所有匹配的组，并且如果您使用替换，可以在替换中使用回溯引用，例如\1将捕获的组插入其中。但非捕获组不提供此功能。经典的非捕获组是(?:pattern)。原子组也具有非捕获属性，因此被称为非捕获组。

- Lily Ballard

---

感谢您对我的痛苦表示关注。这是我的困惑 - “原子组”是指正则表达式永远不会回溯到的一种组合方式，那么什么是回溯？没有“原子组”的情况下，正则表达式如何执行回溯？--- 这就是我整个困惑的区域！您能帮助我形象化吗？ - Arup Rakshit

@RubyTheBang：正则表达式引擎通过逐个匹配表达式的每个组成部分（称为“原子”）来匹配字符串。当它无法匹配时，它会回溯到先前的一个原子，该原子可能是带有交替项的组，或者是由某种重复运算符（?、*、+或{n[,m]}）修改的原子。然后，它会更改所选择的原子匹配并再次尝试。 - Lily Ballard

@RubyTheBang：但是使用/a(bc|b)c/作为模式时，当它无法匹配最后的c时，它可以回溯并选择组中的第二个选择，即b，并将其与之匹配。现在它可以成功地匹配模式中的最后一个c，以获取字符串开头的"abc"。 - Lily Ballard

你能帮我在你的帖子中展示相同的内容吗？我作为一个新手在那个部分仍然感到非常困惑 - 渴望看到引擎是如何内部工作的。 - Arup Rakshit

嗯。对我来说，说引擎不会回溯“过去”原子组似乎是错误的。这让它听起来像是/(aab|a)(?>a)ba/不能匹配aaba，但事实上，引擎会愉快地回溯“过去”原子组，尝试将第一组的匹配从aab更改为a。引擎在回溯时不会尝试不同的原子组匹配，但会回溯“过去”它。 - Mark Amery