Skip to content

Lexical Scanning and Tokenization

Front-end scanning method — instantiates Grammar-Guided Structure Recovery

Segments the raw character stream into typed, position-stamped tokens — the flat, span-tagged feedstock every parser consumes, with no hierarchy of its own.

Before any grammar can find structure, something has to decide where one lexical unit ends and the next begins. Lexical Scanning and Tokenization is that front stage: it walks the raw character stream once, groups characters into typed tokens (identifier, number, operator, string), and stamps each with the exact span it occupies in the source. What makes it this mechanism and not a parser is what it deliberately refuses to do — it builds no tree. It draws boundaries and classifies, governed by a regular pattern set rather than a compositional grammar, and hands downstream a clean, flat, position-tagged token stream. Every parser in the archetype consumes that stream; none of them should be looking at raw bytes.

Example

An interpreter's front end reads the line price = qty * 1.5 # markup. The scanner walks left to right applying maximal munch — always taking the longest match that forms a valid token. It emits price as an IDENT at span 0–5, = as ASSIGN, qty as IDENT, * as STAR, and 1.5 as a single NUMBER (not 1, ., 5), then treats # markup as a COMMENT. Longest-match is what lets it tell == from a pair of =, and >= from > then =. Each token carries its byte offset and line/column, so a later "unexpected token" error can point at the exact character. When the stream contains a stray $, the scanner emits an explicit ILLEGAL token at that position and keeps going, rather than crashing the whole read. The output is a flat list of (type, text, span) triples — no nesting, just segmented, labelled, located units.

How it works

What distinguishes the lexer from the parsers it feeds is that it is deliberately flat and regular:

  • It matches against a set of regular patterns compiled into a finite-state scanner, in a single left-to-right pass — linear in the input, no backtracking over structure.
  • It resolves token boundaries by maximal munch (longest valid match) plus fixed tie-break rules (keywords over identifiers).
  • It records a span for every token and normalizes encoding/whitespace so the parser never touches raw bytes.
  • It classifies but never composes: matching brackets, nesting, and attachment are explicitly not its job — it leaves those to the grammar-driven parser.

Tuning parameters

  • Token granularity — how fine the token set is (keywords as their own types vs. one IDENT type plus a lookup). Finer tokens simplify the parser but enlarge the token table.
  • Longest-match policy — maximal munch by default, with targeted overrides for hostile cases (splitting >> inside nested generics). Overrides rescue specific grammars but add special-case logic.
  • Trivia handling — discard whitespace and comments, or emit them as retained trivia tokens. Discarding is leaner; retaining is required for formatters and round-trip tools.
  • Encoding & normalization — byte vs. Unicode-grapheme scanning, case folding, newline canonicalization — the dial that decides what "a character" even is.
  • Illegal-input policy — emit an ILLEGAL token and continue, or halt; how far to skip before re-syncing the scan.

When it helps, and when it misleads

Its strength is leverage for almost no cost: a linear scan converts raw bytes into clean, classified, position-tagged units, isolating encoding and whitespace concerns so every downstream parser sees a tidy stream, and the recorded spans power precise diagnostics and editor tooling.

It misleads when the tidy separation is assumed to hold universally. Tokenization is context-free of the grammar by design, so genuine lexical ambiguity — is a < b > c two comparisons or a generic instantiation? — cannot be settled at this layer, and forcing it here (the classic "lexer hack" of feeding parser state back into the scanner) quietly couples two stages that were meant to be independent.[1] Over-eager maximal munch can also mis-split a token no grammar can then repair. The classic misuse is pushing structural decisions — matching brackets, tracking nesting — into the lexer to "save a pass"; that belongs to the parser. The discipline is to keep the lexer regular and flat and escalate anything requiring composition upward.

How it implements the components

Lexical Scanning and Tokenization fills the archetype's input-and-segmentation components — the ones a front-end scanner produces, and no more:

  • surface_sequence_record — it is the stage that ingests and canonically records the exact raw character stream as received, the ground truth everything else is measured against.
  • token_and_span_map — its primary output: each token paired with the precise source span it occupies.
  • provenance_record — by stamping every token with its origin position, it seeds the provenance that each structural node built downstream will cite back to.

It does not build hierarchy or resolve attachment — that is the parsers' work (Recursive-Descent Parsing, Shift-Reduce Parsing, Chart Parsing) — and it neither authors the grammar (Grammar Rule Set) nor validates meaning (Semantic Schema Validation).

  • Instantiates: Grammar-Guided Structure Recovery — it supplies the token-and-span stream the whole recovery pipeline runs on.
  • Sibling mechanisms: Recursive-Descent Parsing · Shift-Reduce Parsing · Chart Parsing · Probabilistic Grammar Parsing · Schema-Driven Hierarchical Decoding · Error-Tolerant Parsing · Round-Trip Parse–Serialize Testing · Grammar Rule Set · Ambiguity Register · Controlled Disambiguation Test · Interpretation Walkthrough · Invalid Combination Linter · Linting or Validation Rule · Semantic Schema Validation

Notes

The clean lexer→parser handoff assumes tokenization is context-free of the grammar. A few languages break that assumption — C's typedef-name vs. identifier distinction can't be decided without parser feedback — and paying for that coupling knowingly is better than pretending the layers are always separable. Separately, a lexer that discards whitespace and comments cannot support round-trip tooling: formatters and Round-Trip Parse–Serialize Testing need those retained as trivia, so the trivia-handling dial is a real architectural choice, not a detail.

References

[1] Maximal munch (the longest-match rule) is the standard tokenization discipline: at each point take the longest character sequence that forms a valid token. It is what makes multi-character operators and numeric literals scan correctly, and its limits are exactly where lexical ambiguity forces coupling back to the grammar. ↩