Greedy vs. Reluctant vs. Possessive Qualifiers

Question

I found this tutorial on regular expressions and while I intuitively understand what "greedy", "reluctant" and "possessive" qualifiers do, there seems to be a serious hole in my understanding.

Specifically, in the following example:

Enter your regex: .*foo // Greedy qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo // Reluctant qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // Possessive qualifier
Enter input string to search: xfooxxxxxxfoo
No match found.

The explanation mentions eating the entire input string, letters been consumed, matcher backing off, rightmost occurrence of "foo" has been regurgitated, etc.

Unfortunately, despite the nice metaphors, I still don't understand what is eaten by whom... Do you know of another tutorial that explains (concisely) how regular expression engines work?

Alternatively, if someone can explain in somewhat different phrasing the following paragraph, that would be much appreciated:

The first example uses the greedy quantifier .* to find "anything", zero or more times, followed by the letters "f", "o", "o". Because the quantifier is greedy, the .* portion of the expression first eats the entire input string. At this point, the overall expression cannot succeed, because the last three letters ("f", "o", "o") have already been consumed [by whom?]. So the matcher slowly backs off [from right-to-left?] one letter at a time until the rightmost occurrence of "foo" has been regurgitated [what does this mean?], at which point the match succeeds and the search ends.

The second example, however, is reluctant, so it starts by first consuming [by whom?] "nothing". Because "foo" doesn't appear at the beginning of the string, it's forced to swallow [who swallows?] the first letter (an "x"), which triggers the first match at 0 and 4. Our test harness continues the process until the input string is exhausted. It finds another match at 4 and 13.

The third example fails to find a match because the quantifier is possessive. In this case, the entire input string is consumed by .*+ [how?], leaving nothing left over to satisfy the "foo" at the end of the expression. Use a possessive quantifier for situations where you want to seize all of something without ever backing off [what does back off mean?]; it will outperform the equivalent greedy quantifier in cases where the match is not immediately found.

Mundford

Maximal quantifiers like *, +, and ? are greedy. Minimal quantifiers like *?, +?, and ?? are lazy. Possessive quantifiers like *+, ++, and ?+ are sticky. – Beating

This question has been added to the Stack Overflow Regular Expression FAQ, under "Quantifiers > More on the differences...". – Chrysolite

Of interest: The Java™ Tutorials - Differences Among Greedy, Reluctant, and Possessive Quantifiers - Scroll down to see section. – Pains

I actually find the terminology and explanations pretty awful in that resource. – Tops

Answer 1

I'll give it a shot.

A greedy quantifier first matches as much as possible. So the .* matches the entire string. Then the matcher tries to match the f following, but there are no characters left. So it "backtracks", making the greedy quantifier match one less character (leaving the "o" at the end of the string unmatched). That still doesn't match the f in the regex, so it backtracks one more step, making the greedy quantifier match one less character again (leaving the "oo" at the end of the string unmatched). That still doesn't match the f in the regex, so it backtracks one more step (leaving the "foo" at the end of the string unmatched). Now, the matcher finally matches the f in the regex, and the o and the next o are matched too. Success!

A reluctant or "non-greedy" quantifier first matches as little as possible. So the .* matches nothing at first, leaving the entire string unmatched. Then the matcher tries to match the f following, but the unmatched portion of the string starts with "x" so that doesn't work. So the matcher backtracks, making the non-greedy quantifier match one more character (now it matches the "x", leaving "fooxxxxxxfoo" unmatched). Then it tries to match the f, which succeeds, and the o and the next o in the regex match too. Success!

In your example, it then starts the process over with the remaining unmatched portion of the string, "xxxxxxfoo", following the same process.

A possessive quantifier is just like the greedy quantifier, but it doesn't backtrack. So it starts out with .* matching the entire string, leaving nothing unmatched. Then there is nothing left for it to match with the f in the regex. Since the possessive quantifier doesn't backtrack, the match fails there.

Fogle

