Lexingimplementation

Implementing a Lexer

A hand-written scanner is a while loop, a switch on the first character, and one character of lookahead. A generated one is a DFA table. Both implement maximal munch; they differ in who writes the automaton and in how good the error messages are.

The question

How do I actually write a lexer, and when is a generator worth the dependency?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A scanner is a function from (source, position) to (token, new position), iterated until the input is exhausted. The state between calls is a single integer offset — that is the whole reason the phase is cheap, and it is what "regular" buys you in practice: no stack, no backtracking beyond a bounded amount, one pass.

What this phase may assume or do

A scanner must make progress on every input, including invalid ones: after an error it must consume at least one character before continuing, or it loops forever. It may look ahead a bounded number of characters and must be able to un-consume them, but it may not consult any structure a later phase builds — the moment it does, it is no longer a function of the source text alone.

Key points

  • A hand-written scanner is a loop, a switch on the first character, a per-family sub-scanner, and an operator table tried longest-first.
  • Scan identifiers to full extent and then consult the keyword table; the order is what makes iffy one token.
  • Maximal munch needs the ability to back up, implemented as a last-accepting-state pointer in a DFA or as explicit lookahead by hand.
  • C's a---b lexes as a, --, -, b — maximal munch working correctly and producing a program nobody meant.
  • Every unmatched character must still advance the position, or the compiler hangs on invalid input.
  • Production compilers hand-write scanners for diagnostics, tunability and incremental restart, not for speed; generators remain the right answer for DSLs.

The loop

A hand-written scanner has the same shape in every language. Skip whitespace. Record the start offset. Switch on the current character. Each branch consumes as much as its pattern allows and returns a token with the span. That is essentially all of it; the rest is the operator table and the error handling.

The two details that matter are both visible in the code below. First, the identifier branch runs to completion *before* the keyword table is consulted, which is what makes iffy one identifier. Second, the number branch peeks one character past the . before committing, because 1..5 in a language with a range operator must lex as 1, .., 5 rather than as a malformed float. That one-character lookahead is the difference between a scanner that handles real syntax and one that does not.

The core of a hand-written scanner
1function nextToken(src: string, i: number): Token {
2  while (i < src.length && isSpace(src[i])) i++
3  if (i >= src.length) return { kind: 'EOF', text: '', start: i, end: i }
4 
5  const start = i
6  const c = src[i]
7 
8  // Words: scan to the end, THEN decide keyword vs identifier.
9  if (isAlpha(c) || c === '_') {
10    while (i < src.length && isIdentChar(src[i])) i++
11    const text = src.slice(start, i)
12    return { kind: KEYWORDS.get(text) ?? 'IDENTIFIER', text, start, end: i }
13  }
14 
15  // Numbers: one character of lookahead past the '.' before committing,
16  // so that "1..5" lexes as 1 .. 5 and not as a malformed float.
17  if (isDigit(c)) {
18    while (i < src.length && isDigit(src[i])) i++
19    if (src[i] === '.' && isDigit(src[i + 1])) {
20      i++
21      while (i < src.length && isDigit(src[i])) i++
22    }
23    return { kind: 'NUMBER', text: src.slice(start, i), start, end: i }
24  }
25 
26  // Operators: longest first, or '>=' lexes as '>' then '='.
27  for (const [text, kind] of OPERATORS_LONGEST_FIRST) {
28    if (src.startsWith(text, i)) {
29      return { kind, text, start, end: i + text.length }
30    }
31  }
32 
33  // No rule matched. Consume one character so the scan terminates.
34  return { kind: 'ERROR', text: c, start, end: i + 1 }
35}

The final branch is the one people leave out, and leaving it out is how a compiler hangs on a file with a stray backtick. Emitting an error token and advancing by one guarantees termination and lets the rest of the file still be scanned, so the user gets more than one diagnostic per run.

Maximal munch, and the backing-up problem

Maximal munch says: at each position, take the longest sequence of characters that forms a valid token. It is not a law of nature — it is a disambiguation rule the language chooses — but essentially every language chooses it, because the alternative makes >= and 42 both ambiguous.

