From Regular Expressions to Finite Automata
What You'll Learn
You'll learn how to systematically convert regular expression patterns into executable finite automata that can efficiently recognize tokens in a lexical analyzer.
The Bridge Between Patterns and Machines
Regular expressions are patterns that describe token structures (like identifiers, numbers, or keywords). But a compiler can't directly "run" a regex—it needs a concrete machine to process input character by character. That machine is a finite automaton.
The conversion happens in two stages:
Stage 1: Regular Expression → NFA
Using Thompson's Construction, each regex operator gets translated into a small NFA fragment:
- Single character
a: Two states connected by an edge labeleda - Concatenation
ab: Chain the NFA forato the NFA forb - Alternation
a|b: Create parallel paths with ε-transitions - Kleene star
a*: Add a loop with ε-transitions for zero-or-more repetition
These fragments connect together to build a complete NFA matching the entire regex.
Stage 2: NFA → DFA
The resulting NFA often has nondeterminism—multiple possible transitions from a state, or ε-transitions that move without consuming input. This makes direct simulation slow.
We use the subset construction algorithm to convert the NFA into an equivalent DFA where each state represents a set of NFA states. The DFA has exactly one transition per input symbol from each state, making it much faster to execute.
Why This Matters
Once you have a DFA, recognizing tokens becomes trivial: start at the initial state, follow exactly one transition per input character, and check if you end in an accepting state. This deterministic, table-driven approach is what makes lexical analysis blazingly fast.
Key Takeaway: Converting regex → NFA → DFA transforms declarative token patterns into efficient, executable state machines that power the first phase of compilation.