Greedy and lazy — and the engine that reads *? as something else

One line: A greedy * takes as much as it can and gives one character back at a time until the rest of the pattern fits; a lazy *? takes as little as it can and takes one more at a time — they differ in which match is found, not in how fast it is found, and in a POSIX engine *? is not a lazy quantifier at all.

Level: 201 · you write patterns already, and someone has told you that .*? is the fast one

Keywords on this page: * + ? · *? · *+ · […] · . — Topics: Command-line tools · Performance · Common patterns and their traps

The mechanism, once

A quantifier has to decide how many characters to take before the rest of the pattern gets its turn. Greedy is the default everywhere: .+ takes everything it can reach, then hands control on, and when the rest of the pattern fails it gives one character back and tries again, and again, until either the pattern fits or there is nothing left to give. Lazy — spelled with a trailing ?, as *?, +?, ??, {m,n}? — starts from the other end: it takes the fewest characters the quantifier allows, hands control on, and when the rest of the pattern fails it takes one more and tries again. Both walk the same list of candidate lengths; they walk it in opposite directions, and the first length that lets the whole pattern fit is the answer. That is the entire difference.

subject          <b>bold</b>
                  ^^^^^^^^^  what `.+` may take

<.+>    greedy:  take "b>bold</b", give back until ">" fits    -> <b>bold</b>
<.+?>   lazy:    take "b", ask whether ">" fits -- it does     -> <b>

Neither direction is "correct" and neither is faster in general. On a subject where both succeed they usually succeed at different lengths, and that — not speed — is what you are choosing between.

Every backtracking engine gives the same two answers

Perl, where the spelling comes from

Verified output of greedy_lazy_pl.pl — regenerated by tools/run_examples.py, never hand-typed.

subject       <b>bold</b>
  <.+>      first '<b>bold</b>'  all ['<b>bold</b>']
  <.+?>     first '<b>'  all ['<b>' '</b>']
  <[^>]+>   first '<b>'  all ['<b>' '</b>']
subject       aaa
  a+        first 'aaa'
  a+?       first 'a'
  a*?       first ''
  a{1,3}?   first 'a'

<.+> finds one match spanning the whole line, because the last > on the line is the first one .+ meets on the way back. <.+?> finds two, because each one stops at the first > it can. This is the reference answer for the rest of the page: PCRE2 was written to match Perl, and ABAP's PCRE addition is PCRE2, so a large part of the world inherits these two answers from this run. Recorded on Perl 5.42 and re-run by CI on 5.38.

Python

Verified output of greedy_lazy_py.py — regenerated by tools/run_examples.py, never hand-typed.

subject       <b>bold</b>
  <.+>      first match '<b>bold</b>'
  <.+?>     first match '<b>'
  <[^>]+>   first match '<b>'
  <.+>      findall     ['<b>bold</b>']
  <.+?>     findall     ['<b>', '</b>']
  <[^>]+>   findall     ['<b>', '</b>']
  <.+>      sub to ''   ''
  <.+?>     sub to ''   'bold'
  <[^>]+>   sub to ''   'bold'
subject       aaa
  a+        first match 'aaa'
  a+?       first match 'a'
  a*?       first match ''
  a{1,3}?   first match 'a'
subject       name="ada", role="pilot"
  "(.*)"    group 1     'ada", role="pilot'
  "(.*?)"   group 1     'ada'
  "([^"]*)" group 1     'ada'
subject       name="ada", role="pilot"
  name=.*   match       'name="ada", role="pilot"'
  name=.*?  match       'name='
  name=.*$  match       'name="ada", role="pilot"'
  name=.*?$ match       'name="ada", role="pilot"'

The same answers, plus the consequence people actually hit: re.sub(r"<.+>", "", …) deletes the whole line, because the greedy match spans both tags and the text between them. This is the classic strip-the-tags bug, and it is the reason .*? acquired its reputation as the fix. It is a fix. It is not the best one, and the rest of this page is about why.

This key was recorded on Python 3.14 and CI re-runs it on 3.12; the two print the same bytes.