+1 Good answer. I would only add: Go read Mastering Regular Expressions (3rd Edition) – Upton

@Fogle a little bit late but, in the possessive part, I think you meant So it starts out with .*+ (notice the "+") – Beet

And because of possessive quantifier doesn't backtrack - it much faster than greedy and lazy quantifiers! – Lobation

what exactly does the possessive quantifier do then? if it doesn't match this? (I mean what is the point of it, if you cannot have characters after it) – Ringlet

@relipse: You'd use it in a situation where you know that backtracking won't help, probably not with .*+ that matches everything. For example, if you have a pattern [xyz]*foo, there's no way that backtracking the x's, y's, and z's matched by the [xyz]* bit will ever allow the following foo bit to match, so you can speed things up by making it possessive. – Fogle

Still, I would imagine that actual use cases for possessive searching are pretty rare? – Lydialydian

@moodboom, there are zero cases ever (mathematical fact) where possessive quantifiers will produce a match that will not be produced by simple greedy quantifiers. There are occasional cases where they will produce a no match when greedy quantifiers would produce a match. For ALL other cases (where greedy and possessive produce the same results), possessive quantifiers give a performance gain. – Jemison

A very good and crisp explanation, you should be a teacher, if you have a Youtube channel please let me know. – Devoid

Does that mean that .*+ cannot be used because it will never match anything after it? – Clayclaybank

Answer 2

It is just my practice output to visualise the scene-

Selsyn

Except I think the last case, possessive, shouldn't have n passes -- just grab the entire string at once. – Ilse

@phyzome I think it is ok now? – Selsyn

In EXPRESSION .*?foo (), should't the [f] [o] [o] rectangles be yellow in the 5th pass? – News

@News yes! Yellow coloring needs to be done for matched part in expression .*?foo and .*+foo. – Selsyn

Great visual thanks! I renforced my knowledge about the the lazy and gready quantifiers. And I had no idea about the possessive quantifier. So it help too ;) – Hampstead

Answer 3

I haven't heard the exact terms 'regurgitate' or 'backing off' before; the phrase that would replace these is "backtracking", but 'regurgitate' seems like as good a phrase as any for "the content that had been tentatively accepted before backtracking threw it away again".

The important thing to realize about most regex engines is that they are backtracking: they will tentatively accept a potential, partial match, while trying to match the entire contents of the regex. If the regex cannot be completely matched at the first attempt, then the regex engine will backtrack on one of its matches. It will try matching *, +, ?, alternation, or {n,m} repetition differently, and try again. (And yes, this process can take a long time.)

The first example uses the greedy quantifier .* to find "anything", zero or more times, followed by the letters "f" "o" "o". Because the quantifier is greedy, the .* portion of the expression first eats the entire input string. At this point, the overall expression cannot succeed, because the last three letters ("f" "o" "o") have already been consumed (by whom?).

