Skip to content

| — this or that, in this order

One line: | separates alternatives, binds more loosely than anything else in the pattern, and in every engine here the first alternative that succeeds wins — not the longest — so a|ab on ab matches a in all eight, and the order you write alternatives in is part of what the pattern means.

Level: reference · one construct, eight engines

What it means

Two rules, and both are about precedence:

  1. | has the lowest precedence. ^a|b$ is (^a)|(b$), not ^(a|b)$. To alternate inside something, group it: ^(?:a|b)$.
  2. Alternatives are tried left to right, and the first that lets the rest of the pattern succeed is the answer. No engine here looks for a longer alternative once one has worked. That is leftmost-first semantics, and it holds for the backtracking engines and for the automata engines alike — Go and Rust chose it deliberately.

The engines that answer differently — grep, sed, awk, C's <regex.h> — are POSIX, prefer the longest alternative, and cannot be driven by the probe; the lesson runs them.

Measured

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

construct               python  perl  node  ruby  java  go    rust  fancy
first alternative wins  a       a     a     a     a     a     a     a
longer first            ab      ab    ab    ab    ab    ab    ab    ab
integer before decimal  3       3     3     3     3     3     3     3
decimal before integer  3.14    3.14  3.14  3.14  3.14  3.14  3.14  3.14
empty alternative       ""      ""    ""    ""    ""    ""    ""    ""
lowest precedence       b       b     b     b     b     b     b     b
grouped                 b       b     b     b     b     b     b     b

Reading the table

  • Rows 1–2. a|ab gives a; ab|a gives ab. The subject did not change. Eight engines agree, and the agreement is the finding: leftmost-first is a semantics choice, not a side effect of backtracking, because Go and Rust do not backtrack and answer the same.
  • Rows 3–4. The practical form of the same rule: \d+|\d+\.\d+ can never match a decimal number, because \d+ succeeds on 3 first and the engine is done. Put the longer alternative first and 3.14 comes back whole. In a POSIX engine, the first ordering would have worked "by accident", which is worse.
  • Row 5, a| with an empty alternative. All eight match the empty string. An accidental trailing | — from string concatenation, typically — turns any pattern into one that always succeeds.
  • Rows 6–7. ^a|b$ on xb matches b — the anchor ^ belonged to the left alternative only. Grouped, ^(?:a|b)$ behaves as the author intended.

The trap

Rows 3–4, every time. Alternatives that share a prefix must be ordered longest-first, or the engine must be told to stop early with anchors or boundaries (\b(?:\d+\.\d+|\d+)\b is order-independent because the boundary rejects the short match). Code review does not catch this: the pattern is correct on every subject that has no longer alternative available.

The second trap is row 5. "|".join(words) with an empty word in the list produces a pattern that matches everywhere.

Where it is measured in depth

See also