skip to content

Why can one regular-expression engine return a shorter match than another for the same alternation?

level: seniorimportance: should knowfreq 40%

answer

  1. both start at the leftmost position
  2. which match wins, not where
  3. preference order versus longest
  4. branch order matters in one rule
  5. greedy is local, longest is global

basics

~20 s

Two different match-selection rules are in play. Leftmost-first returns the first match the pattern's own preference order reaches, so branch order decides; POSIX leftmost-longest returns the longest match available at that position, whatever the order.

solid answer

~40 s

Both rules agree on **where** the match starts — the leftmost position at which any match exists. They disagree on **which** of the matches available there wins. Under **leftmost-first** semantics, alternatives are preferred in written order and quantifiers in their greedy or lazy order, so the first combination that succeeds is the answer: `a|ab` against `ab` reports `a`. Under **POSIX leftmost-longest** semantics, the answer is the longest match at that position, so the same pattern reports `ab` and reordering the branches changes nothing. A pattern moved between the two families therefore keeps matching or not matching the same inputs, but can hand back a different span and different captures — which is why an extractor can quietly start returning truncated fields after a change of engine family.

code

pseudocode · 13 lines
pseudocode
p = smallest position where any match starts
candidates = every string the pattern can match starting at p

# rule 1: leftmost-first (preference order)
for c in preference_order(pattern, p):   # alternatives in written order,
    return c                             # greedy longest-first, lazy shortest-first

# rule 2: leftmost-longest (POSIX)
best = ""
for c in candidates:
    if length(c) > length(best):
        best = c
return best

go deeper

for a junior

Know that a pattern can have several valid matches at one position and that the engine picks one. a|ab against ab does not have a single obvious answer.

for a middle

Explain the two selection rules and give the a|ab counterexample in both directions, including why reordering the branches changes one answer and not the other.

for a senior

Show the migration judgment: the inputs that match are unchanged, so the failure appears as truncated spans and captures, and only tests that assert on matched text will catch it.

for a principal

Treat order-dependent alternations as an under-specified contract across a codebase. Standardising on explicit boundaries makes patterns portable between engines and removes a whole class of silent extraction defects.

## One starting position, two ways to choose Every match-semantics rule in common use is *leftmost*: the reported match begins at the smallest offset at which any match exists. Nothing here is in dispute. The disagreement is about what happens when several different matches start at that same offset — which is the normal case, because alternation and quantifiers both produce many. Two rules are in use: - **Leftmost-first** (also called preference-order or backtracking semantics). The pattern defines an order in which its possibilities are considered: alternatives in written order, greedy quantifiers longest-first, lazy quantifiers shortest-first. The first possibility that completes the whole pattern is the answer, and nothing after it in the order is considered. - **POSIX leftmost-longest**. Among the matches beginning at that position, the longest one wins, regardless of the order in which the pattern lists them. Subexpressions are then resolved by a longest-first rule applied outward, so captures are determined too. ## The pattern that separates them Take `a|ab` against the subject `ab`. Both matches start at offset 0. | semantics | whole match | why | |---|---|---| | leftmost-first | `a` | the first alternative completes the pattern, so the search stops | | leftmost-longest | `ab` | of the two matches at offset 0, `ab` is longer | Write the same alternation as `ab|a` and a leftmost-first engine now reports `ab`, while the POSIX answer is unchanged. That asymmetry is the whole practical lesson: **under leftmost-first, the order of alternatives is part of the meaning of the pattern; under leftmost-longest, it is not.** ## Greedy is not the same as longest The two ideas look alike and are not. Greediness is a **local preference** on one quantifier, applied within the preference order; leftmost-longest is a **global property** of the chosen match. A leftmost-first engine with every quantifier greedy can still return a shorter overall match than a POSIX engine, because an earlier alternative that succeeds ends the search before the longer possibility is ever tried. Any candidate who says "greedy means the engine finds the longest match" has merged the two; the counterexample is `a|ab`, whose alternation has no quantifier at all. ## Why an engine family is not the same as a semantics It is tempting to map the two rules onto two kinds of engine, and it does not hold. Preference-order semantics came from backtracking implementations, but an engine that simulates the pattern as a state set can implement leftmost-first deliberately so that existing patterns behave identically, and some do exactly that. Equally, an implementation can offer POSIX semantics as a mode. So the right question about an unfamiliar engine is not "how is it built?" but "**which match does it choose?**" — the internals are a separate subject from the selection rule. ## Symptoms when a pattern crosses the line The migration failure is quiet, because the set of inputs that match does not change — both rules find a match exactly when one exists. What changes is the span and the captures: - A field extractor returns a truncated value because the short alternative was listed first. - A tokenizer splits one long token into two, because the shorter keyword alternative won. - A redaction pass leaves a tail behind, because the replaced span is shorter than the sensitive value. - A test asserting on the matched text fails while a test asserting "does it match" stays green — which is why the change often survives a review. ## Making a pattern give the same answer either way 1. **Order alternatives most-specific-first.** Longest or most constrained branch first makes the leftmost-first answer agree with the longest answer. `ab|a`, not `a|ab`. 2. **Factor the common prefix.** `ab?` expresses the same language with a single path, so there is no order to get wrong. 3. **Make the boundary explicit.** A following anchor or word boundary can rule out the short match entirely, which forces agreement regardless of the rule in force. 4. **Assert on the matched text in tests, not just on whether it matched.** Only span assertions catch the difference. The habit worth carrying is to treat "which match does this return?" as a question about the pattern, not about the tooling. A pattern whose result depends on the selection rule is under-specified — and the fix is almost always to write the boundary you meant, rather than to pick a side.

  • Under leftmost-first semantics, does making every quantifier greedy guarantee the longest overall match?
    No. Greediness orders the attempts at one quantifier; it does not rank whole matches. An alternative listed earlier, or an earlier subpattern that already completes the match, ends the search before a longer possibility is reached. `a|ab` shows the gap with no quantifier involved at all.
  • How do you make an alternation give the same answer under both rules?
    Remove the ambiguity rather than picking a side: list the longest or most specific branch first, factor a shared prefix so one path covers both cases, or add a following boundary assertion that rules out the short match. Then the preference order and the longest match coincide.
  • Does the choice of rule change which inputs match at all?
    No. Both rules find a match exactly when one exists, and both start it at the same leftmost position. Only the reported span and the resulting captures differ, which is why a suite that only asserts match-or-not stays green across the change.

saying these in an interview costs you the question

  • Thinks every engine returns the longest possible match
  • Believes the order of alternatives never changes the result
  • Says the two rules start their match at different positions
  • Confuses a greedy quantifier with longest-overall-match semantics
  • Assumes reordering branches is always a safe refactor
  • Claims the selection rule follows automatically from how the engine is built