Regular Expressions for Scanning

A scanner needs a precise, machine-readable way to say what each token looks like. "An integer is one or more digits" is fine for a human, but the scanner-generator needs a notation it can compile into an automaton. That notation is the regular expression — the same regular expressions from formal language theory, put to work as the specification language for every token pattern in the compiler. This page is about writing those patterns well: the operators, the art of building them up as named regular definitions, and the crucial line between the clean formal object and the messier "regex" of everyday programming.

The operators, and what they build

Over an alphabet \Sigma, a regular expression denotes a set of strings (a language). Four constructions generate every regular language, from just the single-character expressions and \varepsilon (the empty string):

Expression	Name	Language it denotes
r \mid s	union / alternation	a string matching r or s
r\,s	concatenation	an r followed by an s
r^{*}	Kleene star	zero or more rs in a row
r^{+}	positive closure	one or more rs (= r\,r^{*})
r?	optional	zero or one r (= r \mid \varepsilon)

Precedence, highest to lowest, is star/plus/? > concatenation > alternation, and parentheses override it. So ab^{*}\mid c means \big(a(b^{*})\big)\mid c — an a then any number of bs, or else a lone c. Two abbreviations pull their weight in real specs: a character class [abc] is shorthand for a\mid b\mid c, and a range [a\text{-}z] for the whole alphabet's worth of alternatives.

Regular definitions: naming the pieces

Real token patterns get unwieldy fast, so we build them up as a sequence of regular definitions: named regular expressions, where each definition may use the names defined before it. This is nothing more than "let-bindings for regexes", and it is exactly how a lex specification reads. Here is the canonical set for identifiers and numbers:

\begin{aligned} \mathit{letter} &\;\to\; \mathtt{A} \mid \mathtt{B} \mid \cdots \mid \mathtt{z} \mid \mathtt{\_}\\ \mathit{digit} &\;\to\; \mathtt{0} \mid \mathtt{1} \mid \cdots \mid \mathtt{9}\\ \mathit{id} &\;\to\; \mathit{letter}\;(\,\mathit{letter} \mid \mathit{digit}\,)^{*}\\ \mathit{digits} &\;\to\; \mathit{digit}\;\mathit{digit}^{*} \;=\; \mathit{digit}^{+}\\ \mathit{number} &\;\to\; \mathit{digits}\;(\,.\,\mathit{digits}\,)?\;\big(\,\mathtt{E}\,(\mathtt{+}\mid\mathtt{-})?\,\mathit{digits}\,\big)? \end{aligned}

Read \mathit{number} aloud: a run of digits, then an optional fractional part (.\,\mathit{digits})?, then an optional exponent \big(\mathtt{E}(\mathtt{+}\mid\mathtt{-})?\,\mathit{digits}\big)?. That one definition matches 60, 3.14, 6.02E23 and 1E-9 — every optional group and the two ?s are earning their place. Because \mathit{number} is spelled out of the smaller names, it stays readable.

Patterns for the tokens you actually meet

A few token classes come up in nearly every language; committing their regular definitions to memory is worth the effort:

