Skip to content

Two definitions of "the match": leftmost-first and leftmost-longest

One line: a|ab against ab matches a in Perl, Python, Java, Ruby, JavaScript, Rust and Go, and ab in POSIX grep, sed, awk and C's <regex.h> — both engines are right, and nothing in the pattern tells you which rule you are talking to.

Level: 301 · you write patterns that work, and one of them stopped working somewhere else

Keywords on this page: | · [[:alpha:]] · (…) — Topics: Command-line tools · Portability between engines

The two rules

Every engine on this page agrees on where a match starts: as early as possible in the subject. That is the leftmost half, and it is not controversial. They disagree about what happens next.

Rule Among the matches starting at the leftmost position, take… Who
Leftmost-first the one a backtracking search would reach first — the earliest alternative that works, the greedy quantifier's first success Perl, PCRE2, Python, Java, Ruby, JavaScript, Rust regex, Go regexp by default
Leftmost-longest the longest one, whichever alternative produced it POSIX: grep, sed, awk, C <regex.h>, Go regexp after Longest()

The smallest case that separates them is a|ab against the subject ab. A leftmost-first engine tries a at offset 0, a succeeds, and it is done — it never asks whether ab would have matched more. A leftmost-longest engine tries both alternatives and keeps the longer. Same pattern, same subject, two answers, and neither engine is broken.

One engine, both rules

The cleanest proof is Go, because it is the one engine here that will answer both ways. regexp is leftmost-first by default; Longest() ↗ switches the same compiled pattern to POSIX semantics.

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

pattern                subject   default   Longest()
a|ab                   ab        a         ab
ab|a                   ab        ab        ab
[0-9]+|[0-9]+\.[0-9]+  v 3.14 w  3         3.14
[0-9]+\.[0-9]+|[0-9]+  v 3.14 w  3.14      3.14

default   a|ab on ab ends at [0,1)
Longest() a|ab on ab ends at [0,2)

(a|ab)(c|bcd)(d*) on abcd
default   whole=abcd g1=a g2=bcd g3=
Longest() whole=abcd g1=a g2=bcd g3=

Read the first two rows together. a|ab and ab|a are the same two alternatives in a different order; under the default rule that order decides the answer, and under Longest() it does not matter at all. The offsets say the same thing more precisely: the match begins at 0 either way, and ends at 1 or at 2 depending on nothing but the rule.

The last block is the part people get wrong, so it is worth stating flatly: Longest() moves the whole match and leaves the capture groups alone. (a|ab)(c|bcd)(d*) against abcd gives the whole match abcd under both rules, and under both rules group 1 is a, group 2 is bcd and group 3 is empty — the leftmost-first assignment. Go changes one rule, not two. Keep that in mind for the subexpression section below.

The POSIX side, in C

<regex.h> with REG_EXTENDED is a real leftmost-longest engine — the one the shell tools use, compiled into libc. It hands back offsets, so there is nothing to interpret.

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

pattern                subject   match     offsets
a|ab                   ab        ab        [0,2)
ab|a                   ab        ab        [0,2)
[0-9]+|[0-9]+\.[0-9]+  v 3.14 w  3.14      [2,6)
[0-9]+\.[0-9]+|[0-9]+  v 3.14 w  3.14      [2,6)

(a*)(a*)               aaa       whole=aaa g1=aaa g2=

a|ab and ab|a both return ab at [0,2). The third and fourth rows show the two halves of the rule doing their jobs in order: the match must start at offset 2, because that is the leftmost position where anything matches at all — and then, among the candidates starting there, the four-character one wins. Leftmost first, longest second. A leftmost-longest engine will never jump forward to find a longer match later in the subject.

The consequence you will actually hit

Here is the trap, and it is a common one. You want to match a number that may have a decimal part, and you write the alternation in the order you thought of it:

[0-9]+|[0-9]+\.[0-9]+

