Tokens, Lexemes and Patterns

A source file arrives at the compiler as one long, undifferentiated ribbon of characters: r, a, t, e, space, =, space, and so on. The very first phase — the scanner (or lexer, or lexical analyser) — has one job: chop that ribbon into the smallest meaningful chunks the rest of the compiler can reason about, and hand each one upward with a label attached. Those labelled chunks are tokens. Everything downstream — the parser, the type checker, the code generator — sees tokens, never raw characters. Get the scanner right and the parser's life becomes clean; get it wrong and errors ripple through every later phase.

The scanner is where three closely-related words earn precise, separate meanings that beginners forever blur together: pattern, lexeme, and token. Keeping them apart is the whole content of this page, because once the vocabulary is crisp the rest of lexing — regular expressions, automata, table-driven scanners — is just machinery in service of it.

Three words, three jobs

The Dragon Book draws the distinction sharply, and it is worth memorising:

A pattern is a rule describing the set of strings a token can take — almost always written as a regular expression. The pattern for an identifier might be "a letter followed by any number of letters or digits".
A lexeme is an actual run of characters in the source that matches a pattern. In rate = initial + 60, the substrings rate, initial and 60 are lexemes.
A token is the pair \langle \text{name}, \text{attribute value}\rangle the scanner emits: a token name (an abstract symbol the parser uses, e.g. id, num, assign) and an optional attribute value pointing at extra information (which identifier, which numeric value).

In one sentence: a lexeme is a concrete string; a pattern is the rule it matched; a token is the classified pair the scanner outputs. Many lexemes (rate, initial, x, counter) can all match the one identifier pattern and so all become tokens with the same name id — distinguished only by their attribute value.

The classic example, dissected

Take the assignment statement rate = initial + 60. The scanner sweeps left to right and emits five tokens. Here is every lexeme, the token it becomes, and the pattern it matched:

Lexeme	Token	Informal pattern
`rate`	\langle \mathtt{id}, \text{ptr to } rate\rangle	letter ( letter \| digit )*
`=`	\langle \mathtt{assign}\rangle	the literal character `=`
`initial`	\langle \mathtt{id}, \text{ptr to } initial\rangle	letter ( letter \| digit )*
`+`	\langle \mathtt{plus}\rangle	the literal character `+`
`60`	\langle \mathtt{num}, 60\rangle	digit digit*

Notice the shape of the attribute values. Punctuation tokens like assign and plus carry no attribute — knowing the name is enough, because there is only one =. Identifiers carry a pointer into the symbol table, not the spelling itself; the number carries its numeric value 60, not the two characters 6 and 0. The whitespace between the lexemes produces no token at all — it is consumed and discarded.

Identifiers and the symbol table

Why a pointer for identifiers rather than the string? Because the compiler will meet the name rate again and again — every use must resolve to the same variable, with the same type, scope and storage. So when the scanner recognises an identifier lexeme it consults (and, on first sight, inserts into) the symbol table: a dictionary keyed by name. The attribute value in the id token is that table entry, so rate on line 1 and rate on line 40 both point at one shared record. This is the scanner's single most important side effect and the reason lexing is not purely "split on spaces".

Separation of concerns. The parser's grammar is written over token names — id = expr, not rate = … — so the parser is blissfully ignorant of what an identifier is spelled. That is exactly what lets one small grammar handle a program with ten thousand distinct variable names: to the parser they are all just id. The spelling lives in the attribute value, retrieved later only when semantics (type checking, code generation) actually needs it. Compressing "a variable named rate" down to "id plus a table pointer" is the scanner buying the parser its simplicity.

Whitespace, comments, and things that vanish

Not every character produces a token. In most languages whitespace (spaces, tabs, newlines) and comments match patterns whose action is simply "consume and emit nothing". They still must be recognised — the scanner has to know where a comment ends — but they leave no trace in the token stream. This is why the scanner, not the parser, handles them: it keeps the grammar free of clutter. (A handful of languages buck this: Python turns newlines and indentation into real NEWLINE/INDENT/DEDENT tokens, because there layout is syntax.)

Two rules that resolve every ambiguity

