Overview
Thompson's construction recursively turns literals, concatenation, alternation, and repetition into NFA fragments with clear entry and exit states.
CoreSource checked
Thompson's Construction
Compiles a regular expression into an epsilon-NFA using small pattern fragments.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Intermediate
- Family
- Regex Compilation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
regex fragmentepsilon edgeconcatenationalternation
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(regex length)
Average
O(regex length)
Worst
O(regex length)
Space
O(regex length)
When to Use
- Use when language parsing needs regex fragment.
- Use when the input matches the assumptions behind regex Compilation.
When Not to Use
- Avoid when the grammar class does not match the parser's assumptions.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Compiles a regular expression into an epsilon-NFA using small pattern fragments
- Uses regex fragment and epsilon edge to guide the work.
- Produces parse tree.
Use Cases
- Language parsing
- Compiler front ends
- Structured text processing
Inputs
- Tokens or grammar
- Parser state
Outputs
- Parse tree
- Automaton
- Grammar table or parse result
Pseudocode
- 1.Prepare tokens, grammar rules, tables, or automaton states
- 2.Advance through tokens or grammar items according to the parsing rule
- 3.Create parse nodes, state transitions, or table entries when a rule applies
- 4.Report an error or return the completed structure
Canonical Example
- Input
- tokens = ['id', '+', 'id', '*', 'id'] with a tiny grammar or precedence table
- Output
- Parse tree
- Explanation
- Thompson's Construction applies regex fragment to produce parse tree.
Implementation Notes
- Report errors with token position and expected grammar symbols.
- Keep the regex fragment step separate enough to test independently.
- Keep lexical analysis separate from parsing unless the method explicitly combines them.
Common Pitfalls
- Ambiguity and left recursion must be handled according to the parser type.
- Test edge cases, not only clean examples.
- Mixing token positions, character offsets, and grammar states can produce misleading parse errors.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow grammar items, parser states, and consumed input as parsing progresses.
Input:ABABABCABAB
Window:ABAB
Step 1 of 4: Prepare tokens, grammar rules, tables, or automaton states
parsing-mechanismNotes
Thompson's Construction should be used with the assumptions and tradeoffs of regex Compilation in mind.
Sources (2)
What each reference supports for this entry.
Thompson Regular Expression Search
PaperOriginal reference for compiling regular expressions into automata fragments.
Open sourceIntroduction to Automata Theory, Languages, and Computation
BookAutomata textbook support for Thompson's Construction's state-machine construction, language recognition, and correctness model.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pagePrerequisite ofDFA Construction
Thompson construction produces an NFA that can then be determinized into a DFA.
Related Algorithms
Tags
ParsingAutomatonRegular ExpressionParser Generator