32

我浏览了Atomic Groupingruby​​info的文档,我想到了一些问题:

  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">
4

3 回答 3

58

A()有一些属性(包括(?!pattern),(?=pattern)等和 plain (pattern)),但它们之间的共同属性是grouping,这使得任意模式成为一个单独的单元(单元是我自己的术语),这在重复时很有用.

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

原子分组(?>pattern)还具有非捕获属性,因此内部匹配的文本的位置不会被捕获。

与捕获或非捕获组相比,原子分组增加了原子的属性。这里的原子意味着:在当前位置,找到与原子分组内的模式匹配的第一个序列(首先由引擎如何根据给定的模式匹配定义)并保持它(因此不允许回溯)。

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

例子

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

第一个匹配.*bbabbbabbbbc由于贪婪的量词*。它将保留此匹配,不允许c匹配。匹配器将在字符串末尾的下一个位置重试,同样的事情也会发生。所以根本没有任何东西与正则表达式匹配。


输入字符串:bbabbbabbbbc
Pattern: /((?>.*)|b*)[ac]/,用于测试/(((?>.*))|(b*))[ac]/

此正则表达式有 3 个匹配项,即bba, bbba, bbbbc. 如果您使用第二个正则表达式,它是相同的,但添加了捕获组以用于调试目的,您可以看到所有匹配都是b*内部匹配的结果。

您可以在此处查看回溯行为。

  • 如果没有原子分组/(.*|b*)[ac]/,字符串将只有一个匹配,即整个字符串,因为最后会回溯到 match [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
    

    随后的比赛将从这里继续进行。

于 2013-01-19T07:48:31.587 回答
19

我最近不得不向其他人解释原子组,我想我会在这里调整并分享这个例子。

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

粗体匹配

  • 大狗
  • 小鸟
  • 最大的狗
  • 小猫

演示

对于第一行,正则表达式引擎会找到the . 然后它会继续处理我们的形容词(big, small, biggest),它会发现big。匹配big后,它继续并找到空间。然后它会查看我们的宠物(cat, dog, bird),找到cat,跳过它,然后找到dog

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

对于第三行,我们的正则表达式会 find the ,它会继续查找与当前要求big匹配的内容,然后继续。它找不到空间,所以它回溯(将位置倒回到它所做的最后选择)。它会跳过、跳过并查找也符合即时要求的内容。然后它找到空间。它跳过并匹配。bigsmallbiggestcatdog

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


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

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

粗体匹配

  • 大狗
  • 小鸟
  • 最大的狗
  • 小猫

演示

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

对于第三行,我们的正则表达式会 find the ,它会继续查找与当前要求big匹配的,然后继续。它找不到空间,但作为引擎做出的最后选择的原子组不允许重新检查该选择(禁止回溯)。由于它不能做出新的选择,所以匹配必须失败,因为我们的简单表达式没有其他选择。


这只是一个基本的总结。引擎不需要查看整个cat就知道它不匹配dog,只需查看c就足够了。在尝试匹配bird 时,cincatdin 狗足以告诉引擎检查其他选项。

但是,如果您有 ... ((cat|snake)|dog|bird),那么引擎当然还需要检查蛇,然后再掉到前一组并检查狗和鸟。

还有很多选择是引擎在不经过可能看起来不匹配的情况下无法决定的,这就是导致回溯的原因。如果有((red)?cat|dog|bird),引擎将查看r,退出,注意?量词,忽略子组(red),并寻找匹配项。

于 2017-02-22T06:23:07.137 回答
4

“原子组”是正则表达式永远不会回溯过去的组。因此,在您的第一个示例中/a(?>bc|b)c/,如果bc组中的交替匹配,那么它将永远不会回溯并尝试b交替。如果你稍微改变你的第一个例子来匹配,"abcdabcc"那么你会看到它仍然匹配"abcc"字符串末尾的,而不是"abc"开头的。如果您不使用原子组,那么它可以回溯过去bc并尝试b交替并最终匹配"abc"开始时的 。

至于第二个问题,它有什么不同,那只是你第一个问题的改写。

最后,原子团不是“称为”非捕获基团。这不是他们的替代名称。非捕获组是不捕获其内容的组。通常,当您将正则表达式与字符串匹配时,您可以检索所有匹配的组,如果您使用替换,则可以在替换中使用反向引用,例如\1在其中插入捕获的组。但是非捕获组不提供此功能。经典的非捕获组是(?:pattern). 一个原子组恰好也具有非捕获属性,因此它被称为非捕获组。

于 2013-01-19T07:34:18.453 回答