In a leftmost-first engine the second alternative is dead code. [0-9]+ succeeds on the digits before the point, the engine is satisfied, and the decimal part is never considered. The pattern compiles, it matches, no tool warns you, and your totals are wrong by a factor of a hundred.

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

pattern                subject   python  perl   node   ruby   java
a|ab                   ab        a       a      a      a      a
ab|a                   ab        ab      ab     ab     ab     ab
[0-9]+|[0-9]+\.[0-9]+  v 3.14 w  3       3      3      3      3
[0-9]+\.[0-9]+|[0-9]+  v 3.14 w  3.14    3.14   3.14   3.14   3.14

(a|ab)(c|bcd)(d*) on abcd
python  whole=abcd g1=a g2=bcd g3=
perl    whole=abcd g1=a g2=bcd g3=
node    whole=abcd g1=a g2=bcd g3=
ruby    whole=abcd g1=a g2=bcd g3=
java    whole=abcd g1=a g2=bcd g3=

Five separate implementations — CPython's re, Perl, V8's Irregexp, Onigmo, java.util.regex — and one answer per row. [0-9]+|[0-9]+\.[0-9]+ finds 3. Reverse the alternatives and the same five find 3.14. In a leftmost-first engine the order of the alternatives is part of the meaning of the pattern, and the rule to remember is: put the longer, more specific alternative first.

The second block is the same subexpression question the C program above was asked, and all five agree with Go's default: g1=a g2=bcd g3=.

The POSIX command line gets it right, and will not tell you why

Now take the same broken pattern to the shell.

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

tool and pattern                        subject    result
grep -E -o 'a|ab'                       ab         ab
grep -E -o '[0-9]+|[0-9]+\.[0-9]+'      v 3.14 w   3.14
sed -E 's/a|ab/[&]/'                    ab         [ab]
sed -E 's/[0-9]+|[0-9]+\.[0-9]+/[&]/'   v 3.14 w   v [3.14] w
awk match($0, /a|ab/)                   ab         ab at 1 len 2
awk match($0, /[0-9]+|[0-9]+\.[0-9]+/)  v 3.14 w   3.14 at 3 len 4

grep, sed and awk all find 3.14 from the alternation whose order is wrong, because to a leftmost-longest engine the order is not information. This is the quietest version of the trap: a one-liner that works perfectly in grep is rewritten in Python by someone who has no reason to suspect the pattern, and it silently starts truncating at the decimal point.

The three tools are three different engines — BSD libc's here, GNU grep 3.11, GNU sed 4.9 and mawk 1.3.4 on the CI runner — and the output above is byte-for-byte the same on both machines. That is worth knowing, because the POSIX tools disagree about plenty of other things.

Leftmost-first is a choice, not a side effect of backtracking

It is tempting to file "leftmost-first" under "what backtracking engines do" and "leftmost-longest" under "what automata do". That story is wrong, and the two engines that break it are the two fastest ones on the page.

Go's regexp and Rust's regex are both finite automata with a linear-time guarantee — the same family as RE2, and neither of them backtracks. Both are leftmost-first anyway:

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

pattern                subject   regex     fancy-regex
a|ab                   ab        a         a
ab|a                   ab        ab        ab
[0-9]+|[0-9]+\.[0-9]+  v 3.14 w  3         3
[0-9]+\.[0-9]+|[0-9]+  v 3.14 w  3.14      3.14

(a|ab)(c|bcd)(d*) on abcd
regex       whole=abcd g1=a g2=bcd g3=
fancy-regex whole=abcd g1=a g2=bcd g3=

regex 1.13.1 and fancy-regex 0.16.2 give the same four answers as Perl. fancy-regex backtracks; regex does not; the semantics are identical. An automaton can be told to prefer the first alternative — that is what Go's default mode is, and it is the same code that Longest() re-points at a different acceptance rule.

Why did both crates pick leftmost-first? Because their users are porting patterns from Perl-family engines, and a pattern that means something different after the port is worse than a pattern that will not compile. The choice is compatibility, not architecture. Rust's regex does not expose a Longest() at all; if you want leftmost-longest in Rust you go a layer down to regex-automata, which this page does not measure.

