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 kind is the terminal symbol the grammar will match on, so choosing the kinds is designing the interface between the lexer and the parser. Too coarse and the grammar does the lexer's work; too fine and the grammar has a rule per operator.

Kind, value and position. The first two are obvious; the third is the one that pays for itself, because every diagnostic, hover, rename, source map and debugger line table in the entire toolchain is derived from byte ranges recorded once, here, and never recoverable afterwards.

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 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 machine a lexer actually is: states, transitions on characters, and a set of accepting states. Drawing the identifier and number recognisers as automata makes the whole scanner mechanical, and makes the `123abc` problem visible before you write it.

Thompson's construction turns a pattern into an NFA in linear space; subset construction turns the NFA into a DFA that runs in linear time. The bill for that speed is table size, and in the worst case it is exponential.

Everywhere the clean phase separation leaks: maximal munch producing programs nobody wrote, `123abc`, contextual keywords, `>>` closing two generic brackets, escapes, Python emitting INDENT tokens, and C needing a symbol table to lex.