Confusion with Atomic Grouping - how it differs from the Grouping in regular expression of Ruby?

ghz 1years ago ⋅ 5264 views

Question

I have gone through the docs for [Atomic Grouping](http://ruby- doc.org/core-1.9.3/Regexp.html#method-i-named_captures) and rubyinfo and some questions came into my mind:

  1. Why the name "Atomic grouping"? What "atomicity" does it have that general grouping doesn't?
  2. How does atomic grouping differ to general grouping?
  3. Why are atomic groups called non-capturing groups?

I tried the below code to understand but had confusion about the output and how differently they work on the same string as well?

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

Answer

A () has some properties (include those such as (?!pattern), (?=pattern), etc. and the plain (pattern)), but the common property between all of them is grouping , which makes the arbitrary pattern a single unit (unit is my own terminology), which is useful in repetition.

The normal capturing (pattern) has the property of capturing and group. Capturing means that the text matches the pattern inside will be captured so that you can use it with back-reference, in matching or replacement. The non- capturing group (?:pattern) doesn't have the capturing property, so it will save a bit of space and speed up a bit compared to (pattern) since it doesn't store the start and end index of the string matching the pattern inside.

Atomic grouping (?>pattern) also has the non-capturing property, so the position of the text matched inside will not be captured.

Atomic grouping adds property of atomic compared to capturing or non- capturing group. Atomic here means: at the current position, find the first sequence (first is defined by how the engine matches according to the pattern given) that matches the pattern inside atomic grouping and hold on to it (so backtracking is disallowed).

A group without atomicity will allow backtracking - it will still find the first sequence, then if the matching ahead fails, it will backtrack and find the next sequence, until a match for the entire regex expression is found or all possibilities are exhausted.

Example

Input string: bbabbbabbbbc
Pattern: /(?>.*)c/

The first match by .* is bbabbbabbbbc due to the greedy quantifier *. It will hold on to this match, disallowing c from matching. The matcher will retry at the next position to the end of the string, and the same thing happens. So nothing matches the regex at all.

Input string: bbabbbabbbbc
Pattern: /((?>.*)|b*)[ac]/, for testing /(((?>.*))|(b*))[ac]/

There are 3 matches to this regex, which are bba, bbba, bbbbc. If you use the 2nd regex, which is the same but with capturing groups added for debugging purpose, you can see that all the matches are result of matching b* inside.

You can see the backtracking behavior here.

  • Without the atomic grouping /(.*|b*)[ac]/, the string will have a single match which is the whole string, due to backtracking at the end to match [ac]. Note that the engine will go back to .* to backtrack by 1 character since it still have other possibilities.

    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

  • With the atomic grouping, all possibilities of .* is cut off and limited to the first match. So after greedily eating the whole string and fail to match, the engine have to go for the b* pattern, where it successfully finds a match to the regex.

    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

The subsequent matches will continue on from here.

#ruby