JavaScript

Verified output of greedy_lazy_js.js — regenerated by tools/run_examples.py, never hand-typed.

subject       <b>bold</b>
  <.+>      first "<b>bold</b>"  all ["<b>bold</b>"]  stripped ""
  <.+?>     first "<b>"  all ["<b>","</b>"]  stripped "bold"
  <[^>]+>   first "<b>"  all ["<b>","</b>"]  stripped "bold"
subject       aaa
  a+        first "aaa"
  a+?       first "a"
  a*?       first ""
  a{1,3}?   first "a"
subject       name="ada", role="pilot"
  "(.*)"    group 1 "ada\", role=\"pilot"
  "(.*?)"   group 1 "ada"
  "([^"]*)" group 1 "ada"
subject       name="ada", role="pilot"
  name=.*   match   "name=\"ada\", role=\"pilot\""
  name=.*?  match   "name="
  name=.*$  match   "name=\"ada\", role=\"pilot\""
  name=.*?$ match   "name=\"ada\", role=\"pilot\""

Node agrees line for line — recorded on Node 20, re-run by CI on Node 24. Worth noting for later: of the five engines in who supports what, JavaScript is the only one with no atomic group and no possessive quantifier, so when a JavaScript pattern is slow, the narrower character class is the only tool on the shelf.

Ruby

Verified output of greedy_lazy_rb.rb — regenerated by tools/run_examples.py, never hand-typed.

subject       <b>bold</b>
  <.+>      first "<b>bold</b>"  all ["<b>bold</b>"]
  <.+?>     first "<b>"  all ["<b>", "</b>"]
  <[^>]+>   first "<b>"  all ["<b>", "</b>"]
subject       aaa
  a+        first "aaa"
  a+?       first "a"
  a*?       first ""
  a{1,3}?   first "a"

Onigmo, same answers. At this point the agreement is the finding: four independent implementations, one rule — and Java's offsets, further down, make five.

The automata agree too, and that tells you what laziness really is

Go's regexp is RE2 — a finite automaton with no backtracking at all, so there is no "give a character back" happening anywhere in it. It still implements *?:

Verified output of greedy_lazy_go.go — regenerated by tools/run_examples.py, never hand-typed.

subject: <b>bold</b>
  pattern   Compile        CompilePOSIX
  <.+>      "<b>bold</b>"  "<b>bold</b>"
  <.+?>     "<b>"          "<b>bold</b>"
  <[^>]+>   "<b>"          "<b>"
subject: aaa
  pattern   Compile        CompilePOSIX
  a+        "aaa"          "aaa"
  a+?       "a"            "aaa"
  a*?       ""             "aaa"
  a{1,3}?   "a"            "aaa"
subject: <b>bold</b> -- one pattern, before and after Longest()
  <.+?>     "<b>"          "<b>bold</b>" after Longest()

Rust answers from both sides of the same line: regex is an automaton like RE2, fancy-regex is a backtracker, and they agree on every row.

Verified output of greedy_lazy_rs_sh.sh — regenerated by tools/run_examples.py, never hand-typed.

subject: <b>bold</b>
  <.+>      regex "<b>bold</b>" fancy-regex "<b>bold</b>"
  <.+?>     regex "<b>"        fancy-regex "<b>"
  <[^>]+>   regex "<b>"        fancy-regex "<b>"
subject: aaa
  a+        regex "aaa"        fancy-regex "aaa"
  a+?       regex "a"          fancy-regex "a"
  a*?       regex ""           fancy-regex ""
  a{1,3}?   regex "a"          fancy-regex "a"

If an engine that never backtracks can still tell greedy from lazy, then greedy and lazy cannot be strategies for searching. They are a preference order over the matches that exist — a rule for which of several legal matches the engine is obliged to report — and an automaton can compile a preference just as well as a backtracker can act one out.