The last three letters, f, o, and o were already consumed by the initial .* portion of the rule. However, the next element in the regex, f, has nothing left in the input string. The engine will be forced to backtrack on its initial .* match, and try matching all-but-the-last character. (It might be smart and backtrack to all-but-the-last-three, because it has three literal terms, but I'm unaware of implementation details at this level.)

So the matcher slowly backs off (from right-to-left?) one letter at a time until the rightmost occurrence of "foo" has been regurgitated (what does this mean?), at which

This means the foo had tentatively been including when matching .*. Because that attempt failed, the regex engine tries accepting one fewer character in .*. If there had been a successful match before the .* in this example, then the engine would probably try shortening the .* match (from right-to-left, as you pointed out, because it is a greedy qualifier), and if it was unable to match the entire inputs, then it might be forced to re-evaluate what it had matched before the .* in my hypothetical example.

point the match succeeds and the search ends.

The second example, however, is reluctant, so it starts by first consuming (by whom?) "nothing". Because "foo"

The initial nothing is consumed by .?*, which will consume the shortest possible amount of anything that allows the rest of the regex to match.

doesn't appear at the beginning of the string, it's forced to swallow (who swallows?) the

Again the .?* consumes the first character, after backtracking on the initial failure to match the entire regex with the shortest possible match. (In this case, the regex engine is extending the match for .*? from left-to-right, because .*? is reluctant.)

first letter (an "x"), which triggers the first match at 0 and 4. Our test harness continues the process until the input string is exhausted. It finds another match at 4 and 13.

The third example fails to find a match because the quantifier is possessive. In this case, the entire input string is consumed by .*+, (how?)

A .*+ will consume as much as possible, and will not backtrack to find new matches when the regex as a whole fails to find a match. Because the possessive form does not perform backtracking, you probably won't see many uses with .*+, but rather with character classes or similar restrictions: account: [[:digit:]]*+ phone: [[:digit:]]*+.

This can drastically speed up regex matching, because you're telling the regex engine that it should never backtrack over potential matches if an input doesn't match. (If you had to write all the matching code by hand, this would be similar to never using putc(3) to 'push back' an input character. It would be very similar to the naive code one might write on a first try. Except regex engines are way better than a single character of push-back, they can rewind all the back to zero and try again. :)

But more than potential speed ups, this also can let you write regexs that match exactly what you need to match. I'm having trouble coming up with an easy example :) but writing a regex using possessive vs greedy quantifiers can give you different matches, and one or the other may be more appropriate.

leaving nothing left over to satisfy the "foo" at the end of the expression. Use a possessive quantifier for situations where you want to seize all of something without ever backing off (what does back off mean?); it will outperform

"Backing off" in this context means "backtracking" -- throwing away a tentative partial match to try another partial match, which may or may not succeed.

the equivalent greedy quantifier in cases where the match is not immediately found.

Khaki

I suspect that there is never a case where a possessive quantifier will match something that a greedy quantifier will not. I believe that the following proves it: A greedy quantifier always matches as much as possible, then backtracks if it can't find a match. A possessive quantifier matches as much as possible, then quits if it can't find a match. So there may be something that a greedy quantifier matches that a possessive quantifier won't, but not the reverse, because they both search the "tree" in the same sequence, the possessive quantifier just gives up more easily. ;) – Jemison

Confirmed: "That is what atomic grouping and possessive quantifiers are for: efficiency by disallowing backtracking." from regular-expressions.info So the statement in this answer "But more than potential speed ups, this also can let you write regexs that match exactly what you need to match." is actually not quite accurate. – Jemison

@Wildcard, thanks for the comments; that may explain why I had trouble coming up with an example. Hehe. – Khaki

Answer 4

http://swtch.com/~rsc/regexp/regexp1.html

I'm not sure that's the best explanation on the internet, but it's reasonably well written and appropriately detailed, and I keep coming back to it. You might want to check it out.

If you want a higher-level (less detailed explanation), for simple regular expressions such as the one you're looking at, a regular expression engine works by backtracking. Essentially, it chooses ("eats") a section of the string and tries to match the regular expression against that section. If it matches, great. If not, the engine alters its choice of the section of the string and tries to match the regexp against that section, and so on, until it's tried every possible choice.

This process is used recursively: in its attempt to match a string with a given regular expression, the engine will split the regular expression into pieces and apply the algorithm to each piece individually.

The difference between greedy, reluctant, and possessive quantifiers enters when the engine is making its choices of what part of the string to try to match against, and how to modify that choice if it doesn't work the first time. The rules are as follows:

• A greedy quantifier tells the engine to start with the entire string (or at least, all of it that hasn't already been matched by previous parts of the regular expression) and check whether it matches the regexp. If so, great; the engine can continue with the rest of the regexp. If not, it tries again, but trimming one character (the last one) off the section of the string to be checked. If that doesn't work, it trims off another character, etc. So a greedy quantifier checks possible matches in order from longest to shortest.

• A reluctant quantifier tells the engine to start with the shortest possible piece of the string. If it matches, the engine can continue; if not, it adds one character to the section of the string being checked and tries that, and so on until it finds a match or the entire string has been used up. So a reluctant quantifier checks possible matches in order from shortest to longest.

• A possessive quantifier is like a greedy quantifier on the first attempt: it tells the engine to start by checking the entire string. The difference is that if it doesn't work, the possessive quantifier reports that the match failed right then and there. The engine doesn't change the section of the string being looked at, and it doesn't make any more attempts.

This is why the possessive quantifier match fails in your example: the .*+ gets checked against the entire string, which it matches, but then the engine goes on to look for additional characters foo after that - but of course it doesn't find them, because you're already at the end of the string. If it were a greedy quantifier, it would backtrack and try making the .* only match up to the next-to-last character, then up to the third to last character, then up to the fourth to last character, which succeeds because only then is there a foo left after the .* has "eaten" the earlier part of the string.

Obit

@Regex Rookie: glad you like it :) After looking over that site, though, I think I should make clear that its purpose is to promote an alternate implementation of a regular expression engine. The backtracking algorithm I (partially) and other answers describe is the slow way; it's a completely separate algorithm from the NFA/DFA idea described in the web page. Backtracking is just easier to understand, which is why that's how regexps are typically explained to beginners. – Obit

@David Zaslavsky: Good explanation. Your comments in brackets in "A greedy quantifier tells the engine to start with the entire string (or at least, all of it that hasn't already been matched by previous parts of the regular expression)" are important. They apply also to reluctant and possessive quantifiers. This makes your explanation compatible with what happens when we change our example patterns from (".*foo"; ".*?foo"; and ".*+foo") to ("foo.*"; "foo.*?"; and "foo.*+"). – Highstepper

Actually, xfooxxxxxxfoo does match .*foo in normal (computer science meaning) of regular expression. The NFA would be a a state where it loops among itself with any character and then it can jump to foo. The DFA would be a straightforward translation of that NFA. It can be done in 8 states. – Strontium

@JimThio yeah, because that's not a possessive quantifier. – Obit

Answer 5

Here is my take using Cell and Index positions (See the diagram here to distinguish a Cell from an Index).

Greedy - Match as much as possible to the greedy quantifier and the entire regex. If there is no match, backtrack on the greedy quantifier.

Input String: xfooxxxxxxfoo
Regex: .*foo

The above Regex has two parts:
(i)'.*' and
(ii)'foo'

Each of the steps below will analyze the two parts. Additional comments for a match to 'Pass' or 'Fail' is explained within braces.

Step 1:
(i) .* = xfooxxxxxxfoo - PASS ('.*' is a greedy quantifier and will use the entire Input String)
(ii) foo = No character left to match after index 13 - FAIL
Match failed.

Step 2:
(i) .* = xfooxxxxxxfo - PASS (Backtracking on the greedy quantifier '.*')
(ii) foo = o - FAIL
Match failed.

Step 3:
(i) .* = xfooxxxxxxf - PASS (Backtracking on the greedy quantifier '.*')
(ii) foo = oo - FAIL
Match failed.

Step 4:
(i) .* = xfooxxxxxx - PASS (Backtracking on the greedy quantifier '.*')
(ii) foo = foo - PASS
Report MATCH

Result: 1 match(es)
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Reluctant - Match as little as possible to the reluctant quantifier and match the entire regex. if there is no match, add characters to the reluctant quantifier.

Input String: xfooxxxxxxfoo
Regex: .*?foo

The above regex has two parts:
(i) '.*?' and
(ii) 'foo'

Step 1:
.*? = '' (blank) - PASS (Match as little as possible to the reluctant quantifier '.*?'. Index 0 having '' is a match.)
foo = xfo - FAIL (Cell 0,1,2 - i.e index between 0 and 3)
Match failed.

Step 2:
.*? = x - PASS (Add characters to the reluctant quantifier '.*?'. Cell 0 having 'x' is a match.)
foo = foo - PASS
Report MATCH

Step 3:
.*? = '' (blank) - PASS (Match as little as possible to the reluctant quantifier '.*?'. Index 4 having '' is a match.)
foo = xxx - FAIL (Cell 4,5,6 - i.e index between 4 and 7)
Match failed.

Step 4:
.*? = x - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4.)
foo = xxx - FAIL (Cell 5,6,7 - i.e index between 5 and 8)
Match failed.

