Lexer Hazards

The longest-match rule is not a discovery about language; it is a choice, and it is occasionally the wrong one. It produces two families of surprise, and both appear in languages you use.

The first is a longer token where a shorter one was meant. 123abc is the canonical case: the number automaton stops at 3 because there is no transition on a letter, emits NUMBER("123"), and the identifier scan then produces IDENTIFIER("abc"). The token stream is perfectly reasonable and the resulting parse error names the identifier, not the malformed literal. Rust and Go both special-case this, treating a letter immediately following a numeric literal as a lexical error so the message says what actually happened.

The second is a longer *operator* where two shorter ones were meant, which is the C a---b case from [[lexer-implementation]]. Neither is a bug in the scanner; both are the rule working as specified.

The most consequential maximal-munch collision in mainstream languages is the right shift operator against nested generic type arguments. List<List<int>> ends in two closing angle brackets with nothing between them, and the longest match at that position is the single token >>.

C++ lived with this for two decades: until C++11 the standard required List<List<int> > with a space, and every C++ programmer learned the habit. C++11 changed the *parser* to treat a >> token as two closing brackets when it appears where a template argument list is being closed — a context-dependent reinterpretation of a token that was already produced, which is a real complication in the standard and in every conforming implementation.

Java made the same choice and resolves >> and >>> positionally in the parser. C# does the same. Rust sidestepped it in expression position with the turbofish, Vec::<Vec<i32>>::new(), but still has to split >> in type position. The general lesson is that when a language chooses angle brackets for generics, it has chosen this problem, and the only question is which phase pays.

Reserving a word is a source-breaking change: every program using it as an identifier stops compiling. Growing languages therefore invent ways to add vocabulary without reserving anything, and the standard technique is the contextual keyword — a word that has special meaning in one grammatical position and is an ordinary identifier everywhere else.

The lexer's correct behaviour is to do nothing. It emits IDENTIFIER("async"), and the parser recognises it positionally. That is only possible because the keyword decision is a table lookup after the identifier match rather than a separate pattern, which is the design point from [[token-kinds]] paying off.

The examples are everywhere once you look. C# added var, async, await, yield, dynamic, nameof and record this way — var var = 1; is legal C#. TypeScript's type, as, is, declare, namespace and satisfies are all contextual. JavaScript's await is a keyword only inside an async function and yield only inside a generator, so the *same source text* tokenises identically and parses differently depending on the enclosing function. Rust handled a larger version of the problem with editions: async, await, try and dyn became reserved in the 2018 edition, and crates on the 2015 edition still compile, so the reserved-word set is a per-crate property.

The cost is diagnostics and tooling. When await is an identifier in one function and a keyword in another, a syntax highlighter cannot colour it correctly without parsing, and an error message about misusing it has to explain the context rather than the word.

Two hazards share a root: the assumption that a token's text is a slice of the source. String escapes break it in one direction and synthesised tokens break it in the other, and a token record designed around the assumption cannot represent either.

String literals are where the lexer does genuine interpretation rather than classification. "a\nb" is six characters in the source and three in the value, and something has to perform that conversion — the lexer is the only phase that can see the raw bytes, so it is the lexer. That creates a token with two texts: the raw span, which a formatter and a linter need, and the decoded value, which the compiler needs. Production lexers carry both. It also creates a hard error-reporting problem, because an invalid escape sits at a position *inside* the literal, so the diagnostic needs a sub-span — which requires tracking the source position through the decoding loop rather than decoding into a buffer and reporting on the whole literal.

Interpolation goes further and breaks the phase boundary outright: ` total: ${a + b} ` contains an arbitrary expression, so the lexer must either recurse or maintain a mode stack, and nesting — an interpolation containing a string containing an interpolation — makes it genuinely non-regular. CPython restructured its tokenizer in 3.12 under PEP 701 specifically to allow arbitrary nesting and reuse of quote characters inside f-strings, which had been prohibited precisely because the old tokenizer could not handle it.

Python's block structure is indentation, and indentation is nesting, and nesting is not regular. Python resolves this by having the *lexer* synthesise tokens that appear nowhere in the source: INDENT when a logical line is more indented than the previous one, and DEDENT — possibly several — when it is less. The tokenizer maintains a stack of indentation levels to do it.

This is unusual and worth stating plainly: Python's lexer contains a stack, and emits tokens that correspond to zero characters of input. A DEDENT has an empty span at the start of a line. Having done that, the grammar downstream is ordinary and context-free, with INDENT and DEDENT playing the role that { and } play in C. The non-context-free feature was moved into a phase that was supposed to be weaker than context-free, which is a deliberate and rather elegant piece of engineering.

It has consequences. The tokenizer is stateful, so it cannot be restarted at an arbitrary offset without also restoring the indentation stack. Mixing tabs and spaces is a tokenizer-level error, and Python 3 rejects inconsistent mixing outright for exactly this reason. And Haskell's equivalent layout rule is worse: it is specified with a rule that permits inserting a closing brace on a parse error, which makes the layout algorithm depend on the parser and is famously difficult to implement to specification.

The worst case, and the one that breaks the phase separation outright, is C. A * B; is a multiplication statement whose result is discarded if A is a variable, and a declaration of B as a pointer to A if A is a typedef name. The two parse to completely different trees, and the token sequence is identical.

C compilers resolve this with the lexer hack: the parser feeds typedef names back into the lexer, which then emits TYPEDEF_NAME rather than IDENTIFIER for those spellings. The lexer therefore cannot run without a symbol table, and the symbol table is built by a phase that runs after lexing. The pipeline has a cycle in it.

The consequences are not theoretical. A syntax highlighter for C cannot correctly distinguish types from variables without effectively compiling the file, including its includes. An incremental parser cannot rescan a region without knowing which typedefs are in scope there. And because scope matters, the *same identifier* can be a type name in one block and a variable in another, so the feedback is not even a global table lookup. C++ makes it worse with the template angle-bracket problem and the "if it can be a declaration, it is a declaration" rule that produces the most vexing parse.

Every language designed since has treated this as a cautionary tale. Go introduced func, var and type keywords so that every declaration is syntactically distinct from every expression. Rust did the same with fn and let and added the turbofish for the generic case. The verbosity is the price of a lexer that runs standalone, and given what standalone lexing buys in tooling, most designers now consider it cheap.