Regular Expressions for Lexing

A regular expression is a formula, built from a small alphabet of operators, that denotes a set of strings called its language. Formally, over an alphabet $\Sigma$, the regular expressions and the languages they denote are defined by structural induction:

• $\varepsilon$ denotes $\{\varepsilon\}$, the language containing only the empty string.
• For each symbol $a \in \Sigma$, the expression $a$ denotes $\{a\}$.
• If $r$ and $s$ are regular expressions denoting languages $L(r)$ and $L(s)$, then:
• $rs$ (concatenation) denotes $L(r)L(s) = \{xy \mid x \in L(r), y \in L(s)\}$.
• $r \mid s$ (alternation, or union) denotes $L(r) \cup L(s)$.
• $r^*$ (Kleene star) denotes $L(r)^* = \bigcup_{i \ge 0} L(r)^i$, i.e., zero or more concatenations of strings from $L(r)$.

Everything else — `+` (one or more), `?` (optional), character classes like `[a-z]`, the wildcard `.`, bounded repetition `{2,4}` — is syntactic sugar: convenient shorthand that expands into the three primitive operators above. For instance $r^+ \equiv rr^*$ and $r? \equiv r \mid \varepsilon$. This is an important discipline: sugar makes expressions readable, but the expressive power of the notation is fixed by concatenation, alternation, and star alone. The set of languages describable this way is called the regular languages. A foundational theorem of formal language theory — due independently to Kleene's characterization of finite automata — states that a language is regular if and only if some regular expression denotes it, and if and only if some finite automaton accepts it. This three-way equivalence is why regular expressions are the right notation for lexing: they are declarative (you state what the tokens look like) while finite automata are operational (they say how to check membership efficiently), and the theorem guarantees a mechanical, complexity-bounded translation between the two — the subject of Building Scanners with Finite Automata. Regular languages are also exactly the languages recognizable with a constant amount of memory (no stack, no counters), which matches the resource profile of a lexer that must process gigabytes of source text in a single left-to-right pass.

Step 1 — Write one regular expression per token class. A lexical specification is a list of pairs $(r_i, \text{action}_i)$: a regular expression and what to do when it matches (usually: emit a token of a given kind). ``` DIGIT = [0-9] LETTER = [a-zA-Z_] NUMBER = DIGIT+ ('.' DIGIT+)? IDENT = LETTER (LETTER | DIGIT)* KEYWORD_IF = 'if' WHITESPACE = (' ' | '\t' | '\n')+ ```

Step 2 — Resolve ambiguity between rules. Two strings can match more than one pattern (`if` matches both `IDENT` and `KEYWORD_IF`), and a single starting position can extend a match multiple ways (`ifx` could stop the `if` match early). Two disambiguation conventions, used by essentially every lexer generator, remove all ambiguity: 1. Longest match (maximal munch): among all rules that match a prefix of the remaining input, choose the one that matches the longest prefix. 2. Rule priority: if multiple rules match the same longest prefix, choose whichever rule was listed first in the specification. These two rules together turn "any regular expression might match" into "there is exactly one correct token" at every position, which is what makes automatic scanner generation possible.

Step 3 — Combine the rules into a single recognizer. Conceptually, the whole token table is merged into one big regular expression $r_1 \mid r_2 \mid \cdots \mid r_n$, tagged so the recognizer remembers which alternative fired. This combined expression is then compiled to a finite automaton (foreshadowed further in Building Scanners with Finite Automata); for now, treat the recognizer as a black box that, given input text and a position, returns the longest prefix matched and which rule matched it. The driver loop that uses this recognizer to tokenize a whole file is the same regardless of how the recognizer is built: ``` function TOKENIZE(input): tokens = [] pos = 0 n = length(input) while pos < n: (matchLength, ruleIndex) = LONGEST_MATCH(input, pos) // step 2's logic if matchLength == 0: error("no token matches at position", pos) lexeme = input[pos : pos + matchLength] if rules[ruleIndex].action != SKIP: // e.g. skip whitespace/comments tokens.append( Token(kind = rules[ruleIndex].kind, text = lexeme) ) pos = pos + matchLength tokens.append( Token(kind = EOF, text = "") ) return tokens function LONGEST_MATCH(input, pos): best_len = 0 best_rule = NONE for i in 0 .. length(rules) - 1: // rules in priority order len = MATCH_LENGTH(rules[i].regex, input, pos) // longest prefix from pos matched by rule i if len > best_len: best_len = len best_rule = i // strictly greater keeps the earlier-listed rule on ties (rule priority) return (best_len, best_rule) ``` `MATCH_LENGTH` is exactly the operation a compiled finite automaton performs in a single linear scan; writing it directly from the regular-expression definition (by trying every possible split at every alternation and every star) would be exponential, which is precisely the efficiency problem automaton compilation solves. The figure below shows the whole pipeline: source text flows through the combined recognizer built from the per-class regular expressions, and out comes a token stream.