Step 5:
.*? = xx - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4 thru 5.)
foo = xxx - FAIL (Cell 6,7,8 - i.e index between 6 and 9)
Match failed.

Step 6:
.*? = xxx - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4 thru 6.)
foo = xxx - FAIL (Cell 7,8,9 - i.e index between 7 and 10)
Match failed.

Step 7:
.*? = xxxx - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4 thru 7.)
foo = xxf - FAIL (Cell 8,9,10 - i.e index between 8 and 11)
Match failed.

Step 8:
.*? = xxxxx - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4 thru 8.)
foo = xfo - FAIL (Cell 9,10,11 - i.e index between 9 and 12)
Match failed.

Step 9:
.*? = xxxxxx - PASS (Add characters to the reluctant quantifier '.*?'. Cell 4 thru 9.)
foo = foo - PASS (Cell 10,11,12 - i.e index between 10 and 13)
Report MATCH

Step 10:
.*? = '' (blank) - PASS (Match as little as possible to the reluctant quantifier '.*?'. Index 13 is blank.)
foo = No character left to match - FAIL (There is nothing after index 13 to match)
Match failed.

Result: 2 match(es)
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Possessive - Match as much as possible to the possessive quantifer and match the entire regex. Do NOT backtrack.

Input String: xfooxxxxxxfoo
Regex: .*+foo