Implementing it exactly requires the scanner to be able to *back up*. Consider a language with .. and ... and a float syntax. Reading 1.. the scanner has consumed a digit, a dot, and now sees another dot; the longest valid token starting at position 0 was just 1, so it must return to position 1. A DFA implements this by remembering the last position at which it was in an accepting state and rewinding to it on failure — the "last accept" pointer that every table-driven scanner carries.

Backing up costs time, and it is the thing generated scanners report on. flex --backup writes a lex.backup file listing every state from which the scanner may need to rewind, and eliminating them by rewriting the patterns is a standard optimisation for a scanner in a hot loop. A hand-written scanner solves the same problem with explicit lookahead, which is why the number branch above peeks at src[i + 1] instead of committing.

Maximal munch in C: a---b is not what it looks like
a---b

Read it asThe lexer took the longest match without consulting the parser, and the parser is then obliged to make sense of a-- - b. This is maximal munch working exactly as specified and producing a program nobody meant, which is the standing argument that the rule is a trade rather than a truth.

Hand-written or generated

implementationThe "used by" row reflects the current sources of those projects: Clang's Lexer.cpp, rustc's rustc_lexer, Go's cmd/compile/internal/syntax/scanner.go and CPython's Parser/tokenizer.c are all hand-written. This is a change from the 1980s and 1990s, when generated scanners were the norm; the shift was driven by diagnostics and by incremental tooling, not by performance.

A generator — lex, flex, re2c, or the lexer half of ANTLR — takes a list of regular expressions with actions and emits a table-driven DFA. The tables are constructed by exactly the pipeline [[regular-languages]], [[finite-automata]] and [[nfa-vs-dfa]] describe, and the generated code is fast and correct by construction.

Essentially every production compiler written in the last twenty years hand-writes its lexer anyway, and the reasons are worth knowing because they are the same reasons that show up for parsers. Diagnostics: a generated scanner reports "unrecognised character" and a hand-written one can say "unterminated string literal started here" with two spans. Performance: hand-written scanners can be tuned in ways a table-driven loop cannot, including SIMD scanning of whitespace and identifier bodies. Incrementality: a language server needs to restart a scan mid-file, which requires knowing the scanner state, and a hand-written scanner's state is a design decision rather than a table index. Build simplicity: no code-generation step.

The case for a generator is strongest exactly where those pressures are absent: a DSL, a configuration format, a protocol parser, or any project where the token set is still changing weekly and nobody will ever read the error messages closely.

Hand-written versus generated, on the axes that decide it
Hand-writtenGenerated (flex, re2c, ANTLR)
Cost to add a tokenA branch and a table entryA regex line
DiagnosticstypicalWhatever you write — can be excellentGeneric unless you write the actions yourself
SpeedtypicalTunable; SIMD and interning availableFast and predictable, hard to tune further
Correctness of maximal munchYours to get right, including backing upCorrect by construction
Incremental restartPossible if the state is designed for itAwkward — state is a table index
BuildNoneA code-generation step and a tool dependency
Used byimplementationClang, rustc, Go, CPython, V8Many DSLs, database engines, protocol parsers

The details that bite

Four implementation details cause most of the bugs in real scanners, and none of them are conceptually hard.

  • Termination on error. Always consume at least one character when no rule matches. A scanner that returns an error token without advancing hangs the compiler.
  • Unterminated constructs. A string or block comment that runs to end-of-file must report the position where it *started*, not where the file ended, or the user has to search for the missing quote by hand.
  • Line counting. Count newlines inside strings and comments too, or every line number after the first multi-line construct is wrong. Deriving lines from offsets at print time avoids this entirely.
  • Encoding. Decide whether identifiers may contain non-ASCII characters, and if so which — Unicode Standard Annex 31 defines identifier classes precisely, and Rust, Java, Python and C++ all reference it with different profiles. Then normalise, or two visually identical identifiers will not compare equal.

How it works