Time and space of the notation itself. A regular expression of length $m$ (counting symbols and operators) can be compiled to a nondeterministic finite automaton (NFA) with $O(m)$ states via Thompson's construction, and that NFA can be converted to a deterministic finite automaton (DFA) with at worst $O(2^m)$ states in the theoretical worst case, though in practice — and always for the subset of expressions used in real lexers — the DFA is small and $O(m)$-ish in size. Once a DFA exists, matching an input of length $n$ against it takes $O(n)$ time with $O(1)$ additional memory beyond the automaton's fixed table, because each input character causes exactly one table lookup and one state transition. This $O(n)$ scanning bound is the entire reason regular expressions are the tool of choice for lexing: a compiler must process source files of arbitrary size in a single pass with a bounded memory footprint, and only a recognizer with a fixed, finite set of states can guarantee that.

Why longest-match plus priority is correct (uniqueness). The disambiguation rules are not arbitrary conveniences; they are what make tokenization a total function from input to token stream. Consider the alternative — shortest match, or no fixed tie-break. Then `if` could be scanned as `IDENT("i")` followed by `IDENT("f")`, or as `KEYWORD_IF`, and there would be no principled way to choose, so the language's grammar could not be defined without also fixing a scanning convention. By always preferring the longest prefix that matches any rule, and breaking remaining ties by earliest-declared rule, every input string is partitioned deterministically into a unique sequence of lexemes (as long as the specification has no "dead end," i.e., some rule matches every stretch of input, typically guaranteed by an error/catch-all rule). This is exactly the postulate lexer generators rely on to prove that their generated scanners are deterministic total functions on their input alphabet.

What regular expressions cannot do — the honest limitation. Regular languages are closed under union, concatenation, and Kleene star, but they are not closed under arbitrary nesting or counting. The pumping lemma for regular languages formalizes this: for any regular language $L$, there is a constant $p$ (the "pumping length") such that every string $w \in L$ with $|w| \ge p$ can be split as $w = xyz$ with $|xy| \le p$, $|y| \ge 1$, and $xy^iz \in L$ for all $i \ge 0$. Applying this to the language of balanced parentheses $\{a^n b^n \mid n \ge 0\}$: choose $w = a^p b^p$; any decomposition forced by the lemma puts $y$ entirely inside the $a$'s, so pumping $y$ produces a string with more $a$'s than $b$'s, which is not in the language — a contradiction. Hence no regular expression can match balanced parentheses of arbitrary depth, and lexers correctly leave nested structure (matching brackets, matching quotes across balanced escapes, matching tags) to the parser's context-free grammar, discussed once the pipeline moves past lexing.

Consider a miniature language with this token table (priority = order):

Trace `TOKENIZE` on the input string `"if x1=x1+10"`:

The crucial moment is position 0: without the tie-break rule, `if` is genuinely ambiguous between `IDENT` and the keyword `IF`, because both match a prefix of length 2. Listing `IF` before `IDENT` in the specification is what forces the correct outcome — this is exactly why lexer generators document that keyword rules must precede the general identifier rule. At position 5, longest match is what prevents `ASSIGN` from stealing only `=` incorrectly or `IDENT` from over-consuming into `=`; here only one rule matches, so the choice is forced, but the same mechanism is what correctly distinguishes, say, `<=` (length 2) from `<` (length 1) when both rules exist and the input actually contains `<=`.

Regular expressions moved from a tool of pure mathematical logic (finite automata theory in the 1950s) to a piece of everyday engineering infrastructure once Thompson's construction made compiling them practical, and Lex/Flex made that compilation available to any compiler writer without hand-building automata. Every modern parser-generator ecosystem — ANTLR, Bison-paired scanners, hand-rolled lexers in production compilers like those for C, Java, Go, and Rust — still expresses its token classes in essentially the notation Kleene defined in 1951.

Regular expressions specify the lexical layer of essentially every programming-language compiler and interpreter: GCC and Clang's C/C++ front ends, the CPython and Java tokenizers, and JIT compilers for JavaScript engines like V8 all begin with a hand-written or generated scanner built from regular-expression token rules. Tools such as Lex/Flex, ANTLR's lexer grammars, and Python's `re`-based tokenizers all rely on the same three-operator core described here. Beyond compilers, the same notation (extended with practical sugar) powers text search (`grep`, `sed`, `awk`), input validation (email and phone-number formats), network intrusion detection systems that scan packet payloads for signature patterns, log-processing pipelines, and syntax highlighting in editors and IDEs — all applications where a bounded-memory, single-pass, linear-time scan over text is exactly the right computational tool.

:::quiz[If a "whitespace" rule is mistakenly written as `[ \t]*` instead of `[ \t]+`, what bug can result?]

• The scanner rejects all valid whitespace
• The scanner may match a zero-length token and fail to advance, hanging the lexer ✓
• The DFA becomes exponentially large
• Keywords get treated as identifiers

Ask the tutor: How does Thompson's construction actually turn a regular expression into a finite automaton, step by step?