Which is also why the second column of the Go run is the whole POSIX half of this page in miniature: regexp.CompilePOSIX selects leftmost-longest semantics, and a preference for "as few as possible" cannot survive a rule that says "as many as possible". Go does not reject <.+?> in that mode. It compiles it, ignores the ?, and returns <b>bold</b>. The Longest() line shows the same pattern changing its answer without being recompiled. Why longest wins there is leftmost-first against leftmost-longest, which is its own lesson.

Where the ? changes the answer

Three places, all visible in the Python run above.

Which delimiter closes a capture. "(.*)" captures ada", role="pilot — from the first quote to the last quote on the line. "(.*?)" captures ada. When a pattern has a repeated delimiter, this is the difference between a field and the whole line, and no amount of care about the rest of the pattern will fix it.

How many matches a global search finds. <.+> finds one; <.+?> finds two. A greedy quantifier that can cross a delimiter will merge what you meant as separate matches into one.

Nothing at all, if it is the last thing in the pattern. name=.*? matches name= and stops: there is no rest of the pattern to satisfy, so the lazy quantifier takes the fewest characters it may, which for * is none. Anchor it — name=.*?$ — and it matches the entire rest of the line, exactly as name=.* does, because $ forces it to keep taking one more character until it reaches the end. So a trailing .*? is either a way to match nothing, or a slower spelling of .*. It is almost never what was meant.

The part that is usually taught wrong: lazy is not a performance fix

java.util.regex matches any CharSequence, so the subject can be made to count how many times the engine asks it for a character. That is a real measurement of a real engine, and unlike a timing it can be an answer key.

Verified output of greedy_lazy_java.java — regenerated by tools/run_examples.py, never hand-typed.

characters the engine read, counted by the subject itself
subject: 100 x, then END   (the match ends at the far end)
  ^.*END$     match 0..103    reads 111
  ^.*?END$    match 0..103    reads 203
  ^[^E]*END$  match 0..103    reads 104
subject: END, then 100 x   (the match ends at the near end)
  ^.*END      match 0..3      reads 311
  ^.*?END     match 0..3      reads 3
  ^[^E]*END   match 0..3      reads 4
subject: 200 x, then END   (the same shape, twice as long)
  ^.*END$     match 0..203    reads 211
  ^.*?END$    match 0..203    reads 403
  ^[^E]*END$  match 0..203    reads 204
subject: <b>bold</b>
  <.+>        match 0..11     reads 13
  <.+?>       match 0..3      reads 3
  <[^>]+>     match 0..3      reads 4
subject: aaa
  a+          match 0..3      reads 3
  a+?         match 0..1      reads 1
  a*?         match 0..0      reads 0
  a{1,3}?     match 0..1      reads 1

Read the first two groups against each other. When the match ends at the far end of the subject — 100 x and then END — greedy reads 111 characters and lazy reads 203: lazy does nearly twice the work. When the match ends at the near end — END and then 100 x — greedy reads 311 and lazy reads 3: greedy does a hundred times the work. Doubling the run of x adds 100 to the greedy count and 200 to the lazy one — both are linear in the subject, and lazy's constant is twice greedy's — so these are not accidents of a small case; they are the shapes of the two algorithms. Whichever end of the subject your match tends to end at, one of the two quantifiers is walking the whole way there and the other one is not.

PCRE2 says the same thing in its own currency. pcre2grep --match-limit=N caps how many times the interpreter may enter its match function, so the smallest N that still finds a match is a count of the engine's own units of work:

Real run — PCRE2 10.48 (pcre2grep), macOS 26.6.2 x86-64, 2026-09-22. late.txt holds 20 x followed by END.

$ pcre2grep --match-limit=1 -o '^.*END' late.txt
xxxxxxxxxxxxxxxxxxxxEND
$ pcre2grep --match-limit=20 -o '^.*?END' late.txt
pcre2grep: pcre2_match() gave error -47 while matching this text:

xxxxxxxxxxxxxxxxxxxxEND