When the scanner is sitting at a position, several patterns might match, and they might match runs of different lengths. Two conventions, applied in order, decide what to do — and together they define what "the next token" even means:

Longest match (maximal munch). Prefer the longest prefix of the remaining input that matches some pattern. Facing <=, the scanner takes both characters as one le token, not < followed by =. Facing rate it keeps reading letters until it hits the space, taking all four — not just r.
Rule priority. When two patterns match the same longest lexeme, the one listed first in the specification wins. This is how keywords beat identifiers: the lexeme if matches both the keyword pattern and the identifier pattern, and because the keyword rule is listed first, if becomes the if token, not an id.

These two rules are not optional niceties — they are the definition of tokenisation. Change the order of the rules and you change the language.

A hand-written scanner, running

Nothing makes the pattern/lexeme/token trio concrete like watching a scanner do it. Below is a tiny hand-coded scanner that splits rate = initial + 60 into tokens, applying maximal munch for identifiers and numbers and treating keywords as higher-priority identifiers. Run it and read the token stream it prints.

type Token = | { name: "id"; value: string } | { name: "num"; value: number } | { name: "assign" } | { name: "plus" }; const KEYWORDS = new Set(["if", "else", "while"]); const isLetter = (c: string) => /[A-Za-z]/.test(c); const isDigit = (c: string) => c >= "0" && c <= "9"; function scan(src: string): Token[] { const tokens: Token[] = []; let i = 0; while (i < src.length) { const c = src[i]; if (c === " " || c === "\t" || c === "\n") { i++; continue; } // whitespace: no token if (c === "=") { tokens.push({ name: "assign" }); i++; continue; } if (c === "+") { tokens.push({ name: "plus" }); i++; continue; } if (isLetter(c)) { // maximal munch: identifier let j = i + 1; while (j < src.length && (isLetter(src[j]) || isDigit(src[j]))) j++; const lexeme = src.slice(i, j); // priority: if the keyword rule were listed first, a lexeme in KEYWORDS // would become a keyword token here; none of these three are keywords. const isKeyword = KEYWORDS.has(lexeme); tokens.push({ name: "id", value: lexeme + (isKeyword ? " [reserved]" : "") }); i = j; continue; } if (isDigit(c)) { // maximal munch: number let j = i + 1; while (j < src.length && isDigit(src[j])) j++; tokens.push({ name: "num", value: Number(src.slice(i, j)) }); i = j; continue; } throw new Error(`Lexical error: unexpected character '${c}' at ${i}`); } return tokens; } for (const t of scan("rate = initial + 60")) { console.log(JSON.stringify(t)); }

The while loops inside the identifier and number cases are maximal munch: each keeps swallowing characters as long as the pattern still matches. The scanner emits an id for rate carrying its spelling as the attribute — a real compiler would instead store that spelling in the symbol table and carry the pointer.

When nothing matches: lexical errors

Sometimes the scanner is stuck: the current character starts no legal token — a stray @ in a C program, an unterminated string, an illegal character in an identifier. That is a lexical error, and it is caught here, before the parser ever runs. The usual recovery is panic mode: delete the offending character (or characters) and resume, so that one bad symbol does not abort the whole compilation. Reporting the exact line and column is a large part of what makes a compiler pleasant to use — and, as we will see later, a reason production compilers often hand-write their scanners.

Two mistakes account for most tokenisation bugs, and both come straight from the two rules above:

Getting keyword-vs-identifier priority backwards. If the identifier rule is checked before the keyword rule, the lexeme while is happily classified as an id and your loop keyword silently disappears. Keywords are reserved precisely because the keyword pattern is given priority over the identifier pattern for the same spelling. (Some languages instead keep keywords "soft" by not reserving them — a deliberate, and tricky, design choice.)
Forgetting maximal munch — or applying it too eagerly. Without longest-match, >= splits into two tokens and 3.14 into 3, ., 14. But the greedy rule can also bite: in old C, a---b munches as a -- - b (post-decrement then minus), which is probably not what the programmer meant. Maximal munch is a mechanical rule, not a mind-reader — it resolves ambiguity consistently, not always intuitively.