Greedy and Non-Greedy Matching

Part II · Module 19 · Chapter 19.13 · Greedy and Non-Greedy Matching

1. The Field That Swallowed the Line

A UVM error message with three bracketed fields, and a pattern that asks for the first one:

import re

LINE = "UVM_ERROR [DRV] write to [0x40001000] returned [0xdeadbeef]"

m = re.search(r"\[(.*)\]", LINE)
print("group(1):", m.group(1))
print("group(0):", m.group(0))

group(1): DRV] write to [0x40001000] returned [0xdeadbeef
group(0): [DRV] write to [0x40001000] returned [0xdeadbeef]

The pattern says an open bracket, then anything, then a close bracket, and that is exactly what it did — it found the first [, the last ], and called everything between them "anything". The message id, the address and the data all arrived in one string, with two stray brackets in the middle.

This is not a bug in re and it is not an edge case. It is the default behaviour of every quantifier in the module so far: *, +, ? and {m,n} are greedy, which means each one takes as many characters as it can while still allowing the rest of the pattern to match.

The same defect with findall is worse, because it hides the shape of the loss:

import re

LINE = "UVM_ERROR [DRV] write to [0x40001000] returned [0xdeadbeef]"

print("greedy:", re.findall(r"\[(.*)\]", LINE))

greedy: ['DRV] write to [0x40001000] returned [0xdeadbeef']

One result where a reader expects three. The match consumed the whole region, so there is nothing left for a second match to find — and a script counting len(...) to count fields now reports 1.

2. What Greedy Actually Does

The mechanism is worth having, because it explains both the default and the fix.

When the engine reaches .*, it takes everything to the end of the string first. Then it tries to match the rest of the pattern — here, a ] — and fails, because it is at the end and there is nothing left. So it gives one character back and tries again. Still no ]. Gives another back. It keeps doing this, one character at a time, until the character it is now looking at is a ] — and the last ] in the line is the first one it meets coming backwards.

That reverse walk is called backtracking, and two things follow from it:

• Greedy quantifiers find the rightmost possible end for the thing after them.
• A greedy quantifier is not "wrong" — it matched exactly what the pattern described. .* means any characters, and ] is a character.

The pattern was underspecified. . matches anything except a newline, which includes the two ] characters the author assumed it would stop at.

3. Adding ?: Try the Shortest First

Put a ? after any quantifier and it becomes non-greedy, usually called lazy:

import re

LINE = "UVM_ERROR [DRV] write to [0x40001000] returned [0xdeadbeef]"

print("greedy:", re.search(r"\[(.*)\]", LINE).group(1))
print("lazy  :", re.search(r"\[(.*?)\]", LINE).group(1))
print("all   :", re.findall(r"\[(.*?)\]", LINE))

greedy: DRV] write to [0x40001000] returned [0xdeadbeef
lazy  : DRV
all   : ['DRV', '0x40001000', '0xdeadbeef']

.*? takes nothing first, then tries the rest of the pattern, and grows by one character only when that fails. The first ] it reaches is the first one in the line, so the group is DRV — and findall now returns the three fields the line actually has.

Every quantifier has a lazy twin:

import re

S = "aaa"

print("a+   ->", repr(re.match(r"a+", S).group(0)))
print("a+?  ->", repr(re.match(r"a+?", S).group(0)))
print("a*   ->", repr(re.match(r"a*", S).group(0)))
print("a*?  ->", repr(re.match(r"a*?", S).group(0)))
print("a??  ->", repr(re.match(r"a??", S).group(0)))
print("a{2,3}  ->", repr(re.match(r"a{2,3}", S).group(0)))
print("a{2,3}? ->", repr(re.match(r"a{2,3}?", S).group(0)))

a+   -> 'aaa'
a+?  -> 'a'
a*   -> 'aaa'
a*?  -> ''
a??  -> ''
a{2,3}  -> 'aaa'
a{2,3}? -> 'aa'

Note a*? and a?? matching the empty string, which is Chapter 19.6's warning about * arriving from a new direction: a lazy * with nothing after it to force it forward will happily match nothing and report success. And a{2,3}? takes two, the minimum its own bound allows — lazy respects the bounds, it just starts at the bottom of the range instead of the top.

So the two-line summary, and the canonical annotation:

re.search(r"\[(.*)\]", line)     # greedy — runs to the last ]
re.search(r"\[(.*?)\]", line)    # stops at the first ]

4. Lazy Does Not Mean Shortest

This is the section that stops the second surprise. The usual mental model — ? gives me the short match — is wrong, and here is the line of output that proves it:

import re

TAG = "[WR] expected [0xdead] got [0xbeef]"

print("lazy          :", re.search(r"\[(.*?)\]", TAG).group(1))
print("lazy, anchored:", re.search(r"\[(.*?)\]$", TAG).group(1))

lazy          : WR
lazy, anchored: WR] expected [0xdead] got [0xbeef

Same lazy quantifier. One $ added, and it captured the entire span — precisely what the greedy version would have done.

A lazy quantifier does not want the shortest match. It wants the shortest match that lets the rest of the pattern succeed, and it will expand as far as necessary to get there. With $ in the pattern, the ] has to be the last character of the subject, so .*? is forced forward past two closing brackets until the only remaining ] is the final one.

The correct way to hold it:

• Greedy — take everything, then give back as little as possible.
• Lazy — take nothing, then take as little more as necessary.

Both are driven by what the rest of the pattern requires. Neither is a promise about length. A lazy quantifier whose follower is easy to satisfy stops early; one whose follower is hard to satisfy runs just as far as a greedy one.

5. The Better Fix: Describe the Field

There is a third option, and in a flow script it is usually the right one. Instead of saying any characters, but not too many, say what the field is made of:

import re

TAG = "[WR] expected [0xdead] got [0xbeef]"

print("lazy     :", re.findall(r"\[(.*?)\]", TAG))
print("negated  :", re.findall(r"\[([^\]]*)\]", TAG))

lazy     : ['WR', '0xdead', '0xbeef']
negated  : ['WR', '0xdead', '0xbeef']

Identical here — and not identical where it counts:

import re

TAG = "[WR] expected [0xdead] got [0xbeef]"

print("lazy, anchored   :", re.search(r"\[(.*?)\]$", TAG).group(1))
print("negated, anchored:", re.search(r"\[([^\]]*)\]$", TAG).group(1))

lazy, anchored   : WR] expected [0xdead] got [0xbeef
negated, anchored: 0xbeef

[^\]]* is Chapter 19.5's negated class: any characters that are not a closing bracket. It cannot overshoot, because a ] is not a character it is allowed to match — so no amount of pressure from the rest of the pattern can make it cross one. The anchored version finds the last bracketed field, which is what an anchored pattern should mean.

That is the general principle, and it is worth more than the two quantifier forms put together:

A lazy quantifier says stop somewhere early. A negated class says this field does not contain that character. The second is a fact about your data, and facts survive edits to the rest of the pattern.

This is also why Chapter 19.12's finished pattern contains no . at all. \d+, (?:\.\d+)? and (?:VIOLATED|MET) each describe what is there, so there is nothing for a quantifier to overshoot and nothing to rein back in.

6. Both Are Correct — They Answer Different Questions

Greedy is not the broken one. On a hierarchical instance path, the two forms give two different, equally useful splits:

import re

PATH = "uvm_test_top.env.agt.drv"

print("greedy:", re.search(r"^(.*)\.(\w+)$", PATH).groups())
print("lazy  :", re.search(r"^(.*?)\.(.*)$", PATH).groups())

greedy: ('uvm_test_top.env.agt', 'drv')
lazy  : ('uvm_test_top', 'env.agt.drv')

The greedy split takes the last dot: parent scope and leaf component, which is what you want to report which component raised an error. The lazy split takes the first dot: the root and everything below it, which is what you want to group every message by testbench top.

Same data, same two constructs, two different questions. Neither pattern is a mistake.

The same pair on a delimited row:

import re

ROW = "smoke_rw,1839274,PASS"

print("greedy:", re.search(r"^(.*),(.*)$", ROW).groups())
print("lazy  :", re.search(r"^(.*?),(.*)$", ROW).groups())

greedy: ('smoke_rw,1839274', 'PASS')
lazy  : ('smoke_rw', '1839274,PASS')

Greedy gives you everything except the last field; lazy gives you the first field and the rest. Both are legitimate; both are also a sign you should be using str.split or the csv module, which is exactly the argument Chapter 19.19 makes.

And one case where greedy is simply the answer:

import re

LINE = "UVM_ERROR drv.sv(88) @ 12500: uvm_test_top.env.agt.drv [WR] expected 0xdead, got 0xbeef"

print("message:", re.search(r": (.*)$", LINE).group(1))

message: uvm_test_top.env.agt.drv [WR] expected 0xdead, got 0xbeef

Everything after the first colon-space, to the end of the line is a genuine requirement — a message body contains anything, including colons and brackets, and there is no class that describes it. Greedy .* with $ is correct, and a lazy .*? here would give the identical answer for the reason Section 4 explained, which makes the ? pure noise.