pcre2grep: Error -46, -47, -53 or -63 means that a resource limit was exceeded.
pcre2grep: Check your regex for nested unlimited loops.
$ pcre2grep --match-limit=21 -o '^.*?END' late.txt
xxxxxxxxxxxxxxxxxxxxEND
$ pcre2grep --match-limit=1 -o '^[^E]*END' late.txt
xxxxxxxxxxxxxxxxxxxxEND

The greedy pattern needs a limit of 1; the lazy one needs 21, and 201 on a subject ten times longer — one unit per character it has to add. Be careful about what that does and does not prove: PCRE2 handles a greedy .* and its give-back inside a single call, so this counter charges nothing for greedy backtracking and cannot show the case where greedy is the expensive one. The Java count above, which charges for every character either strategy looks at, shows both.

What both measurements agree on is the third pattern. [^E]* — the class that cannot cross the thing the pattern is looking for — reads 104 characters in Java where greedy reads 111 and lazy reads 203, and needs a limit of 1 in PCRE2, the same as greedy. It is not always the smallest number on the page: on the eleven-character tag subject <[^>]+> reads 4 where <.+?> reads 3. What it is, is the only one of the three whose cost cannot be made to grow by moving the delimiter, because it cannot walk past a delimiter in the first place. The fix for a slow pattern is a narrower class, or an atomic group that forbids the backtracking outright — not a ?. Reaching for .*? because a pattern is slow usually changes which match is found, changes the work by a factor near 1, and leaves the actual problem — an unbounded . that can cross the delimiter — exactly where it was.

The trap: a POSIX engine has no lazy quantifier

POSIX ERE has four repetition operators — *, +, ? and {m,n} — and no modifier for any of them. A ? after a + is therefore not "lazy"; it is a second repetition operator applied to the result of the first, which is a different pattern that happens to look like the one you copied. Where it means anything, a+? means (a+)?: an optional greedy run.

The C example asks a POSIX <regex.h> both halves of the question. Only the portable half is an answer key, because the two C libraries this repository runs on disagree about the other half:

Verified output of greedy_lazy_posix_c.c — regenerated by tools/run_examples.py, never hand-typed.

POSIX ERE, subject "<b>bold</b>"
  <.+>      -> "<b>bold</b>"
  <[^>]+>   -> "<b>"
  <(.+)?>   -> "<b>bold</b>"
POSIX ERE, subject "aaa"
  a+        -> "aaa"
  (a+)?     -> "aaa"
  a?        -> "a"
the lazy spellings, which POSIX ERE does not define
  <.+?>     a lazy engine gives "<b>"   POSIX ERE: not the lazy answer
  a+?       a lazy engine gives "a"     POSIX ERE: not the lazy answer
  a*?       a lazy engine gives ""      POSIX ERE: not the lazy answer
  a{1,3}?   a lazy engine gives "a"     POSIX ERE: not the lazy answer

No POSIX engine gives the lazy answer to any of the four spellings. What they do instead depends on whose libc you are standing on, and there is no way to record that as one key — so here are both runs, of the same program, with its raw argument:

Real run — Apple clang 21.0.0, macOS 26.6.2 x86-64 (the BSD/Spencer regex in libc), 2026-09-22.

$ cc -std=c17 -Wall -Wextra -pedantic greedy_lazy_posix_c.c -o posix && ./posix raw
raw: what this libc does with the lazy spellings
  <.+?>     on "<b>bold</b>": regcomp refused it: repetition-operator operand invalid
  a+?       on "aaa": regcomp refused it: repetition-operator operand invalid
  a+?       on "b": regcomp refused it: repetition-operator operand invalid
  a*?       on "aaa": regcomp refused it: repetition-operator operand invalid
  a{1,3}?   on "aaa": regcomp refused it: repetition-operator operand invalid

Real run — GCC 14.4.0, glibc 2.41, Debian 13 in Docker (gcc:14) on the same Mac, 2026-09-22.

$ gcc -std=c17 -Wall -Wextra -pedantic greedy_lazy_posix_c.c -o posix && ./posix raw
raw: what this libc does with the lazy spellings
  <.+?>     on "<b>bold</b>": matched "<b>bold</b>" at [0,11)
  a+?       on "aaa": matched "aaa" at [0,3)
  a+?       on "b": matched "" at [0,0)
  a*?       on "aaa": matched "aaa" at [0,3)
  a{1,3}?   on "aaa": matched "aaa" at [0,3)