The above regex has two parts: '.*+' and 'foo'.

Step 1:
.*+ = xfooxxxxxxfoo - PASS (Match as much as possible to the possessive quantifier '.*')
foo = No character left to match - FAIL (Nothing to match after index 13)
Match failed.

Note: Backtracking is not allowed.

Result: 0 match(es)

Ensoll

Answer 6

Greedy: "match the longest possible sequence of characters"

Reluctant: "match the shortest possible sequence of characters"

Possessive: This is a bit strange as it does NOT (in contrast to greedy and reluctant) try to find a match for the whole regex.

By the way: No regex pattern matcher implementation will ever use backtracking. All real-life pattern matcher are extremely fast - nearly independent of the complexity of the regular expression!

Schulz

As far as I know most general-use implementations now are packed so full of features it became impossible not to use backtracking. So in theory they should be extremely (exponentially) slow for some cases. But for most of those cases there are special optimizations built into the pattern matcher. – Terminus

Backtracking is real and it's not too hard to write examples that end up backtracking when you wish they didn't. blog.cloudflare.com/… is a nice real-life example. Using possessive quantifiers can be a good way to avoid backtracking. – Synsepalous

Answer 7

Greedy Quantification involves pattern matching using all of the remaining unvalidated characters of a string during an iteration. Unvalidated characters start in the active sequence. Every time a match does not occur, the character at the end is quarantined and the check is performed again.

When only leading conditions of the regex pattern are satisfied by the active sequence, an attempt is made to validate the remaining conditions against the quarantine. If this validation is successful, matched characters in the quarantine are validated and residual unmatched characters remain unvalidated and will be used when the process begins anew in the next iteration.

The flow of characters is from the active sequence into the quarantine. The resulting behavior is that as much of the original sequence is included in a match as possible.

Reluctant Quantification is mostly the same as greedy qualification except the flow of characters is the opposite--that is, they start in the quarantine and flow into the active sequence. The resulting behavior is that as little of the original sequence is included in a match as possible.

Possessive Quantification does not have a quarantine and includes everything in a fixed active sequence.

Gdynia

Reading this again a number of years later and some of these terms (like "active sequence" and "quarantined") were my best guess at the time and not official. Literal meanings might help explain the attempt at a terse explanation. – Gdynia