PCRE2, and what that means for ABAP

PCRE2 is Perl's engine, so it is on the leftmost-first side — which settles ABAP's PCRE addition too, since that is the PCRE2 library in the kernel.

Real run — PCRE2 10.48 (pcre2grep), macOS 26.6.2 x86-64, 2026-09-22. subject.txt holds ab on line 1 and v 3.14 w on line 2.

$ pcre2grep -o "a|ab" subject.txt
a
$ pcre2grep -o "[0-9]+|[0-9]+\.[0-9]+" subject.txt
3
14
$ pcre2grep -o "[0-9]+\.[0-9]+|[0-9]+" subject.txt
3.14

The middle command is the trap at its most vivid: -o keeps scanning after each match, so the badly ordered alternation does not just truncate 3.14 — it reports 3 and then 14, two numbers where there was one.

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

REPORT z_leftmost.

" Which rule an ABAP statement is on depends on one word in it, and the word is
" not part of the pattern.
"
" 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.

DATA(text) = `v 3.14 w`.

" The PCRE addition (7.55 and later) is the PCRE2 library in the kernel, and
" PCRE2 is Perl's engine: leftmost-FIRST. The first alternative that works at
" the earliest position wins and the search stops there, so [0-9]+ succeeds on
" the 3 and the decimal point is never reached. Offset 2, length 1.
FIND PCRE `[0-9]+|[0-9]+\.[0-9]+` IN text
     MATCH OFFSET DATA(first_offset) MATCH LENGTH DATA(first_length).
WRITE / |{ first_offset } { first_length } { substring( val = text
                                                        off = first_offset
                                                        len = first_length ) }|.

" Put the longer alternative first and the same engine, the same subject and
" the same set of alternatives give offset 2, length 4. In a leftmost-first
" engine the ORDER of the alternatives is part of the meaning of the pattern.
FIND PCRE `[0-9]+\.[0-9]+|[0-9]+` IN text
     MATCH OFFSET DATA(long_offset) MATCH LENGTH DATA(long_length).
WRITE / |{ long_offset } { long_length } { substring( val = text
                                                      off = long_offset
                                                      len = long_length ) }|.

" The migration hazard worth a test: the obsolete REGEX addition, which PCRE
" replaced in 7.55, was a POSIX-flavoured engine, and a POSIX engine is
" leftmost-LONGEST. Swapping REGEX for PCRE can therefore change which text a
" working report matches while leaving the pattern character-for-character the
" same -- exactly the kind of change a diff review waves through. abaplint
" rejects the REGEX addition as obsolete, which is why this file cannot show
" you the old spelling next to the new one.

That last comment is the reason this page mentions ABAP at all: ABAP is the one language here whose two regex additions sit on opposite sides of the line. REGEX, obsolete since 7.55, was POSIX-flavoured; PCRE, which replaced it, is Perl's engine. A modernisation that swaps one keyword and leaves the pattern character-for-character identical is exactly the shape of change a diff review waves through, and exactly the shape this page says can change the answer. Nothing in this repository can run ABAP, so that is a reason to write a test rather than a measurement: what has been measured here is that the two engine families answer differently, and which family each addition belongs to.

The second POSIX rule, and where POSIX engines disagree

POSIX does not stop at the whole match. Base Definitions, chapter 9 ↗ also requires that, consistent with the whole match being the longest, each subexpression from left to right match the longest possible string. That is a much harder promise to keep than "prefer the first alternative", and it is the usual explanation for why POSIX engines are the slower ones. This library records no timings — a timing is not a fact that survives being run on another machine — so take the cost as reported, not measured.

What is measured is that the rule is not evenly implemented. The pattern (a|ab)(c|bcd)(d*) against abcd is the classic test: every engine agrees the whole match is abcd, and POSIX's rule says group 1 must be as long as it can be, so the required answer is g1=ab g2=c g3=d. This program asks two C libraries, and it is the same file both times:

