The previous recipe explains the difference between greedy and lazy quantifiers, and how they backtrack. In some situations, this backtracking is unnecessary.
‹d+
› uses a
greedy quantifier, and ‹d+?
› uses a lazy quantifier. They both match
the same thing: an integer. Given the same subject text, both will find
the exact same matches. Any backtracking that is done is unnecessary.
Rewrite this regular expression to explicitly eliminate all
backtracking, making the regular expression more efficient.
d++
Regex options: None |
Regex flavors: Java, PCRE, Perl 5.10, Ruby 1.9 |
The easiest solution is to use a possessive quantifier. But it is supported only in a few recent regex flavors.
(?>d+)
Regex options: None |
Regex flavors: .NET, Java, PCRE, Perl, Ruby |
An atomic group provides exactly the same functionality, using a slightly less readable syntax. Support for atomic grouping is more widespread than support for possessive quantifiers.
JavaScript and Python do not support possessive quantifiers or atomic grouping. There is no way to eliminate needless backtracking with these two regex flavors.
A possessive quantifier is similar to a greedy quantifier: it tries to repeat as many times as possible. The difference is that a possessive quantifier will never give back, not even when giving back is the only way that the remainder of the regular expression could match. Possessive quantifiers do not keep backtracking positions.
You can make any quantifier possessive by placing a plus sign
after it. For example, ‹*+
›, ‹++
›,
‹?+
›, and
‹{7,42}+
› are all
possessive quantifiers.
Possessive quantifiers are supported by Java 4 and later, the
first Java release to include the java.util.regex
package. All versions of PCRE discussed in this book (version 4 to 7)
support possessive quantifiers. Perl supports them starting with Perl
5.10. Classic Ruby regular expressions do not support possessive
quantifiers, but the Oniguruma engine, which is the default in Ruby 1.9,
does support them.
Wrapping a greedy quantifier inside an atomic
group has the exact same effect as using a possessive
quantifier. When the regex engine exits the atomic group, all
backtracking positions remembered by quantifiers and alternation inside
the group are thrown away. The syntax is ‹(?>⋯)
›, where ‹⋯
› is
any regular expression. An atomic group is essentially a noncapturing
group, with the extra job of refusing to backtrack. The question mark is
not a quantifier; the opening bracket simply consists of the three
characters ‹(?>
›.
When you apply the regex ‹d++
› (possessive) to 123abc 456
, ‹› matches
at the start of the subject, and ‹
d++
› matches 123
. So far, this is no different from what
‹d+
› (greedy) would do. But then the
second ‹› fails to match
between
3
and
a
.
The possessive quantifier did not store any backtracking
positions. Since there are no other quantifiers or alternation in this
regular expression, there are no further options to try when the second
word boundary fails. The regex engine immediately declares failure for
the match attempt starting at 1
.
The regex engine does attempt the regex starting at the next
character positions in the string, and using a possessive quantifier
does not change that. If the regex must match the whole subject, use
anchors, as discussed in Recipe 2.5.
Eventually, the regex engine will attempt the regex starting at the
4
and find the
match 456
.
The difference with the greedy quantifier is that when the second
‹› fails during the
first match attempt, the greedy quantifier will backtrack. The regex
engine will then (needlessly) test ‹
› between
2
and 3
, and between 1
and 2
.
The matching process using atomic grouping is essentially the
same. When you apply the regex ‹(?>d+)
› (possessive) to 123abc 456
, the word
boundary matches at the start of the subject. The regex engine enters
the atomic group, and ‹d+
› matches 123
. Now the engine exits the atomic group.
At this point, the backtracking positions remembered by ‹d+
› are thrown away. When the
second ‹› fails, the
regex engine is left without any further options, causing the match
attempt to fail immediately. As with the possessive quantifier,
eventually
456
will be found.
We describe the possessive quantifier as failing to remember
backtracking positions, and the atomic group as throwing them away. This
makes it easier to understand the matching process, but don’t get hung
up on the difference, as it may not even exist in the regex flavor
you’re working with. In many flavors, ‹x++
› is merely syntactic sugar for ‹(?>x+)
›, and both are
implemented in exactly the same way. Whether the engine never remembers
backtracking positions or throws them away later is irrelevant for the
final outcome of the match attempt.
Where possessive quantifiers and atomic grouping differ is that a possessive quantifier applies only to a single regular expression token, whereas an atomic group can wrap a whole regular expression.
‹w++d++
› and
‹(?>w+d+)
› are not
the same at all. ‹w++d++
›, which is the same as ‹(?>w+)(?>d+)
›, will not
match abc123
.
‹w++
› matches abc123
entirely. Then, the
regex engine attempts ‹d++
› at the end of the subject text. Since there
are no further characters that can be matched, ‹d++
› fails. Without any remembered backtracking
positions, the match attempt fails.
‹(?>w+d+)
› has
two greedy quantifiers inside the same atomic group. Within the atomic
group, backtracking occurs normally. Backtracking positions are thrown
away only when the engine exits the whole group. When the subject is
abc123
,
‹w+
› matches abc123
. The greedy
quantifier does remember backtracking positions. When ‹d+
› fails to match, ‹w+
› gives up one character.
‹d+
› then matches
3
. Now, the
engine exits the atomic group, throwing away all backtracking positions
remembered for ‹w+
› and
‹d+
›. Since the end of
the regex has been reached, this doesn’t really make any difference. An
overall match is found.
If the end had not been reached, as in ‹(?>w+d+)d+
›, we would be in the same
situation as with ‹w++d++
›. The second ‹d+
› has nothing left to match at the end of the
subject. Since the backtracking positions were thrown away, the regex
engine can only declare failure.
Possessive quantifiers and atomic grouping don’t just optimize regular expressions. They can alter the matches found by a regular expression by eliminating those that would be reached through backtracking.
This recipe shows how to use possessive quantifiers and atomic grouping to make minor optimizations, which may not even show any difference in benchmarks. The next recipe will showcase how atomic grouping can make a dramatic difference.
Recipe 2.12 shows the different alternation operators supported by regular expressions.
Recipe 2.15 explains how to make sure the regex engine doesn’t needlessly try different ways of matching a group.