Lexingtypical

Lexical Analysis

The first transformation in the pipeline: fifteen characters of `let x = 42 + y;` become seven tokens, each with a kind, its text and the byte range it occupied. Everything downstream is written against that list rather than against the text.

The question

What does a lexer actually produce, and why is that a separate phase from parsing at all?

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

Before: a byte sequence with no structure whatsoever — the file as it sits on disk. After: a flat, finite list of tokens, each a (kind, text, start, end) record. The list exists to answer exactly one question the byte sequence cannot: *which characters belong together, and what kind of thing is each group?* It answers nothing about how the groups relate; that is the parser's job.

What this phase may assume or do

The lexer is entitled to assume nothing at all — it is the first phase, and its input is arbitrary bytes. It must therefore terminate on every input, including invalid ones, and it may not consult any information a later phase produces. Where a language breaks that rule — C's typedef names, discussed in [[lexer-hazards]] — the phase separation is broken with it, and every tool that wanted tokens without a symbol table pays.

Key points

  • The lexer turns a byte sequence into a flat list of (kind, text, start, end) records and nothing more.
  • let x = 42 + y; is fifteen bytes and seven tokens; the four spaces are consumed and discarded.
  • Maximal munch — take the longest valid token at each position — is why 42 is one token and >= is one operator.
  • The lexer/parser split exists because token structure is regular and program structure is not; the weaker formalism is cheaper.
  • Spans recorded here are the origin of every diagnostic, every hover, every source map and every debugger line table downstream.
  • A lexer that needs information from a later phase, as C's does, breaks every tool that wanted tokens without a full compilation.

Fifteen characters, seven tokens

Take one line of source. As a byte sequence it is let x = 42 + y; — fifteen characters, and nothing about that sequence says that l, e and t form one thing while 4 and 2 form another. The lexer walks it left to right, and at each position takes the longest sequence of characters that forms a valid token. That rule is called *maximal munch*, and it is the reason 42 is one number rather than two.

What comes out is a list. Each entry carries a kind — the terminal symbol the grammar will match against — the exact text that was matched, and the half-open byte range [start, end) it occupied in the source. Whitespace is consumed and discarded; so are comments, in most languages. The result is smaller, uniform, and finite in a way the character sequence is not.

Read the offsets in the device below carefully, because they are the point. let is [0, 3), and the space at offset 3 vanishes — the next token starts at 4. A token that ends at 14 is followed by one that starts at 14, because there is no space before the semicolon. Spans are byte ranges, not word positions, and every diagnostic, every jump-to-definition and every source map in the entire toolchain is ultimately derived from numbers recorded right here.

The complete token stream for one line
let x = 42 + y;

Read it asSeven tokens, four whitespace characters discarded, and fifteen bytes accounted for exactly. What the list adds: grouping and classification. What it still cannot say: that 42 + y is one expression, that x is being declared, or that any of these names refer to anything — those need [[what-parsing-does]] and [[semantic-analysis]] respectively.

Why it is a separate phase

Nothing forces the split. A parser could work directly on characters, and scannerless parsers exist. The split is a design decision, made almost universally, for three reasons that are worth separating because they carry different weight.

The first is formal, and it is the strongest. Token structure is *regular* — identifiers, numbers and string literals have bounded structure and need no counting — while program structure is *context-free* and needs a stack. Using the weaker formalism where it suffices means the lexer can be a finite automaton: constant memory, one pass, no backtracking. That argument is [[regular-languages]] in full.

The second is practical: the parser gets dramatically simpler. A grammar written over token kinds has no rules about whitespace, no rules about digit sequences and no rules about comment bodies, and a grammar with those rules in it is several times larger and much harder to read.

The third is performance, and it is the weakest of the three but still real. The lexer touches every byte of the input exactly once and produces something an order of magnitude smaller for the parser to work on. In a compiler that reads large headers repeatedly, lexing has historically been a measurable fraction of front-end time, which is one of the arguments for precompiled headers and for [[modules]].

What the first two stages each add and discardtypical
  1. Bytesyou write it
    The file as stored. No structure, no encoding decisions made yet.
  2. Charactersbuild time
    A decoded sequence of Unicode scalar values.
    An encoding interpretation — which is itself a decision, and one that can fail.
  3. Tokensbuild time
    A flat list of (kind, text, start, end) records.
    Grouping and classification: which characters form one thing, and what kind of thing it is.
    Whitespace and comments, unless deliberately retained as trivia for a formatter.
  4. Parse treebuild time
    A tree over those tokens, shaped by the grammar.
    How the groups relate — nesting, precedence, statement structure.
    Nothing yet, if spans were threaded through.

