Ruby Regex – Differences Between Lazy, Greedy, and Possessive Quantifiers

regexrubyruby-1.9.3

How do the following quantifiers differ – with respect of scenarios, speed, etc.

?, ?? and ?+ all match 0 or 1 times.
*, *? and*+` all match 0 or more times.
+, +? and ++ all match 1 or more times.

?, * and + are greedy.
??, *? and +? are reluctant/lazy.
?+, *+ and ++ are possessive.

Can anyone help me to understand what these terms mean? Why are there three variations of each quantifier for the same job?

Best Answer

Take the string

aaaab

and see how the following regexes match it:

Regex          Submatches
               group 1  group 2  group3
(a?)(a*)(ab)   a        aa       ab
(a??)(a*)(ab)           aaa      ab
(a?+)(a*)(ab)  a        aa       ab
(a*)(a?)(ab)   aaa               ab
(a*?)(a?)(ab)  aa       a        ab
(a*+)(a?)(ab)  aaaa              <Match fails!>
(a+)(a*)(ab)   aaa               ab 
(a+?)(a*)(ab)  a        aa       ab
(a++)(a*)(ab)  aaaa              <Match fails!>

Explanation:

a? tries to match one a, but it's prepared to match nothing if that's necessary for the whole match to succeed.
a?? tries to match nothing, but it's prepared to match one a if that's necessary for the whole match to succeed.
a?+ tries to match one a. If it can do that, it will not back down to match nothing if that were necessary for the overall match to succeed. If it can't match an a, then it will gladly match nothing, though.
a* tries to match as many as as it can, but it's prepared to match fewer as, even nothing if that's necessary for the whole match to succeed.
a*? tries to match nothing, but it's prepared to match just as many as as is absolutely necessary in order for the whole match to succeed, but not more.
a*+ tries to match as many as as it can. If it can do that, it will not back down to match fewer as if that were necessary for the overall match to succeed. If it can't match even a single a, then it will gladly match nothing, though.
a+ tries to match as many as as it can, but it's prepared to match fewer as (but at least one) if that's necessary for the whole match to succeed.
a+? tries to match only one a, but it's prepared to match just as many as as is absolutely necessary in order for the whole match to succeed, but not more.
a++ tries to match as many as as it can. If it can do that, it will not back down to match fewer as if that were necessary for the overall match to succeed. If it can't match even a single a, then the regex fails.

Related Solutions

Regex Lazy vs Greedy – Is Lazy Worse?

Another thing to consider is how long the target text is, and how much of it is going to be matched by the quantified subexpression. For example, if you were trying to match the whole <BODY> element in a large HTML document, you might be tempted to use this regex:

/<BODY>.*?<\/BODY>/is

But that's going to do a whole lot of unnecessary work, matching one character at a time while effectively doing a negative lookahead before each one. You know the </BODY> tag is going to be very near the end of the document, so the smart thing to do is to use a normal greedy quantitier; let it slurp up the whole rest of the document and then backtrack the few characters necessary to match the end tag.

In most cases you won't notice any speed difference between greedy and reluctant quantifiers, but it's something to keep in mind. The main reason why you should be judicious in your use of reluctant quantifiers is the one that was pointed out by the others: they may do it reluctantly, but they will match more than you want them to if that's what it takes to achieve an overall match.

Regex – Explanation of Possessive Quantifiers

Perhaps the best place to start is Regex Tutorial - Possessive Quantifiers:

When discussing the repetition operators or quantifiers, I explained the difference between greedy and lazy repetition. Greediness and laziness determine the order in which the regex engine tries the possible permutations of the regex pattern. A greedy quantifier will first try to repeat the token as many times as possible, and gradually give up matches as the engine backtracks to find an overall match. A lazy quantifier will first repeat the token as few times as required, and gradually expand the match as the engine backtracks through the regex to find an overall match.

Possessive quantifiers are a way to prevent the regex engine from trying all permutations. This is primarily useful for performance reasons. You can also use possessive quantifiers to eliminate certain matches.

Best Answer

Related Solutions

Regex Lazy vs Greedy – Is Lazy Worse?

Regex – Explanation of Possessive Quantifiers

Related Question