Lexingspec

Regular Languages

The formal reason the lexer is cheap: token structure needs no memory beyond a bounded state, so a finite automaton suffices. The reason the parser exists: nesting does need memory, and nothing regular can count.

The question

Why are regular expressions enough for tokens but hopeless for programs?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A *set of strings* defined by a pattern, and equivalently by a machine with finitely many states. The equivalence is the useful part: a regular expression is a specification and a finite automaton is an implementation of the same set, so writing patterns and getting a linear-time scanner is one mechanical step rather than a design problem.

What this phase may assume or do

A construct may be handled by the lexer only if recognising it requires no unbounded memory — that is, only if the set of strings it can produce is regular. Identifiers, numbers, operators, string literals and non-nesting comments qualify. Balanced brackets, nested comments and matched if/end pairs do not, and pushing one of them into the lexer produces a scanner that is quietly wrong on deep input.

Key points

Regular expressions, NFAs and DFAs describe exactly the same class of languages, and the constructions between them are mechanical.
The defining limitation is bounded memory: a finite automaton cannot count to an unbounded number.
Token structure is regular; program structure is not, and that single fact is the whole justification for the lexer/parser split.
Nested block comments and balanced brackets are the standard counterexamples — both need a counter or a stack.
Backreferences and recursive patterns make a "regex" non-regular, which is why some engines backtrack and some cannot.
ReDoS lives in the gap between a regular set and a backtracking engine: (a+)+b is regular and still exponential to match by backtracking.
Staying regular buys linear time, constant memory and restartability — the last of which is what incremental tooling depends on.

Three descriptions of one thing

A language is regular if it can be described by any one of three equivalent things: a regular expression, a nondeterministic finite automaton, or a deterministic finite automaton. Kleene's theorem says these describe exactly the same class of sets, and the constructions between them are mechanical — which is what makes [[finite-automata]] and [[nfa-vs-dfa]] practical topics rather than theoretical ones.

The defining limitation is memory. A finite automaton has a fixed number of states and no other storage, so whatever it needs to remember must fit in that fixed set. It can remember "I am inside a string literal" or "I have seen at least one digit". It cannot remember "I have seen seventeen open parentheses", because seventeen is unbounded and the state set is not.

Regular languages are closed under union, concatenation, Kleene star, intersection and complement, which is why a lexer specification is an alternation of patterns and still recognisable by one automaton. That closure is doing real work: it is why you can write twenty independent token patterns and have the tool combine them into a single machine that recognises all of them at once.

Regular: identifiers [A-Za-z_][A-Za-z0-9_]*, integers [0-9]+, floats, hex literals, operators, line comments, and string literals with escapes.
Not regular: balanced parentheses, nested block comments, a^n b^n, matched HTML or XML tags, and anything requiring a count.
Regular but you should not: keywords as twenty separate patterns. Correct, and a table lookup after one identifier pattern is smaller and makes contextual keywords possible.
Looks regular, is not: a "regular expression" with backreferences. (a+)b\1 is not a regular language, and the feature is why some engines backtrack.

Why the pumping argument matters in practice

implementationThe nested-comment row describes languages that support them: Rust, Swift, D and Haskell all do, each with a depth counter in the scanner. C and C++ do not — /* /* */ closes at the first */ in both standards, and GCC and Clang warn about the inner /* under -Wcomment precisely because the construct looks nested and is not.

The formal proof that balanced parentheses are not regular is the pumping lemma, and the intuition behind it is worth carrying even if the proof is not. Suppose an automaton with n states recognises balanced brackets. Feed it n + 1 open brackets. By the pigeonhole principle it must have entered some state twice, so it cannot distinguish the two depths at which that happened — and therefore it will accept a string with the wrong number of closing brackets.

The practical translation is a design rule: if recognising it requires counting to an unbounded number, it does not belong in the lexer. That single rule decides most of the lexer/parser boundary, and it is why nested block comments are the recurring counterexample. /* /* */ */ needs a depth counter, so a purely regular scanner closes the comment at the first */ and treats the rest of the file as code — producing a cascade of errors nowhere near the actual problem.

Languages that do support nested comments — Rust, Swift, D, Haskell — implement them with an explicit integer counter in the scanner. That is not a regular expression; it is a small pushdown automaton living inside the lexer, and it is a deliberate, documented departure from the regular-language boundary rather than an oversight.

What needs memory, and how much

Construct	Memory needed	Regular?	Handled by
Identifier	A single state: "in a word"	Yes	Lexer
Integer or float literal	A handful of states for the digit/dot/exponent phases	Yes	Lexer
String with escapes	Two states: in-string, after-backslash	Yes	Lexer
Line comment	One state until the newline	Yes	Lexer
Non-nesting block comment	Two states: in-comment, saw-star	Yes	Lexer
Nested block commentimplementation	An unbounded depth counter	No	A counter bolted into the lexer
Balanced parentheses	An unbounded stack	No	Parser
Matched if/else nesting	An unbounded stack	No	Parser

The word "regex" has drifted