Read it asThe loses row on Tokens is the one to dwell on. Whitespace and comments are gone by the time the parser runs, which is why a compiler cannot reformat your code and why formatters, linters and language servers all need a lexer that keeps trivia — a different mode of the same scanner. See [[concrete-syntax-tree]].

What the lexer refuses to know

A good lexer is aggressively ignorant. It does not know that let introduces a declaration, that + is a binary operator, that x and y might be the same variable, or that 42 will end up as a 32-bit integer. It knows that three characters formed a keyword, that one formed an identifier, and where each of them was.

That ignorance is what makes the phase reusable. The same token stream feeds the compiler's parser, the syntax highlighter, the formatter and the language server's incremental reparser. Push any judgement into the lexer and every one of those consumers inherits it — which is precisely what goes wrong in C, where the lexer must know which identifiers are typedef names and therefore cannot run without a symbol table.

The one judgement a lexer does make is the keyword lookup, and even that is usually deferred: scan the identifier, then consult a table. Doing it that way rather than with a separate pattern per keyword is what makes contextual keywords possible at all — a topic that gets its own treatment in [[lexer-hazards]].

  • The lexer produces a *flat list*. Any nesting in the output means the split has been broken.
  • Every token carries a span, or the compiler can only ever say "syntax error" — see [[source-locations]].
  • Errors at this level are lexical: an unterminated string, an illegal character, a malformed number. They are not "expected an expression".
  • The lexer runs on invalid input too, and must terminate on it. A scanner that hangs on a stray backslash is a denial-of-service surface in every tool that embeds it.

How it works

The steps, in the order the compiler takes them.

  • Decode the input bytes into characters, choosing an encoding — this is a decision, and an invalid byte sequence is a lexical error.
  • Skip whitespace and comments, or record them as trivia if a formatter or language server will consume the stream.
  • At the current position, try every token pattern and take the longest match; ties are broken by a fixed rule order, which is how keywords beat identifiers.
  • Emit a record with the matched kind, the matched text and the half-open byte range, then advance the position to the end of the match.
  • On no match, emit a lexical error with the offending span and recover by skipping one character, so the scan terminates and later errors are still reported.
  • Emit an end-of-file token so the parser has a definite terminator rather than a special case.

How it breaks

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

  • Spans are computed off by one — usually by recording the position after the token rather than before — and every error message in the compiler points at the character following the mistake.
  • The scanner does not advance on an unrecognised character and loops forever, so the compiler hangs on a file containing a stray byte and never reports anything.
  • Comments are stripped before line counting, and every reported line number after the first block comment is wrong by the number of lines that comment spanned.
  • A multi-byte UTF-8 identifier is measured in characters while the editor measures in UTF-16 code units, and the squiggle in the IDE lands several characters away from the error — a symptom that only appears for users writing non-ASCII source.
  • An unterminated string literal consumes the rest of the file, so a single missing quote produces one lexical error and a hundred nonsensical parse errors after it.

When it helps

  • Any time the input has bounded lexical structure and unbounded grammatical structure, which is every programming language and most configuration and query languages.
  • Building tooling: a lexer alone is enough for syntax highlighting, for token-based diffing and for a fast approximate search index.
  • Debugging a front-end problem: dumping tokens separates "the scanner grouped it wrong" from "the parser structured it wrong" in one command.

When it hurts

  • When the language cannot be tokenised without parsing context. Scannerless parsing exists precisely for languages where the lexical structure depends on the grammatical one, and forcing a split there means a lexer that carries modes and state.
  • For templating and mixed-language formats — HTML with embedded scripts, or a shell language — a single token stream is a poor fit, and the practical answer is several lexers with explicit switching rather than one heroic scanner.

What it costs

Every one of these is paid by something.

  • Separating lexing from parsing buys a constant-memory single-pass scanner and a much smaller grammar, and costs the ability to make lexical decisions that need grammatical context — which some languages genuinely need.
  • Discarding whitespace and comments buys a smaller, uniform token stream, and costs the ability to reproduce the source, so formatters and language servers must run a second scanning mode that keeps trivia.
  • Recording a span on every token costs memory proportional to the token count — a real number on a large translation unit — and buys every diagnostic, hover and source map the toolchain will ever produce.

What else you could do

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

  • Scannerless parsing, where the grammar goes all the way down to characters. It handles languages whose lexical structure depends on context, and pays with a much larger grammar and the loss of the linear-time scanning guarantee.
  • Two-phase lexing with an explicit preprocessing stage, as in C, where the preprocessor produces a token stream that the compiler then re-lexes. It buys macro expansion and pays with a phase whose errors reference text nobody wrote — see [[the-preprocessor]].
  • Lexer modes or stacked lexers for embedded languages: a template engine switches between a text mode and an expression mode on delimiters. It buys mixed-language support and costs the lexer its statelessness, which breaks restarting a scan at an arbitrary offset.