Token	Regular definition	Matches
integer	[0\text{-}9]^{+}	`0`, `60`, `2048`
identifier	[A\text{-}Za\text{-}z\_][A\text{-}Za\text{-}z0\text{-}9\_]^{*}	`x`, `rate2`, `_tmp`
float	[0\text{-}9]^{+}\,.\,[0\text{-}9]^{+}	`3.14`, `0.5`
line comment	\mathtt{//}\,[^\backslash n]^{*}	`// to end of line`
block comment	\mathtt{/}\;\ldots\;\mathtt{/}	see the warning below

The C-style line comment \mathtt{//}[^\backslash n]^{*} is a clean regular expression — slash, slash, then any run of non-newline characters. The block comment /* … */ is the famously awkward one: written naïvely as \mathtt{/*}\,.^{*}\,\mathtt{*/} with a greedy star it will swallow everything up to the last */ in the file, merging two separate comments into one. The correct regular definition forbids the closing delimiter inside the body — roughly "any character that is not a *, or a * not followed by /, repeated". It is expressible as a regular language; it is just fiddly, which is why lex lets you write it as a small start-condition sub-machine instead.

The lex specification format: pattern → action

A scanner generator like lex/flex takes a file of rules, each a pattern paired with an action — a fragment of code to run when that pattern wins the match. The generator compiles all the patterns together into one finite automaton (the subject of the next few pages) and wraps it in the longest-match, first-rule-wins driver. Conceptually a rule list looks like this:

[ \t\n]+ { /* whitespace: do nothing, emit no token */ } if|else|while { return keyword(yytext); } // listed BEFORE id, so it wins [A-Za-z_][A-Za-z0-9_]* { return install_id(); } [0-9]+ { return install_num(); } "//".* { /* line comment: skip */ } "<=" { return LE; } "<" { return LT; } . { lexical_error(yytext); } // catch-all: any single char

Every convention from the previous page is visible here: the keyword rule sits above the identifier rule (priority), <= is a separate rule that longest-match prefers over <, whitespace and comments have empty-emitting actions, and the final . is a deliberate lexical-error catch-all. yytext is the matched lexeme; the action decides what token — if any — to hand the parser.

Matching a pattern, in code

You do not need a whole generator to feel how this works. Below, two token patterns — identifier and number — are written as hand-rolled matchers that return the length of the longest prefix they match at a position (or 0 for no match). This is precisely the primitive a longest-match driver calls repeatedly.

// Returns the length of the longest prefix of s (from index i) matching the pattern, or 0. function matchIdentifier(s: string, i: number): number { const isL = (c: string) => /[A-Za-z_]/.test(c ?? ""); const isLD = (c: string) => /[A-Za-z0-9_]/.test(c ?? ""); if (!isL(s[i])) return 0; // must START with a letter or _ let j = i + 1; while (j < s.length && isLD(s[j])) j++; // then letters/digits/_ (the star) return j - i; } // number -> digits ('.' digits)? (an integer or a simple float) function matchNumber(s: string, i: number): number { const isD = (c: string) => c !== undefined && c >= "0" && c <= "9"; if (!isD(s[i])) return 0; let j = i + 1; while (isD(s[j])) j++; // digits+ if (s[j] === "." && isD(s[j + 1])) { // optional . digits+ j += 2; while (isD(s[j])) j++; } return j - i; } const tests = ["rate2", "3.14", "_tmp", "60", "007bond", "9lives"]; for (const t of tests) { console.log(`${t} -> id:${matchIdentifier(t, 0)} num:${matchNumber(t, 0)}`); }

Look at 9lives: matchIdentifier returns 0 (it does not start with a letter) while matchNumber returns 1 (just the 9) — so a driver would emit a num and then start a fresh match at lives. And 007bond matches num for length 3, then id for the rest: the patterns compose to tokenise the whole string.

Tokens are, by design, flat: a number, a name, an operator — none of them nest. Regular languages are precisely the languages a finite-memory machine can recognise, and a finite automaton is astonishingly cheap: constant memory, one pass, linear time. That is a perfect fit for token structure, and it is why we deliberately stop at regular power for the scanner. The moment a construct nests — balanced parentheses, { } blocks, matching if…else — you have stepped beyond regular languages: no finite automaton can count the open brackets to match them against the closed ones (that needs a stack, i.e. a context-free grammar and a parser). Splitting the front end into "regular scanner + context-free parser" is not an accident of history; it is drawing the line exactly where the cheap model runs out of power.

The /…/ regexes in Perl, Python, JavaScript and friends look like the formal object but have quietly grown teeth that escape the regular languages entirely:

Backreferences like (a+)\1 ("some as, then the same run again") match a non-regular language — no finite automaton can do it. The instant you use one, you are no longer in regular-language land and the linear-time guarantee can collapse.
Greedy vs lazy. The star {}^{*} in these engines is greedy — it grabs as much as possible, then backtracks — whereas *? is lazy and grabs as little as possible. For a comment body, /\*.*\*/ (greedy) eats to the last */; /\*.*?\*/ (lazy) stops at the first. In the formal model there is no such knob — a regular expression denotes a set of strings with no notion of "how much" a repetition consumes; greediness is a property of the matcher's search strategy, resolved for us by the scanner's longest-match rule.

For scanner specifications, stick to the honest regular subset (union, concat, star, plus, optional, classes). That is all a token needs, and it is all that compiles to a fast, backtracking-free automaton.