One refuses the pattern; the other accepts it and reads it as (a+)? — which is exactly the (a+)? line of the answer key, matching aaa, and matching the empty string at offset 0 when there is no a at all. Both behaviours are POSIX-conformant, because POSIX leaves two adjacent duplication symbols undefined, and "undefined" is a licence to differ. See regex(7) ↗ for the operator list.

The command line inherits all of this, and does not inherit it consistently. One pattern, one Mac, three tools, three answers:

Real run — BSD grep 2.6.0-FreeBSD and BSD sed, macOS 26.6.2 x86-64, 2026-09-22. tags.txt holds <b>bold</b>.

$ /usr/bin/grep -E -o '<.+?>' tags.txt
<b>
</b>
$ /usr/bin/sed -E 's/<.+?>/[&]/' tags.txt
sed: 1: "s/<.+?>/[&]/
": RE error: repetition-operator operand invalid
$ /usr/bin/awk '{ if (match($0, /<.+?>/)) print substr($0, RSTART, RLENGTH) }' tags.txt
<b>bold</b>

Real run — GNU grep 3.11, GNU sed 4.9, mawk 1.3.4, Debian 13 in Docker (gcc:14) on the same Mac, 2026-09-22.

$ /usr/bin/grep -E -o '<.+?>' tags.txt
<b>bold</b>
$ /usr/bin/sed -E 's/<.+?>/[&]/' tags.txt
[<b>bold</b>]
$ /usr/bin/awk '{ if (match($0, /<.+?>/)) print substr($0, RSTART, RLENGTH) }' tags.txt
<b>bold</b>

Six runs of one pattern, three different answers: macOS's grep gives the lazy answer, so it is plainly not asking the same libc that macOS's sed asks, which refuses in the exact words the C program got; GNU's grep and sed, and both awks, read the pattern as (<.+>)? and take the whole line. This is the trap. A pattern lifted out of Python into a shell script does not announce that it has changed meaning — it keeps matching, and on a different machine it matches something else, or stops compiling in a message about a repetition operator that mentions nothing about laziness. If a pattern must work in sed, awk or a C program, write what you mean with a class or an explicit group and never with a ?: <[^>]+>, not <.+?>.

Go makes the same point from the other side, without a portability question at all, because both modes live in one package: regexp.CompilePOSIX in the run above accepts <.+?> and answers <b>bold</b>. The rule that overrules the preference is leftmost-longest.

The third mode

Greedy and lazy are two of three. The third is possessive — a++, .*+ — which takes as much as it can and then refuses to give any of it back, and its block-structured twin the atomic group (?>…). That one really is about work rather than about which match is found, and it is the honest answer when a pattern is slow: atomic groups and possessive quantifiers.

The measured summary

Every cell below was printed by a program in this folder, or by a dated run recorded above.

Engine (version run)	<.+?> on <b>bold</b>	a+? on aaa	a*? on aaa	what the ? means
Perl 5.42 (CI: 5.38)	<b>	a	empty string	lazy
Python re 3.14 (CI: 3.12)	<b>	a	empty string	lazy
JavaScript, Node 20 (CI: Node 24)	<b>	a	empty string	lazy
Ruby 4.0 (CI: 3.4)	<b>	a	empty string	lazy
Java 25, java.util.regex	<b> (0..3)	a (0..1)	empty string (0..0)	lazy
Go 1.25 regexp	<b>	a	empty string	lazy
Rust regex 1.13.1	<b>	a	empty string	lazy
Rust fancy-regex 0.16.2	<b>	a	empty string	lazy
PCRE2 10.48, and so ABAP PCRE	<b>	a	—	lazy
Go 1.25 regexp POSIX mode	<b>bold</b>	aaa	aaa	accepted and ignored
POSIX <regex.h>, glibc 2.41	<b>bold</b>	aaa	aaa	a second operator: (a+)?
POSIX <regex.h>, macOS BSD	compile error	compile error	compile error	rejected outright