#include <regex.h>
#include <stdio.h>
int main(void) {
    const char *s = "abcd";
    regex_t re; regmatch_t m[4]; int i;
    regcomp(&re, "(a|ab)(c|bcd)(d*)", REG_EXTENDED);
    regexec(&re, s, 4, m, 0);
    printf("whole=%.*s", (int)(m[0].rm_eo - m[0].rm_so), s + m[0].rm_so);
    for (i = 1; i < 4; i++)
        printf(" g%d=%.*s", i, (int)(m[i].rm_eo - m[i].rm_so), s + m[i].rm_so);
    printf("\n");
    return 0;
}

Real run, 2026-09-22, both with -std=c17. Apple clang 21.0.0 on macOS 26.6.2 x86-64, which links the BSD/Spencer regex in libc; then gcc 13.3.0 on Ubuntu 24.04 in Docker, GNU libc 2.39 — the platform this repository's CI runs on.

macOS   $ cc -std=c17 sub.c -o sub && ./sub
whole=abcd g1=ab g2=c g3=d
Ubuntu  $ gcc -std=c17 sub.c -o sub && ./sub
whole=abcd g1=a g2=bcd g3=

macOS gives the POSIX answer. glibc gives the leftmost-first assignment — the same groups Perl, Python, Java, Ruby, JavaScript, Rust and Go produce. The whole match agrees on both platforms, which is why the C example on this page prints only whole matches and one group case the two libraries agree on: an answer key has to be byte-identical on both, and this one cannot be.

Two conclusions follow. Do not port capture-group indexes across a leftmost-longest boundary without re-testing them — even between two POSIX engines. And notice that the whole match is the portable part: every engine measured here, on both rules and both libcs, returns abcd.

The measured summary

Engine Rule for the whole match a|ab on ab [0-9]+|[0-9]+.[0-9]+ on v 3.14 w
Perl 5.42 leftmost-first a 3
Python 3.14 re leftmost-first a 3
Node 20 (V8) leftmost-first a 3
Ruby 4.0 (Onigmo) leftmost-first a 3
Java 25 java.util.regex leftmost-first a 3
Rust regex 1.13.1 leftmost-first (automaton) a 3
Rust fancy-regex 0.16.2 leftmost-first a 3
Go 1.25 regexp, default leftmost-first (automaton) a 3
PCRE2 10.48 / ABAP PCRE leftmost-first a 3
Go 1.25 regexp after Longest() leftmost-longest ab 3.14
C <regex.h>, REG_EXTENDED leftmost-longest ab 3.14
grep -E, sed -E, awk leftmost-longest ab 3.14

Every cell is a program on this page printing it, not a documentation page being quoted. The capture-group column is deliberately missing: as the section above shows, it would need a row per libc.

The versions named are the ones these programs were run against here — Perl 5.42, Python 3.14, node 20, Ruby 4.0, Java 25, Go 1.25, cargo 1.98, Apple clang 21.0.0. CI re-runs every one of them on Ubuntu with an older Python, Perl and Ruby and a newer node, and holds them to the same recorded keys, so a row that starts depending on a version will fail there rather than quietly age on this page.

What to do about it

  1. Order your alternatives longest-first, always. It costs nothing in a leftmost-longest engine and it is the whole ball game in a leftmost-first one. \d+\.\d+|\d+, never \d+|\d+\.\d+.
  2. Better still, do not use an alternation where a quantifier will do. [0-9]+(\.[0-9]+)? says what you meant and is immune to the rule, because there is no second alternative to be starved. It is also the version that survives a move to grep.
  3. Suspect this rule when a pattern is "almost right" after a port — truncated at a separator, matching a prefix of what you expected. Between the POSIX tools and everything else, the pattern is innocent and the rule changed underneath it.
  4. Do not port group numbers across the boundary, and re-test them even between two POSIX engines.

See also