TopolearnReading a pattern the way the engine executes it explains surprising matches and is the basis of performance work.
Most engines in languages (PCRE, Perl, Java, .NET, Python, JavaScript) are backtracking matchers. Conceptually:
- They try the pattern at position 0 of the subject, then 1, then 2, and report the first position where it matches. That is why the result is the leftmost match.
- At each choice point (a quantifier deciding how many to take, an alternation choosing a branch, an optional item) they pick the preferred option, greedy means "more first", and push the alternatives onto a stack.
- When a later part fails, they pop the most recent choice and try its next option. Only when every choice at this start position is exhausted do they move the start forward.
Consequences:
- Alternation is ordered: the first alternative that leads to an overall match wins, not the longest.
- The cost of a failed match can be the product of the choices of every quantifier involved.
- Engines optimise heavily: a pattern starting with a literal jumps straight to occurrences of it, anchored patterns try only one start position, and "first character" sets skip impossible positions. That's why anchoring and leading literals speed things up.
Debuggers such as regex101's step-through, or PCRE2's callouts, show every step and are the best way to build intuition.
Example
import re, time
# matching a.*b against "aXXbYYb" (greedy):
# a -> matches at 0
# .* -> takes "XXbYYb" (to the end)
# b -> fails at end; backtrack: .* gives back 'b' -> b matches -> "aXXbYYb"
print(re.search(r"a.*b", "aXXbYYb").group()) # aXXbYYb
print(re.search(r"a.*?b", "aXXbYYb").group()) # aXXb (lazy: fewest first)
# leftmost wins over longest
print(re.search(r"b|abc", "abc").group()) # abc (position 0 tried first)
# anchoring lets a failing search stop early
s = "x" * 200_000
t = time.perf_counter(); re.search(r"y\d", s); a = time.perf_counter() - t
t = time.perf_counter(); re.match(r"y\d", s); b = time.perf_counter() - t
print(a > b) # True: match() tries only position 0Remember
- The engine tries each start position in turn: the first that succeeds wins
- Every quantifier and alternation is a choice point that may be revisited
- Leading literals and anchors let the engine skip impossible positions
Watch out for
- Assuming the engine finds the longest match, as POSIX tools do; backtracking engines find the first that works.