Regular Expressions

A regular expression (RE) is a formula that describes a set of strings — called a regular language. In compiler design, every token type has a corresponding regular expression that defines what text can match it.

For example:

• The regular expression [a-zA-Z_][a-zA-Z0-9_]* describes all valid C identifiers.
• The regular expression [0-9]+ describes all unsigned integers.

Regular expressions are important because:

1. They are precise — no ambiguity about what matches.
2. They are mechanically convertible to finite automata, which run in O(n) time.
3. They form the theoretical backbone of every lexer generator (flex, ANTLR, re2c).

Alphabet and Language

Before defining operations, two terms matter:

• Alphabet (Σ) — the set of all characters the language can use. For most programming languages Σ = ASCII or Unicode.
• Language (L) — a (possibly infinite) set of strings over Σ. A regular expression denotes a language.

Every regular expression is built from three primitive operations applied to base symbols:

1. Union (written r | s or r + s)

Denotes all strings that match r OR all strings that match s.

Example: a | b matches the strings {a, b} — nothing else.

Example: cat | dog matches "cat" or "dog".

2. Concatenation (written rs or r · s)

Denotes all strings formed by taking any string from L(r) and appending any string from L(s).

Example: ab matches only "ab" — 'a' followed by 'b'.

Example: (a|b)(c|d) matches {ac, ad, bc, bd}.

3. Kleene Star (written r*)

Denotes zero or more repetitions of any string that matches r.

Example: a* matches {ε, a, aa, aaa, aaaa, …} — zero or more 'a's.

Example: (ab)* matches {ε, ab, abab, ababab, …}.

Operator Precedence (highest to lowest)

So ab*|c parses as (a(b*))|c, not a(b*(|c)).

The three core operations are all you need theoretically, but practical lexers use shorthand to keep patterns readable:

Example 1 — Unsigned Integer

Language: strings of one or more digits.

Example 2 — C Identifier

Language: starts with a letter or underscore, followed by zero or more letters, digits, or underscores.

Example 3 — Floating-Point Literal

Language: optional minus sign, one or more digits, a dot, one or more digits.

Example 4 — C String Literal

Language: a double-quote, followed by any non-quote characters (simplified), followed by a closing double-quote.

Example 5 — C Keyword OR Identifier

In a real lexer, keywords are listed explicitly (higher priority) and identifiers catch everything else:

In a compiler's lexer, regular expressions do not run directly. They go through a standard pipeline:

Each step is mechanical and lossless — the minimal DFA accepts exactly the same strings as the original regular expression, and it runs in O(n) time.

This pipeline is what tools like flex, ANTLR, and re2c implement for you when you write a lexer specification.

Regular Languages and the Chomsky Hierarchy

Regular expressions describe exactly the regular languages — the Type 3 languages in the Chomsky Hierarchy. They are less powerful than context-free grammars (CFGs) but sufficient for all lexical-level patterns:

This is exactly why compilers use two separate phases: the lexer (regular expressions / DFA) for tokens, and the parser (CFG / PDA) for structure.

Thompson's Construction is the standard algorithm for converting a regular expression into an NFA. It works inductively — it builds a tiny NFA for each base symbol and combines them using rules that mirror the RE operators exactly.

Key Properties of Every Thompson NFA

Every NFA produced by Thompson's Construction has exactly three guarantees:

These properties make composition predictable — you can always wire two sub-NFAs together cleanly.

The Four Construction Rules

Rule 1 — Single character a

Create exactly two states and connect them with a single labelled edge. No ε-edges are needed.

Rule 2 — Union r | s

Add a new start state and a new accept state. Use four ε-edges to run both sub-NFAs in parallel — the machine non-deterministically picks one path.

Purple boxes represent the two complete sub-NFAs. Arrows into a box enter at its start state; arrows out of a box leave from its accept state.

Rule 3 — Concatenation r · s

No new states are needed. A single ε-edge chains the accept of r directly into the start of s, so they run one after the other.

Rule 4 — Kleene Star r*

Add a new start state and a new accept state. Four ε-edges implement the four behaviours of *: enter, skip (zero times), loop (repeat), and exit.

The dotted line between start_r and accept_r represents the entire NFA body for r (its internal states and transitions, whatever they are).

Worked Example — Convert (a|b)* to NFA

We parse the expression bottom-up and apply the rules in this order:

Step 1 — NFA for a

Apply Rule 1: two states, one 'a' edge.

Step 2 — NFA for b

Apply Rule 1 again: two new states, one 'b' edge.

Step 3 — NFA for a | b

Apply Rule 2 (Union): add new start N4 and new accept N5. Draw four ε-edges to wire both sub-NFAs in parallel.

Reading the diagram:

• N4 non-deterministically jumps to N0 (try the 'a' path) or N2 (try the 'b' path).
• Whichever path matches, its accept state flows into N5 via ε.

Step 4 — NFA for (a|b)*

Apply Rule 4 (Kleene Star): add new start N6 and new accept N7. Draw four ε-edges:

Tracing the NFA on Input "ab"

We track the ε-closure of the active state set after every symbol.

Tracing the NFA on Input "ba"

Tracing the NFA on ε (empty string)

Summary of Thompson's Construction

A regular expression of length m produces an NFA with at most 2m states — one pair per character or operator. Thompson's Construction always runs in O(m) time and produces a compact NFA ready for subset construction.