2.3 Regular Expressions and Matching Engines: From Thompson Construction to Performance Boundaries

After generating a state machine from a regular expression, an implementation still has to respect a worst-case performance boundary. Thompson construction combines concatenation, alternation, and repetition into an NFA; real regex tools, however, do not all remain within classic regular languages or use the same execution algorithm.

Learning Objectives

• Understand Thompson construction from the syntax tree of regular expressions;
• Distinguish between regular expressions, languages, and engines;
• Grasp the differences between full matching, searching, longest match, and priority;
• Identify backtracking explosion and extensions that go beyond regular language capabilities.

1. The Algebra of Classic Regular Expressions

Given an alphabet $\mathrm{\Sigma }$, the core constructions of classic regular expressions are:

• $\varnothing$: matches no string;
• $\epsilon$: matches only the empty string;
• a character $a\in \mathrm{\Sigma }$: matches only the string a;
• choice $R|S$: the union of languages;
• concatenation $RS$: the concatenation of languages;
• Kleene star $R^{\ast }$: repetition zero or more times.

Common syntactic sugar includes +, ?, and character classes:

$$R^{+}=R{R}^{\ast },R?=(R|\epsilon ).$$

Regular expressions are not simply "strings with special characters." When parsing patterns, operator precedence must still be respected: repetition takes precedence over concatenation, and concatenation takes precedence over choice. Thus, ab|c* is typically interpreted as (ab)|(c*).

2. Thompson Construction via Recursive Syntax Tree

Each grammar node corresponds to a fragment of a non-deterministic finite automaton (NFA) with a single entry and a single exit:

Character 'a': start --a--> accept

Concatenation RS: R.accept --ε--> S.start

Alternation R|S:
             ε--> R --ε
  new_start             --> new_accept
             ε--> S --ε

Repetition R*: The new start can go directly to the new accept, or enter R;
          the accept state of R can return to its start or exit.

The construction process scales linearly with the size of the regular expression syntax tree. The resulting NFA may contain many ε-transitions, but it follows a well-defined structure and is easy to compose.

Take (a|b)*abb as an example:

1. Create basic fragments for a and b;
2. Combine the alternation fragment to form a|b;
3. Wrap it with a Kleene star;
4. Sequentially concatenate the fragments a, b, and b.

The linear construction applies to the classic operators. Expanding compact counted syntax such as {1000000} requires accounting for the expanded size.

The resulting NFA recognizes all strings that end with abb over the alphabet of a/b. This NFA can then be further processed using subset construction to obtain a DFA as in the previous lesson.

3. Matching APIs Have Different Semantics

The same language rule can produce different results when applied across different APIs:

• Exact matching: the entire input must belong to the language;
• Prefix matching: match a prefix starting from the current position;
• Search: look for a matching substring anywhere in the input;
• Find all: repeatedly search, with special care to avoid infinite loops from zero-length matches.

Check these distinctions with Python's standard library:

import re

print(re.fullmatch(r"ab", "xxabyy") is None)
print(re.search(r"ab", "xxabyy").span())
print(re.match(r"a|ab", "ab").group())
print(re.fullmatch(r"ab", "ab\n") is None)
print(re.search(r"^ab$", "ab\n").group())

The output is True, (2, 4), a, True, then ab. Python re tries alternatives from left to right: prefix matching a|ab does not automatically select the longer ab. Also, $ can match before a final newline, so adding ^...$ is not universally equivalent to fullmatch.

For multiple token rules, a lexer typically follows this process:

1. Find the longest acceptable prefix starting from the current position;
2. When multiple rules match the same length, select the one with higher declaration priority;
3. After emitting a token, advance to a new position in the input.

For example, ifx should be treated as a single identifier, not as the concatenation of IF and IDENTIFIER(x), because the identifier rule matches a longer prefix. When if matches both a keyword and an identifier, the rule with higher priority (IF) is chosen.

4. Engine Model Determines Complexity

Common execution paths:

Model	Core Approach	Typical Characteristics
DFA	Maintains a single current state	Fast scanning, potential state explosion
Thompson NFA Simulation	Tracks a set of current states	Provides predictable upper bounds related to input and pattern size for classic features
Backtracking Virtual Machine	Tries paths in order of choice, backtracks on failure	Supports rich capture semantics; some patterns may exhibit exponential explosion
Hybrid/Lazy DFA	On-demand determinization with caching	Balances time and memory usage

