Greedy vs Non-Greedy

Part I · Module 11 · Chapter 11.7 · Greedy vs Non-Greedy

1. One Line, Two Fields, One Answer

A constraint file line with two bracketed groups is the shortest honest demonstration.

use strict;
use warnings;

my $line = "set_load 0.4 [get_pins u_alu/A] [get_pins u_fifo/B]";

my ($greedy)  = $line =~ /\[(.*)\]/;
my ($lazy)    = $line =~ /\[(.*?)\]/;

printf "subject    : %s\n", $line;
printf "greedy  .* : [%s]\n", $greedy;
printf "lazy    .*?: [%s]\n", $lazy;

subject    : set_load 0.4 [get_pins u_alu/A] [get_pins u_fifo/B]
greedy  .* : [get_pins u_alu/A] [get_pins u_fifo/B]
lazy    .*?: [get_pins u_alu/A]

The pattern \[(.*)\] reads as "an opening bracket, then anything, then a closing bracket", which sounds like a description of one bracketed group. It returned the contents of the first group, the closing bracket, the space, the opening bracket, and the contents of the second group.

The capture itself contains ] and [. That is the tell: if a captured field contains the delimiter you were using to end it, a greedy quantifier ran past where you meant it to stop.

Adding one ? after the * gives the field you wanted. A ? placed immediately after a quantifier does not mean "optional" — it means "prefer fewer". Chapter 11.6's ? was a quantifier in its own right; this one is a modifier on the quantifier before it. The same applies to +?, ?? and {2,4}?.

2. The Wrong Count, Not Just the Wrong String

A wrong string is visible. A wrong count hides in a summary line.

use strict;
use warnings;

my $line = "set_load 0.4 [get_pins u_alu/A] [get_pins u_fifo/B]";

my @greedy = $line =~ /\[(.*)\]/g;
my @lazy   = $line =~ /\[(.*?)\]/g;

printf "greedy  : %d match(es)\n", scalar @greedy;
printf "          %s\n", join(" || ", @greedy);
printf "lazy    : %d match(es)\n", scalar @lazy;
printf "          %s\n", join(" || ", @lazy);

greedy  : 1 match(es)
          get_pins u_alu/A] [get_pins u_fifo/B
lazy    : 2 match(es)
          get_pins u_alu/A || get_pins u_fifo/B

Two bracketed groups on the line. The lazy pattern found two; the greedy pattern found one.

This is the version of the bug that reaches production. The /g modifier — Chapter 11.12's subject — scans for every match, and a greedy quantifier consumed the territory where the second match lived, so there was nothing left to find. A script reporting "1 constraint found" on a line with two is not obviously broken; it is a plausible number, and it is wrong in the direction that loses data.

The general principle: a greedy quantifier between two delimiters does not just capture too much, it suppresses the matches that would have followed.

3. The Classic Case

The same shape appears whenever the delimiters are markup.

use strict;
use warnings;

my $s = "<inst>u_alu</inst><inst>u_fifo</inst>";

my ($greedy) = $s =~ m{<inst>(.*)</inst>};
my ($lazy)   = $s =~ m{<inst>(.*?)</inst>};

printf "subject : %s\n", $s;
printf "greedy  : %s\n", $greedy;
printf "lazy    : %s\n", $lazy;

subject : <inst>u_alu</inst><inst>u_fifo</inst>
greedy  : u_alu</inst><inst>u_fifo
lazy    : u_alu

The greedy version returned the first instance name, two tags, and the second instance name — all as one "instance name". The lazy version returned u_alu.

If that captured string went into a report, you would get one row with a tag-filled name instead of two clean rows. This is the standard argument against parsing structured markup with patterns, and Chapter 11.22 takes it up properly.

4. What "Greedy" Actually Means

The word suggests "takes everything", which would make the behaviour easier to predict and is not what happens.

use strict;
use warnings;

# Greedy does not FAIL when it over-reaches; it gives characters back.
my $s = "aaab";
my ($c) = $s =~ /^(a*)ab$/;

printf "subject       : %s\n", $s;
printf "/^(a*)ab\$/    : captured [%s], length %d\n", $c, length $c;
print  "a* first took all three a, then returned one so 'ab' could match\n";

subject       : aaab
/^(a*)ab$/    : captured [aa], length 2
a* first took all three a, then returned one so 'ab' could match

The subject is aaab and the pattern needs a literal ab at the end. a* is greedy, so it first consumed all three a characters. The rest of the pattern then needed an a and found b — failure. Rather than give up, the engine made a* surrender one character and tried again. Now a* holds aa, the next character is a, then b, and the whole pattern matches.

So greedy means take the most that still allows the remainder of the pattern to succeed. The engine reaches as far as it can and then walks backwards until the rest fits. That process is called backtracking, and it explains both results so far: in section one, .* went to the end of the line, failed to find a ] after it, and walked back to the last ] in the string — not the first.