The steps, in the order the compiler takes them.

  • Skip whitespace and comments, recording newlines only if the language needs them, and note the start offset.
  • Dispatch on the current character into a family: word, digit, quote, operator, punctuation.
  • Within a family, consume the longest valid extent, using bounded lookahead where a prefix is also a valid token.
  • For words, look the completed text up in the keyword table to assign the final kind.
  • For operators, test candidates longest-first, or build a small trie so the longest match falls out of the traversal.
  • On no match, emit an error token spanning exactly one character and advance, so the scan terminates and later tokens are still produced.
  • Return (token, newPosition) and iterate until an end-of-file token is emitted.

How it breaks

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

  • A stray character with no rule causes the scanner to return without advancing, and the compiler spins at 100% CPU on a file that a text editor opens fine.
  • Operators are tested shortest-first, so every >= becomes > followed by = and the parser reports an error at the = in every comparison in the project.
  • An unterminated string swallows the rest of the file and the reported error is at the last line, so the user searches the wrong end of a thousand-line file for a missing quote.
  • Newlines inside block comments are not counted, and every line number after the file's license header is wrong by twenty — reported as "the compiler's line numbers are off".
  • Two identifiers that look identical do not compare equal because one uses a precomposed character and the other a combining sequence, and the error is "cannot find value café in this scope" pointing at what appears to be the definition.
  • A generated scanner backs up on a hot pattern, and lexing dominates front-end time on large inputs — invisible until someone profiles and finds lex.backup was never checked.

When it helps

  • Any language implementation: the scanner is the first thing to build and the easiest to test exhaustively, since its input and output are both flat.
  • Tooling that needs tokens but not a parse — highlighters, token-based diffs, simple linters — can reuse the scanner alone.
  • Fuzzing: a scanner is a pure function from bytes to a token list, which makes it the easiest component in a compiler to fuzz for hangs and crashes.

When it hurts

  • For a format that is genuinely regular and tiny — a two-key configuration file — a scanner is more machinery than a split and a trim.
  • When the language's lexical structure is context-dependent, a standalone scanner is the wrong shape and forcing it produces a mode stack that is harder than the scannerless alternative.

What it costs

Every one of these is paid by something.

  • Hand-writing buys diagnostics, tunability and incremental restart, and costs the correctness-by-construction a generated DFA gives you for maximal munch and backing up.
  • Generating buys a correct automaton from a readable specification and costs a build-time tool dependency, generic error messages, and difficulty restarting a scan mid-file.
  • Bounded lookahead buys correct handling of prefix-overlapping tokens such as 1..5 and costs a branch per character class plus the requirement that the scanner can un-consume.
  • Interning identifiers buys pointer-equality comparisons for the rest of the compiler and costs a hash table lookup per identifier occurrence plus a global structure the scanner must be given.

What else you could do

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

  • re2c, which generates a scanner as inline C or C++ with no runtime and no table indirection, sitting between hand-written and flex on every axis — used by PHP and by several database engines.
  • A regular-expression library driven by an alternation of named patterns, which is how many scripting-language tokenizers work. Convenient and considerably slower, and dangerous with a backtracking engine on adversarial input.
  • Scannerless parsing, where the grammar handles characters directly. It is the right answer when lexical structure depends on context, and it gives up the linear-time constant-memory scanning guarantee.
  • tree-sitter's incremental lexer, which is generated but designed around resumability so an editor can rescan only an edited region — a genuinely different point in the design space from both flex and a hand-written loop.