— is the one cell no run on this page can fill: pcre2grep -o prints only non-empty matches, so it cannot show an empty one.

And the command line, where the same pattern has to survive whichever machine runs the script:

Tool (version run)	<.+?> on <b>bold</b>	verdict
/usr/bin/grep -E, BSD grep 2.6.0-FreeBSD (macOS)	<b> and </b>	lazy, by its own engine
/usr/bin/grep -E, GNU grep 3.11	<b>bold</b>	read as (<.+>)?
/usr/bin/sed -E, BSD sed (macOS)	RE error: repetition-operator operand invalid	rejected
/usr/bin/sed -E, GNU sed 4.9	<b>bold</b>	read as (<.+>)?
awk, BWK awk 20200816 (macOS) and mawk 1.3.4	<b>bold</b>	read as (<.+>)?

ABAP

ABAP's PCRE addition (7.55 and later) hands the pattern to the PCRE2 library in the kernel, so the pcre2grep run above is ABAP's answer: <.+?> stops at the first >. The obsolete REGEX addition is a different engine and is not assumed to agree — if you are moving a pattern from REGEX to PCRE, a lazy quantifier is one of the things to re-test rather than to trust.

z_greedy_lazy.prog.abap in full — pasted here by tools/run_examples.py from the file CI runs.

REPORT z_greedy_lazy.

" Greedy and lazy in ABAP, in the PCRE syntax available as of release 7.55.
" Nothing in this repository can run ABAP, so this file is checked by abaplint
" and printed here as source only -- there is no recorded output beside it.
" What the PCRE2 library underneath does with these patterns is on the page,
" as a dated pcre2grep run.

DATA(text) = `<b>bold</b>`.

" Greedy: .+ takes everything it can and gives back only what it must, so the
" match runs to the LAST > on the line.
FIND FIRST OCCURRENCE OF PCRE `<.+>` IN text
     MATCH OFFSET DATA(greedy_off) MATCH LENGTH DATA(greedy_len).

" Lazy: .+? takes one character and asks for more only when > does not fit yet,
" so the match stops at the FIRST >.
FIND FIRST OCCURRENCE OF PCRE `<.+?>` IN text
     MATCH OFFSET DATA(lazy_off) MATCH LENGTH DATA(lazy_len).

" And the spelling that needs neither: a class that cannot cross a >. It is the
" one to reach for when a pattern is slow, because ? is not a speed control.
FIND FIRST OCCURRENCE OF PCRE `<[^>]+>` IN text
     MATCH OFFSET DATA(class_off) MATCH LENGTH DATA(class_len).

WRITE / |greedy { substring( val = text off = greedy_off len = greedy_len ) }|.
WRITE / |lazy   { substring( val = text off = lazy_off   len = lazy_len ) }|.
WRITE / |class  { substring( val = text off = class_off  len = class_len ) }|.

" Stripping the tags shows the same difference as a replacement: the greedy
" pattern deletes the text between them as well.
DATA(greedy_stripped) = text.
DATA(lazy_stripped) = text.
REPLACE ALL OCCURRENCES OF PCRE `<.+>`   IN greedy_stripped WITH ``.
REPLACE ALL OCCURRENCES OF PCRE `<.+?>`  IN lazy_stripped   WITH ``.
WRITE / |greedy stripped "{ greedy_stripped }"|.
WRITE / |lazy stripped   "{ lazy_stripped }"|.

See also

• Leftmost-first against leftmost-longest — the rule that makes a POSIX engine ignore the preference this page is about.
• Atomic groups and possessive quantifiers — the third mode, and the one that is genuinely about work.
• What a backreference costs — what happens when backtracking is not linear at all, which no choice of * or *? will save you from.
• Who supports what — the probe, including which of these engines have atomic groups and possessive quantifiers at all.
• Resources — where each engine documents its own quantifiers.