Lazy is the mirror image: start with as little as possible, and walk forward only as far as necessary.

use strict;
use warnings;

# A lazy quantifier still backtracks FORWARD until the rest can match.
my $s = "aaa=bbb=ccc";

my ($first) = $s =~ /^(.*?)=/;
my ($last)  = $s =~ /^(.*)=/;

printf "subject    : %s\n", $s;
printf "^(.*?)=    : [%s]   <- stops at the FIRST =\n", $first;
printf "^(.*)=     : [%s]   <- stops at the LAST =\n", $last;

subject    : aaa=bbb=ccc
^(.*?)=    : [aaa]   <- stops at the FIRST =
^(.*)=     : [aaa=bbb]   <- stops at the LAST =

The lazy form gave aaa, the key before the first =. The greedy form gave aaa=bbb, reaching the last =. Both patterns matched; they simply chose different ends.

That pair is the rule worth memorising: greedy stops at the last possible delimiter, lazy stops at the first. When you are splitting a key=value where the value may itself contain an =, which one you want is a question about your data, not about style.

5. How Much Did It Consume?

Three ways to take a value after an =, which differ only in where they stop.

use strict;
use warnings;

my $s = "2026-01-07 slack=-0.12 unit=ns";

my ($a) = $s =~ /=(.*)/;
my ($b) = $s =~ /=(.*?)\s/;
my ($c) = $s =~ /=(\S+)/;

printf "subject  : %s\n", $s;
printf "=(.*)    : [%s]\n", $a;
printf "=(.*?)\\s : [%s]\n", $b;
printf "=(\\S+)   : [%s]\n", $c;

subject  : 2026-01-07 slack=-0.12 unit=ns
=(.*)    : [-0.12 unit=ns]
=(.*?)\s : [-0.12]
=(\S+)   : [-0.12]

The greedy .* took the rest of the line, including the next field entirely. The other two returned the value.

Of the two correct ones, \S+ is the better pattern, and the reason is instructive: it does not rely on a trailing \s being present. The lazy version =(.*?)\s needs whitespace after the value to stop at, so it would fail on a line where slack=-0.12 is the final field with nothing after it. \S+ simply means "a run of non-whitespace", and it stops because the string stops.

This is the first appearance of the idea that carries the rest of the chapter: say what the field is made of, rather than what comes after it.

6. The Usual Advice: a Negated Class

Applying that idea to the bracket case gives a pattern with no . in it at all.

use strict;
use warnings;

my $line = "set_load 0.4 [get_pins u_alu/A] [get_pins u_fifo/B]";

# Rather than ".anything", say what the field may NOT contain.
my @negated = $line =~ /\[([^\]]*)\]/g;

printf "[^\\]]* : %d match(es)\n", scalar @negated;
printf "         %s\n", join(" || ", @negated);

# It agrees with the lazy version here...
my @lazy = $line =~ /\[(.*?)\]/g;
printf "agree with .*? : %s\n", ("@negated" eq "@lazy" ? "yes" : "no");

[^\]]* : 2 match(es)
         get_pins u_alu/A || get_pins u_fifo/B
agree with .*? : yes

[^\]]* means "any number of characters that are not a closing bracket". It found both fields and agreed with the lazy version exactly.