See it for yourself

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

  • flex --backup grammar.l writes lex.backup listing every state that may need to rewind; flex -v reports the table sizes and the number of DFA states.
  • flex -d (or %option debug) makes the generated scanner print each rule it matches at run time, which is maximal munch narrating itself.
  • Read a real one: clang/lib/Lex/Lexer.cpp, rustc_lexer/src/lib.rs, go/src/cmd/compile/internal/syntax/scanner.go and CPython's Parser/tokenizer.c are all readable in an afternoon and all hand-written.
  • re2c --emit-dot renders the generated automaton as a Graphviz graph, which is the fastest way to see what your patterns actually compiled to.
  • Our lexer stepper at /compilers/lexer steps the real AtlasLang scanner one character at a time, showing the pending match and the last accepting position.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Generated lexers are faster than hand-written ones." Not reliably. Modern hand-written scanners in Clang and rustc are tuned in ways a table-driven loop cannot be, and the reason production compilers hand-write them is diagnostics rather than speed.
  • "Maximal munch is obviously correct." It is a chosen rule, and C's a---b and x+++y are the standard demonstrations that it produces programs nobody wrote.
  • "A lexer never needs lookahead." It needs bounded lookahead whenever a valid token is a prefix of another valid token, which is true of >/>=, ./.. and ////.
  • "Error recovery is the parser's job." The scanner has its own recovery obligation: advance on failure, and report unterminated constructs at their start. Getting it wrong makes every later diagnostic worse.

Misconceptions

The claim, and what is actually true.

A lexer is just a regular expression.
It is an alternation of patterns with a longest-match rule, a priority rule for ties, error recovery, and position tracking. A single regex gives you none of the last three.
The scanner should reject invalid programs.
It rejects invalid *lexemes*. let let let; scans perfectly and fails in the parser, and a scanner that tried to prevent that would need the grammar.
Backing up is a flex problem.
It is maximal munch's problem. A hand-written scanner solves it with explicit lookahead; the requirement is the same and only the mechanism differs.

Go deeper

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

overview

Write a loop. Skip whitespace, note where you are, look at the current character, and dispatch: letters start a word, digits start a number, a quote starts a string, everything else is an operator or punctuation. Each branch consumes the longest thing it can and returns a token with its byte range. Consume something on every path, including the error path.

practical

Two rules will save you most of the bugs. Test multi-character operators longest-first, or build a trie so the longest falls out of the walk. And always advance on an unmatched character, because a scanner that returns without moving hangs the whole compiler on a file with one stray byte — which is also the first thing a fuzzer will find. When you write the string scanner, record the opening quote's position so an unterminated literal can be reported where it started.

advanced

The shift from generated to hand-written scanners in production compilers over the last two decades was driven by requirements that did not exist when flex was designed. A language server needs to rescan an edited region without rescanning the file, which requires the scanner state at an arbitrary offset to be a small, describable value — easy if you designed the state, awkward if it is a generated table index. Diagnostics need two spans and a structured note, not a return code. Macro and template systems need a scanner that can be pointed at a synthetic buffer while keeping a link to the original. Each of these is achievable with a generator and easier without one, and the cumulative effect is that the correctness-by-construction argument, which is genuinely strong, lost to the sum of everything else. tree-sitter is the interesting counter-move: a generator designed for resumability from the start, which recovers the construction guarantee for exactly the use case that killed the old generators.

How much this depends on

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

implementationThe hand-written-scanner claim is about the current sources of Clang, rustc, the Go toolchain, CPython and V8. Generated scanners remain standard in database engines and in DSL toolchains — PostgreSQL uses flex, and many ANTLR-based projects use its generated lexer. Which is right depends on whether anyone will read the diagnostics.
typicalMaximal munch is the disambiguation rule in essentially every mainstream language, and C, C++, Java, Go and Rust all state it. It is not universal: some assembly and template languages disambiguate by rule priority instead, taking the first matching pattern rather than the longest, which makes pattern order semantically significant.
specIdentifier character classes are specified by reference to Unicode Standard Annex 31 in Rust, Java, Python and C++, but with different profiles and different normalisation requirements — Python normalises identifiers to NFKC while Rust requires NFC and warns on confusable characters. A scanner that ignores this accepts identifiers the language does not.

If you were asked this in an interview

  • Write the identifier and number branches of a scanner. Where does the keyword lookup go, and why there?
  • What does your scanner do with a character no rule matches, and what happens if it does not advance?
  • Why do Clang, rustc and Go all hand-write their lexers when flex exists?

Connections

DSAstringhash-tabletrie
Securityfuzzing