See it for yourself

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

  • clang -Xclang -dump-tokens -fsyntax-only x.c prints every token with its kind and its source location, which is exactly the device in this lesson for real C.
  • python3 -m tokenize file.py prints Python's token stream with type, string and start/end (row, col) pairs, including the synthesised INDENT and DEDENT tokens.
  • go/scanner in the Go standard library will dump a token stream in a dozen lines of code; the token.Position it yields is the span this lesson is about.
  • rustc -Z unpretty=expanded is post-expansion rather than tokens, but cargo expand and the proc_macro::TokenStream type expose Rust's tokens directly to macros.
  • Our lexer stepper at /compilers/lexer runs the real AtlasLang scanner over whatever you type, one token at a time, with the source range highlighted.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The lexer removes whitespace." It removes whitespace *from the token stream*. Whether it is retained as trivia is a decision, and every formatter and language server retains it.
  • "Tokens are words." They are the longest valid lexemes. >= is one token and 42 is one token; neither is a word, and a---b is three operators and two identifiers.
  • "The lexer validates the program." It validates lexical structure only. let let let; lexes perfectly into three keywords and a semicolon, and fails in the parser.
  • "Spans are line and column numbers." They are byte offsets. Line and column are derived from them by a separate line-index structure, which is why an off-by-one in the offsets shifts every reported position at once.

Misconceptions

The claim, and what is actually true.

Lexing is the easy part of a compiler.
It is the simplest to start and the one with the most edge cases in a real language: encodings, escapes, numeric literal forms, contextual keywords and significant indentation all land here.
The token stream is a faithful representation of the source.
It has already lost whitespace, comments and — in most lexers — the distinction between 0x2A and 42. Reconstructing the source from tokens is not generally possible.
Every language can be lexed without parsing.
C cannot: whether A in A * B; is a type name is a symbol-table question. That is the lexer hack, and it breaks the phase separation this lesson describes.

Go deeper

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

overview

The lexer reads the source left to right and groups characters into tokens: keywords, identifiers, numbers, operators, punctuation. Each token records what kind it is, what text it matched and where it was. Whitespace and comments are thrown away. Everything after this point works on the token list instead of the text.

practical

When the front end misbehaves, dump the tokens first. clang -Xclang -dump-tokens or python3 -m tokenize will tell you in one command whether the characters were grouped as you expected. Half of "the parser is wrong" reports are the scanner having taken a longer match than intended, and the token dump makes that obvious in a way that staring at the source does not.

advanced

The span is the load-bearing part of the record, and its representation is a real design decision. Clang stores a single 32-bit SourceLocation that indexes into a table of files, macro expansions and offsets, so a location can encode "column 7 of line 3 of the third expansion of this macro" in one word — which is why Clang can print macro expansion backtraces at all. rustc uses a global byte-offset Span into a source map, with a side table for expansion context, for the same reason. A compiler that stores a naive (line, column) pair per token has already given up on macro backtraces and pays for line recomputation on every edit; a compiler that stores raw byte offsets and derives lines lazily can reparse an edited region without renumbering anything after it, which is what an incremental language server needs.

How much this depends on

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

typicalThe lexer/parser split described here is what mainstream compilers do — Clang, GCC, rustc, the Go toolchain and CPython all have a distinct scanner. Scannerless designs exist and are the right answer for languages whose lexical structure is context-dependent; SGLR-based tools and several PEG parsers work directly on characters.
implementationThe -Xclang -dump-tokens output described here is Clang's and prints kind, spelling and location per token. GCC has no directly equivalent flag; gcc -E gives preprocessed text rather than tokens, so the same investigation on GCC needs -fdump-tree-original or a different approach entirely.
simplifiedOur token records carry kind, text and a byte range. Production lexers additionally carry a flag for whether the token started a line, whether whitespace preceded it, a macro-expansion identifier in C and C++, and often an interned handle rather than the text itself. Several of those exist purely to make diagnostics and [[the-preprocessor]] work.

If you were asked this in an interview

  • Walk me through what the lexer produces for let x = 42 + y;, including the spans.
  • Why is lexing a separate phase from parsing, and what would it cost to merge them?
  • A compiler reports every error one character to the right of where it happened. Which phase has the bug?

Connections

DSAstringhash-table
Databasesql-parser-internals