What programming languages call a regular expression is usually not one. Backreferences (\1), lookahead and lookbehind assertions, and recursive patterns all describe languages outside the regular class. (a+)b\1 matches aabaa and not aabaaa, which requires remembering an unbounded count — precisely what a finite automaton cannot do.

This is not pedantry; it has a direct performance consequence. A genuinely regular pattern can be compiled to a DFA and matched in time linear in the input, with no backtracking, and that is what RE2 and Go's regexp package guarantee. A pattern with backreferences cannot, so PCRE, Java, Python and JavaScript use backtracking engines — and a backtracking engine on a pathological pattern takes exponential time. That is the ReDoS failure mode: a pattern like (a+)+b against a long run of as hangs a service.

For a lexer this settles the tool question. Token patterns are genuinely regular, so a DFA-based engine or a generated scanner is both correct and linear. Using a backtracking regex library to tokenise untrusted input imports a denial-of-service surface for no benefit, and the input a compiler reads is very often untrusted.

Regular, and not

1[A-Za-z_][A-Za-z0-9_]*      regular   -- identifier
2[0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?
3                            regular   -- float literal
4"([^"\\]|\\.)*"           regular   -- string with escapes
5//[^\n]*                    regular   -- line comment
6/\*([^*]|\*+[^*/])*\*+/     regular   -- NON-nesting block comment
7 
8(a+)b\1                      NOT regular -- backreference: unbounded memory
9\((?:[^()]|(?R))*\)          NOT regular -- recursive pattern: this is a parser
10(a+)+b                       regular set, exponential to match by backtracking

The last line is the important one: the *language* it describes is regular, so a DFA engine matches it in linear time. A backtracking engine still takes exponential time on aaaaaaaaaaaaaaaaaaaaaaaaaaX. Regularity is a property of the set; backtracking is a property of the engine, and ReDoS lives in the gap between them.

Where the boundary is drawn, and what it costs

Keeping the lexer regular buys three concrete things: linear time with constant memory, a scanner that can be restarted at any position given a small state, and the ability to combine independent patterns into one automaton mechanically. Those are exactly the properties an incremental language server needs, which is why the boundary has become *more* important rather than less as tooling has grown.

It costs syntax freedom, and the bill arrives in specific places. A language that wants nested comments has to bolt on a counter. A language with significant indentation has to synthesise tokens the character stream does not contain. A language whose string interpolation can contain arbitrary expressions — ` ${a + b} ` in JavaScript, f-strings in Python — has a construct that is genuinely recursive, and every implementation solves it with either a lexer mode stack or, as CPython did in 3.12, by making the tokenizer recurse.

The honest summary: the regular boundary is where the lexer *should* be, and every real language crosses it in one or two well-known places, each of which is a documented departure rather than an accident. Knowing which places those are in your language is most of what makes its scanner comprehensible.

How it works

The steps, in the order the compiler takes them.

Describe each token family as a pattern over characters, using only alternation, concatenation and repetition.
Check each pattern for unbounded counting; if it needs one, the construct is not lexical and belongs in the parser.
Combine the patterns by alternation into a single specification — closure under union guarantees the result is still regular.
Compile the combined pattern to an NFA by Thompson's construction, then to a DFA by subset construction, then minimise.
Add a priority rule for ties at the same match length, so that keywords and identifiers resolve deterministically.
Where the language genuinely requires more — nested comments, interpolation — add an explicit counter or mode stack and document it as a departure.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A language adds nested comments and the existing regular scanner closes at the first */, so the remainder of a commented-out block is parsed as code and produces dozens of errors far from the cause.
A tokenizer built on a backtracking regex library hangs on a crafted input, and a compiler-as-a-service endpoint becomes a denial-of-service target with a fifty-byte request.
A pattern for string literals does not handle the escaped-quote case, so "a\"b" terminates early and the rest of the line is lexed as code — a bug that only appears in strings containing quotes.
A hand-written scanner tries to handle nesting with a boolean rather than a counter, so depth two works and depth three silently does not.
An incremental language server cannot restart its scan mid-file because the scanner acquired unbounded state, and every keystroke rescans the whole file — felt as typing lag in large files rather than as a correctness bug.

When it helps

Deciding whether a proposed lexical feature is implementable as one: ask what it must count, and the answer falls out immediately.
Choosing a regex engine for input you do not control, where the linear-time guarantee is a security property rather than a performance one.
Explaining why a scanner is fast: linear time and constant memory are consequences of the formalism, not of tuning.

When it hurts

Insisting on strict regularity in a language that has already decided it wants nested comments or interpolation forces the feature into the parser, where the diagnostics are worse.
Treating the regular/non-regular line as a specification for what a lexer may contain, rather than as a description of what is cheap, produces arguments about purity instead of about cost.

What it costs

Every one of these is paid by something.