7. Predict, Run, Observe

import re

LINE = "[A] mid [B] end [C]"

# A
print("A:", re.search(r"\[(.*)\]", LINE).group(1))

# B
print("B:", re.search(r"\[(.*?)\]", LINE).group(1))

# C
print("C:", re.findall(r"\[(.+?)\]", LINE))

# D
print("D:", re.search(r"\[(.*?)\]$", LINE).group(1))

# E
print("E:", re.search(r"\[([^\]]*)\]$", LINE).group(1))

# F
print("F:", repr(re.match(r"\w*?", "abc").group(0)))

# G
print("G:", re.search(r"^(.*?)\s", LINE).group(1))

The verified output:

A: A] mid [B] end [C
B: A
C: ['A', 'B', 'C']
D: A] mid [B] end [C
E: C
F: ''
G: [A]

A — greedy runs to the last ]. Section 1.

B — lazy stops at the first. Section 3.

C — +? rather than *?, so each field must be non-empty; all three are found.

D — the anchor forces the lazy quantifier all the way forward, and D equals A. Section 4, which is the one to get right.

E — the negated class cannot cross a ], so the anchored pattern finds the last field. Section 5.

F — a lazy * with nothing after it to force it forward matches the empty string and succeeds.

G — lazy up to the first whitespace, which is the first bracketed field including its brackets, because the pattern never asked for them to be stripped.

8. Exercises

Exercise 1 — reproduce the swallow. Take a line with three bracketed fields and extract the first with \[(.*)\]. Print group(0) and group(1) and say which characters the quantifier took that you did not want.

Exercise 2 — count the loss. Run findall with the greedy pattern and with the lazy one on the same line. Report both lengths and explain the greedy count in one sentence.

Exercise 3 — the reverse walk. In your own words, describe what the engine does between taking the whole line and returning the last ]. Use the word backtracking once.

Exercise 4 — every lazy twin. Build Section 3's seven-row table for a subject of your own. Say which two rows match the empty string and why.

Exercise 5 — the anchored surprise. Take your lazy pattern from Exercise 2, add $, and record what the group becomes. Then write the one-sentence rule that explains it without using the word shortest.

Exercise 6 — the negated class. Fix Exercise 5 with a negated class instead of a quantifier change. Confirm the anchored version now returns the last field.

Exercise 7 — which of the three. For each, choose a class, a lazy quantifier or greedy, and justify it: (a) a hex value inside brackets; (b) everything between Startpoint: and Endpoint: on one line; (c) the whole message body after a colon; (d) a key=value pair where the value may contain =.

Exercise 8 — two correct splits. Split a four-level instance path at the last dot and at the first dot. Name a report that wants each one.

Exercise 9 — the pointless ?. Find a pattern in which .*? and .* give identical results, and explain why the ? changes nothing there.

Exercise 10 — audit a pattern. Take Chapter 19.12's finished slack pattern and say why it contains no . at all, and what you would have to add if \d were replaced by ..

9. Summary

• Every quantifier is greedy by default — *, +, ? and {m,n} take as much as they can while still letting the rest of the pattern match.
• \[(.*)\] runs to the last ] and returns every field in between as one string, with no error.
• With findall the symptom is a count, because one oversized match leaves nothing for a second.
• Greedy works by backtracking — take everything, then give characters back one at a time until the follower matches, which finds the rightmost end.
• . matches anything except a newline, which is the only thing keeping a greedy .* inside one line.
• A ? after a quantifier makes it lazy — take nothing, then grow by one only when the rest fails.
• Every quantifier has a lazy twin, and *? and ?? can match the empty string.
• Lazy does not mean shortest. It means the shortest that lets the rest of the pattern succeed — and \[(.*?)\]$ consumes exactly as much as the greedy version.
• A lazy quantifier returning too much is a sign of a hard follower, usually an anchor. Another ? will not help.
• Prefer a class that describes the field. [^\]]* cannot cross a ] at all, so it is immune to pressure from the rest of the pattern.
• Three options in order: a class or literal first, a lazy quantifier when no class can express the terminator, greedy when you genuinely want everything to the last occurrence.
• Greedy and lazy are both correct on an instance path — one splits at the last dot and one at the first, and they answer different questions.
• Chapter 19.12's pattern has no . in it, which is why neither form of this problem can arise there.

The next chapter covers the three flags that change what a pattern means — including the one that removes the newline limit on . and makes everything in this chapter apply to a whole file at once.