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

The gatekeeper can now recognize hand-drawn state diagrams. The next task is to automatically generate a state machine from a single regular expression rule and enforce the worst-case performance boundary.

The circular markers on the wall can finally be generated from a text rule. Concatenation, alternation, and repetition (like three casting operations) are combined by Thompson construction into a non-deterministic finite automaton (NFA). But in reality, regex tools don't all stick to classic regular languages, nor do they all use the same matching 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 $\Sigma$, the core constructions of classic regular expressions are:

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

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

$$ R^+ = RR^*,\qquad R? = (R|\varepsilon). $$

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 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. Semantic Matching Is Not a Single Rule

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.

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

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 subsequent text to exactly match previously captured content, such as the concept pattern (.*)\1. Since finite automata cannot remember arbitrary-length captured values, such features typically fall outside the scope of regular languages.

Some lookaheads 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 greedy 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 only change the order in which attempts are made.

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 parsing precedence 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.

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. Write long-failure input tests for a regular expression in your project, and record how execution time scales 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.