Restricting the lexer to regular constructs buys linear time, constant memory and a restartable scan, and costs syntax the language might have wanted — nested comments and recursive interpolation both have to be bolted on.
Using a backtracking regex engine buys backreferences and lookaround and costs the linear-time guarantee, which on untrusted input is a denial-of-service exposure rather than a slow path.
Compiling patterns to a DFA buys linear matching and costs construction time and, in the worst case, exponential table size — which is exactly the trade [[nfa-vs-dfa]] is about.

What else you could do

What a different compiler or language does instead, and when that is better.

A DFA-based regex engine such as RE2 or Go's regexp, which guarantees linear time by refusing to implement backreferences. The right default for untrusted input; the wrong choice when you genuinely need the features it drops.
Recognising the whole language with one context-free grammar and no lexer, which handles context-dependent lexical structure and gives up the linear-time constant-memory scan.
A hybrid: a regular core with an explicit mode stack for interpolation and a depth counter for comments. This is what most real scanners are, and it is a pragmatic departure rather than a formalism.

See it for yourself

The flag, dump or tool that shows you this directly.

flex -v grammar.l reports the number of DFA states and the table sizes your patterns compiled to — a direct measurement of the automaton this lesson describes.
re2c --emit-dot patterns.re | dot -Tsvg renders the generated automaton, so you can see the states a pattern produced.
go doc regexp states the linear-time guarantee explicitly and explains that backreferences are absent because of it; RE2 documentation makes the same argument at length.
In Python, re is backtracking: time re.match(r"(a+)+b", "a" * 30) and compare with the same pattern in Go's regexp, which returns immediately.
gcc -Wcomment x.c warns about /* inside a comment — the compiler telling you it is not nesting, which is the regular boundary made visible.

Plausible wrong readings

Stated the way a confident engineer states them.

"Regular expressions are the same as what my language calls regex." Backreferences, lookahead and recursion all leave the regular class, and the features that leave it are the features that force backtracking.
"Regular means simple patterns." Regularity is about memory, not complexity. A float literal with an optional exponent is regular; two nested brackets are not.
"If it needs a stack it needs a parser." It needs unbounded, stack-shaped memory. A depth counter is enough for nested comments, which is why some lexers implement them.
"ReDoS is a bug in the pattern." It is an interaction between a pattern and a backtracking engine. The same pattern on a DFA engine is linear.

Misconceptions

The claim, and what is actually true.

Regular expressions cannot parse HTML because HTML is complicated.

Because matched tags require unbounded counting. The same argument applies to any nesting, however simple the rest of the format is.

A DFA-based regex engine is slower because it has to build a table.

It builds the table once and matches in linear time with no backtracking. The construction cost is real and is paid at compile time in a lexer.

Nested comments prove the lexer must be a parser.

They prove it needs a counter. The languages that support them add one integer and stay otherwise regular, which is a much smaller departure than a stack.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A language is regular if a machine with a fixed number of states can recognise it — no counting, no stack. Identifiers, numbers, operators and simple comments all qualify, which is why a lexer is fast and simple. Nesting does not qualify, because you cannot count to an unbounded depth with a fixed number of states, and that is why the parser exists.

practical

Use the counting test when deciding where a feature goes: if recognising it requires remembering how many of something you have seen, it is not lexical. And when tokenising input you do not control, use a DFA-based engine — RE2 or Go's regexp — because a backtracking engine turns a regular pattern into a denial-of-service surface, and a compiler service reads exactly the input an attacker chooses.

advanced

The property that has become most valuable is one nobody optimised for originally: restartability. Because a DFA's entire state is one small value, a scanner can be resumed at any position given only the state it was in, which is what lets an editor rescan a single edited line instead of a whole file. Everything that pushes the lexer past regular — a mode stack for interpolation, a comment depth counter, Python's indentation stack — enlarges that resumption state, and enlarging it enough makes incremental rescanning impractical. tree-sitter's design takes this seriously: it constrains what an external scanner may keep and requires it to be serialisable, precisely so that resumption stays cheap. That is the regular-language argument reappearing forty years later as a tooling requirement rather than a performance one.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specKleene's theorem, the closure properties and the pumping lemma are results about formal languages and hold regardless of tooling. The claim that a specific construct in a specific language is regular depends on that language's definition: block comments are regular in C and not in Rust, because Rust chose to make them nest.

implementationThe linear-time guarantee described here is RE2's and Go's regexp, which achieve it by omitting backreferences. Python's re, Java's java.util.regex, PCRE and JavaScript's built-in engine all backtrack and are exponential on adversarial input; Java added a limited automaton path and JavaScript engines have added specific mitigations, so the exposure differs by version and by pattern.

typicalThe claim that mainstream lexers stay within the regular class is true of the core token families and false at exactly two or three points per language — interpolation, nested comments and significant indentation. Treat "the lexer is a finite automaton" as an accurate description of the design and an approximate description of the code.

If you were asked this in an interview

Why can a regular expression not match balanced parentheses? Give the pigeonhole argument.
Your language wants nested block comments. What does that do to the lexer?
Explain ReDoS to someone who thinks the pattern is at fault.

Connections

DSAstring naive-string-matching

Securityinput-validation fuzzing