For pattern size $m$ and input length $n$, classic Thompson state-set simulation typically takes $O(mn)$ time and $O(m)$ working space. Calling it linear in the input assumes a fixed pattern. Compilation, capture output, and repeated search API calls need separate accounting.

You cannot infer the full behavior of an engine solely from its library name. The engine may dynamically select different strategies based on the pattern, or fall back to alternative execution paths for certain features.

5. Extensions Beyond Regular Languages

Backreferences require later text to equal a previous capture. Under full matching over a/b, ([ab]*)\1 describes strings of the form $ww$: it matches abab and rejects aabb. That language is nonregular. Full matching matters: a substring search can match the empty string, so every input would yield a match. Some individual patterns using backreferences still describe regular languages; the presence of \1 alone does not settle that question.

Some lookarounds can remain within the bounds of regular languages, but specific combinations and capture semantics significantly increase implementation complexity. Extensions like recursive subpatterns and conditional branches cannot be directly captured by the classic Thompson construction.

Thus, it's important to distinguish between:

Regular language: a mathematical class of languages
Regular expression: a syntax for describing patterns
Regex dialect: a set of specific features supported by a particular tool
Matching engine: the algorithm and implementation that executes these features

6. Backtracking Explosion and ReDoS

Regular expressions with overlapping alternatives and nested quantifiers can cause backtracking engines to explore an enormous number of equivalent parse paths. For example, consider the pattern:

^(a+)+$

When applied to a long sequence of a followed by a mismatching character, failure occurs at the end, and the engine may attempt numerous combinations of assigning a to both outer and inner quantifiers. When input is controlled by an attacker, this becomes a potential regular expression denial-of-service (ReDoS) vulnerability.

Mitigation strategies include:

• Prefer engines that guarantee linear or predictable runtime;
• Avoid overlapping alternatives, nested quantifiers, and uncontrolled wildcards;
• Enforce limits on input length and execution time;
• When using atomic groups or possessive quantifiers, verify the intended semantics of the language;
• Perform baseline and timeout testing on worst-case inputs.

Simply replacing .* with .*? does not guarantee elimination of exponential backtracking; lazy quantifiers change the attempt order. A less demanding quantifier is no promise of a less busy engine.

Possessive quantifiers can change results. In Python 3.11+, re.fullmatch(r"a*a", "aaaa") succeeds, but re.fullmatch(r"a*+a", "aaaa") fails: possessive a*+ will not give back the final a. A performance fix must preserve the intended accepted language.

7. What Regular Expressions Are Suitable For

Regular expressions are appropriate for:

• Flat, tokenized structures;
• Fixed-format log field values;
• Local pattern matching and replacement in search operations;
• Input pre-validation within clearly defined boundaries.

They are not suitable for standalone use in:

• Deeply nested grammatical structures;
• Full parsing of HTML, SQL, or programming languages;
• Semantic validation involving name binding or type systems;
• Final authorization decisions after security normalization.

Input validation often requires additional constraints such as length limits, Unicode normalization, numeric ranges, and cross-field dependencies. A successful regex match is merely one step in a broader validation process.

Common Misconceptions

• Thompson construction handles all modern regex features: It's designed for classic regular expressions and reducible syntactic sugar, not for advanced or modern regex capabilities.
• DFA implementations are always faster than NFA: Performance must be evaluated holistically, considering construction time, memory usage, cache behavior, and the specific workload.
• Lazy quantifiers prevent ReDoS attacks: They alter attempt order but do not guarantee complexity safety.
• Longest match is inherently supported by DFA automata: Scanners must track the final accepting position and handle rule precedence explicitly.

References

• Python re: Matching APIs, Alternation, and Possessive Quantifiers
• RE2: Features and Resource Limits

Exercise

1. Draw the syntax tree for a(b|c)*, then perform Thompson construction step by step on each node.
2. Compare the results of exact matching versus search patterns for the same API when applied to input xxabyy.
3. Design token rules for if, identifiers, and integers, and provide examples demonstrating longest match and tie-breaking behavior under equal length.
4. Test failing input for a regex, growing from short strings in a separate process with a timeout. Record how runtime changes with input length.

Summary

Classic regular expressions describe regular languages using a finite set of groupings and operators. Thompson construction systematically converts the syntax tree into a non-deterministic finite automaton (NFA). However, the actual performance and capabilities of real-world regex implementations depend heavily on the specific dialect and execution engine, so it's incorrect to generalize that "all regular expressions run in linear time."

The next chapter introduces stacks and context-free grammars, enabling the handling of recursive nesting that finite-state machines cannot express.