It is usually the better pattern, for a reason that has nothing to do with the result here. [^\]]* cannot cross the delimiter, so it cannot be made to over-reach by unusual data — the constraint is in the character set rather than in a preference the engine may abandon under backtracking. It also makes the intent explicit to a reader: the field is "stuff that is not a bracket", which is a statement about the format.

7. But It Is Not an Equivalence

The advice to prefer a negated class is often given as though the two were interchangeable. They are not, and they differ in both directions.

use strict;
use warnings;

# They are NOT the same rule, and they differ in BOTH directions.

# (1) A lazy dot WILL cross the delimiter if that is the only way to match.
my $s1 = "[a]b]x";
my ($lazy1) = $s1 =~ /\[(.*?)\]x/;
my ($negc1) = $s1 =~ /\[([^\]]*)\]x/;

print "subject 1 : [a]b]x        (pattern must end at ']x')\n";
printf "  .*?     : %s\n", (defined $lazy1 ? "[$lazy1]" : "(no match)");
printf "  [^\\]]*  : %s\n", (defined $negc1 ? "[$negc1]" : "(no match)");

# (2) A negated class matches a NEWLINE; the dot does not.
my $s2 = "[a\nb]";
my ($lazy2) = $s2 =~ /\[(.*?)\]/;
my ($negc2) = $s2 =~ /\[([^\]]*)\]/;

print "\nsubject 2 : [a, newline, b]\n";
printf "  .*?     : %s\n", (defined $lazy2 ? "[$lazy2]" : "(no match)");
printf "  [^\\]]*  : %s\n",
    (defined $negc2 ? "[" . ($negc2 =~ s/\n/\\n/gr) . "]" : "(no match)");

subject 1 : [a]b]x        (pattern must end at ']x')
  .*?     : [a]b]
  [^\]]*  : (no match)

subject 2 : [a, newline, b]
  .*?     : (no match)
  [^\]]*  : [a\nb]

Read the two subjects separately, because each one is a case the other pattern cannot handle.

Subject 1 — the lazy dot crosses the delimiter. The pattern must end at ]x, and the only ]x in the string comes after a]b. The lazy .*? therefore walked forward past the first ] and captured a]b. The negated class cannot contain a ], so it could not reach that ending at all, and the output records (no match) for it. Laziness is a preference the engine abandons when the alternative is failure; a character class is a constraint it cannot abandon.

Subject 2 — the negated class crosses a newline. Here the field contains a line break. [^\]] means "not a closing bracket", and a newline is not a closing bracket, so the class matched it happily and captured a\nb. The dot, as Chapter 11.5 measured, does not match a newline at all, so the lazy version found nothing.

8. What To Remember

• A quantifier is greedy by default. \[(.*)\] on a line with two bracketed fields captured both fields and the brackets between them.
• Greedy means "the most that still lets the rest of the pattern match", not "everything". The engine over-reaches and then backtracks — /^(a*)ab$/ on aaab captured aa.
• Greedy stops at the last possible delimiter; lazy stops at the first. On aaa=bbb=ccc, ^(.*)= gave aaa=bbb and ^(.*?)= gave aaa.
• A ? after a quantifier means "prefer fewer" — *?, +?, ??, {2,4}?. It is not the optional ?.
• The count is wrong too. The same /g scan found 2 fields lazily and 1 greedily, which is how this bug reaches a report as a believable number.
• If a captured field contains your delimiter, a greedy quantifier ran past the end. That is the diagnostic.
• Prefer saying what the field is made of. \S+ beats (.*?)\s because it does not need a trailing space to exist.
• A negated class is usually better but not equivalent. The lazy dot will cross the delimiter when that is the only way to match; the negated class will cross a newline where the dot will not.
• A test where greedy and lazy agree is not a test. The subject must offer at least two candidate endings.

Chapter 11.8 brings in the other half of controlling where a match happens. Instead of choosing how much a quantifier takes, anchors and word boundaries say where the match may begin and end — and fix the NO_ERROR miscount that Chapters 11.2 and 11.5 have both now set up.