Lexical Analysis and Tokens

A token is a category — a named class of lexical units that the grammar of the language treats uniformly. Typical token classes include `ID` (identifiers), `NUM` (numeric literals), `STRING` (string literals), keyword tokens like `IF` or `WHILE`, and punctuation/operator tokens like `PLUS`, `LPAREN`, or `SEMI`. A lexeme is the concrete substring of the source program that was matched to produce a token — `count`, `42`, `"hello"`, `if`, `+`. Many different lexemes can map to the same token class (`x`, `count`, `total17` are all lexemes of class `ID`), but a token by itself discards the specific spelling. To avoid losing information the parser or later phases might need, each token carries an attribute (sometimes called a semantic value): for an `ID` token this is typically a pointer or index into a symbol table; for a `NUM` token it is the parsed numeric value; for a keyword or punctuation token there is often no attribute needed, since the token class alone determines meaning. A pattern is the rule — usually a regular expression — that describes the set of lexemes belonging to a token class. For example the pattern for `ID` might be "a letter followed by zero or more letters or digits," and the pattern for `NUM` might be "one or more digits, optionally followed by a decimal point and more digits." The lexical analyzer's job, formally, is: given the pattern set $P = \{p_1, \dots, p_k\}$ for token classes $T = \{t_1, \dots, t_k\}$, and the source text $S$, partition $S$ (after discarding whitespace and comments) into a sequence of lexemes $\ell_1 \ell_2 \cdots \ell_m$ such that each $\ell_i$ matches some pattern $p_{j_i}$, and emit the token sequence $(t_{j_1}, \text{attr}_1), \dots, (t_{j_m}, \text{attr}_m)$. This partition is not automatically unique, so lexical analysis is as much about disambiguation as recognition. Two standard conventions make the partition well defined. The maximal munch (longest match) rule says that at each position, the scanner consumes the longest prefix of the remaining input that matches any pattern — so `<=` is read as one token, not `<` followed by `=`. The priority rule breaks ties among patterns that match the same longest lexeme, typically by rule order — so `if` matches both the `ID` pattern and the literal keyword pattern, and listing the keyword pattern first (or giving keywords explicit priority) ensures it is tokenized as `IF`, not `ID` with lexeme `"if"`. Whitespace and comments are usually matched by their own patterns and then discarded rather than emitted as tokens, since the parser's grammar has no need to see them (though position information from them, like line numbers, is retained for error messages).

Conceptually, a scanner is a loop: repeatedly skip irrelevant characters, then find the longest matching pattern for the token that begins at the current position, emit a token, and advance. The engineering reality is that this loop is implemented efficiently as a deterministic finite automaton (DFA), either hand-coded or generated from regular expressions by a scanner generator — the mechanics of that translation belong to Building Scanners with Finite Automata, but the algorithm below describes the abstract behavior any correct scanner must exhibit, independent of how the matching is implemented internally. The key data the scanner threads through the computation is a cursor into the input and, at each step, a record of the longest match found so far together with which token class it belongs to — this second piece is what lets maximal munch and rule priority be resolved together in a single scan. ``` function TOKENIZE(source): tokens ← empty list pos ← 0 line ← 1 n ← length(source) while pos < n: skip whitespace and comments starting at pos, advancing pos and incrementing line on each newline seen if pos ≥ n: break // trailing whitespace/comments only bestLen ← 0 bestClass ← NONE bestPriority ← +∞ for each (tokenClass, pattern, priority) in patternTable: len ← LONGEST_PREFIX_MATCH(pattern, source, pos) // LONGEST_PREFIX_MATCH returns 0 if no match at pos if len > bestLen: bestLen ← len bestClass ← tokenClass bestPriority ← priority else if len == bestLen and len > 0 and priority < bestPriority: bestClass ← tokenClass // same length, higher priority wins bestPriority ← priority if bestLen == 0: report LEXICAL_ERROR at (pos, line) pos ← pos + 1 // error recovery: skip one char continue lexeme ← source[pos .. pos + bestLen - 1] attribute ← BUILD_ATTRIBUTE(bestClass, lexeme) // e.g. intern in // symbol table, parse // numeric literal if bestClass is not a DISCARD class (whitespace/comment already handled above): append (bestClass, attribute, line) to tokens pos ← pos + bestLen append (EOF, ε, line) to tokens return tokens ``` Two subroutines are doing real work here and deserve to be named explicitly. `LONGEST_PREFIX_MATCH(pattern, source, pos)` finds, for one pattern, the length of the longest prefix of `source` starting at `pos` that the pattern accepts — in a real implementation this is a DFA simulation that runs until it can no longer transition, remembering the last position at which it was in an accepting state. `BUILD_ATTRIBUTE` performs class-specific post-processing: interning an identifier lexeme into a symbol table (so repeated occurrences of `count` share one table entry) or converting a numeric lexeme's digits into an integer or floating-point value. The following diagram shows the pipeline view: a character stream flows through the scanner and out as a token stream, with the symbol table filled in as a side effect.

Time complexity. Assume the patterns are compiled into DFAs (the standard implementation, elaborated in Building Scanners with Finite Automata). Simulating a DFA on an input of length $\ell$ takes $O(\ell)$ time, since each character triggers exactly one table lookup and one state transition. The `TOKENIZE` loop advances `pos` by at least one character on every iteration (either by matching a lexeme of length $\ge 1$ or by the error-recovery skip), and every character is examined by the matching process a bounded number of times. If all patterns are merged into a single combined DFA — the standard scanner-generator technique — the whole tokenization pass runs in $O(n)$ time on an input of $n$ characters, independent of the number of token classes, because the combined automaton processes each input character exactly once regardless of how many original patterns it encodes. If patterns are instead tried one at a time as in the pseudocode above (a naive but illustrative version), the cost is $O(n \cdot k)$ for $k$ patterns, since each of the (amortized) $O(n)$ match attempts tries all $k$ patterns; real implementations always merge the automata precisely to eliminate this factor. Either way, lexical analysis is asymptotically linear in the size of the source, which is why it is never the bottleneck of compilation.

Space complexity. The automaton itself is $O(|P|)$ in the total size of the patterns, a constant with respect to the input. The token stream produced is $O(n)$ in the worst case (e.g., source consisting entirely of single-character tokens like `+++++...`), but $O(m)$ more precisely where $m \le n$ is the number of lexemes — in practice $m \ll n$ since identifiers and numbers are usually several characters long. The symbol table adds $O(u)$ space where $u$ is the number of unique identifiers, since repeated occurrences share one entry.

Correctness. The central correctness claim is that maximal munch plus rule priority produces a partition of the input that is (a) total — every non-whitespace, non-comment character is eventually consumed into some token — and (b) deterministic — the same input always yields the same token sequence. Totality holds by an inductive argument on the loop: at the start of every iteration, `pos` points to either end-of-input (loop terminates) or the start of an unconsumed suffix; the loop body either matches a nonzero-length lexeme (advancing `pos`) or reports an error and skips one character (also advancing `pos`), so `pos` strictly increases and the loop terminates after at most $n$ iterations having consumed every character. Determinism holds because `bestLen` and `bestClass` are computed by a total order — pick strictly longer matches, then break exact ties by a fixed priority ranking — so no two runs on the same input can produce a different winning pattern. A subtler correctness property is that maximal munch is the right disambiguation policy for real languages, not merely a convenient one. Consider the alternative "first match wins regardless of length": scanning `<=` with patterns for `<` (LESS) and `<=` (LEQ) listed in that order would greedily emit `LESS` for `<`, then fail to match `=` against any operator-starting pattern in the intended way, misparsing the input. Longest match avoids this class of error automatically, which is precisely why it is the near-universal convention in scanner generators such as `lex`/`flex` and in hand-written lexers alike. The one place this policy requires explicit help from rule priority is when the longest match is genuinely tied between two classes with different intended meaning — the canonical case being keywords versus identifiers, where `if` is simultaneously a maximal match for the identifier pattern and for the literal-keyword pattern of equal length, resolved only by declaring keyword patterns higher priority.

Honest tradeoffs. Linear-time, single-pass scanning assumes token boundaries can be found without looking arbitrarily far ahead or backward — true for most languages, but not universally. Some constructs need small bounded lookahead (distinguishing `.` as end-of-statement from `.` beginning a floating literal like `.5`), which a DFA handles fine since lookahead is folded into longer match attempts, not violating linearity. Genuinely context-sensitive lexical decisions — Python's significant indentation, or C++'s notorious `template>>` versus `>>` as a shift operator — cannot be resolved by a context-free DFA scan alone and require either a stateful lexer (tracking indentation levels on a stack) or cooperation with the parser (as C++ does for `>>`). These are documented exceptions, not failures of the theory: the pure token-DFA model is correct for the regular, context-free-at-the-lexical-level core that covers the overwhelming majority of language constructs.

Trace the scanner on the source line (with an intentionally tricky mix of an operator ambiguity, a keyword/identifier collision, and a floating literal): ``` if (x1 <= 3.14) x1 = x1+1; ``` Assume the pattern table (with priority: lower number = higher priority) is:

Final token stream: ``` (IF) (LPAREN) (ID,#1) (LEQ) (NUM,3.14) (RPAREN) (ID,#1) (ASSIGN) (ID,#1) (PLUS) (NUM,1) (SEMI) (EOF) ``` Notice three things the trace demonstrates concretely: the keyword/identifier tie at position 0 is resolved purely by priority since both patterns matched the same two characters; the `<`/`<=` tie at position 7 is resolved purely by length since `LEQ`'s match is strictly longer; and the symbol table collapses three occurrences of `x1` into one entry, which is exactly the space saving noted in the complexity section.

Every production compiler front end — GCC, LLVM/Clang, the Java and C# compilers, the V8 and SpiderMonkey JavaScript engines — begins with a lexical analysis phase structurally identical to what is described here, whether hand-written for speed (as in most industrial compilers) or generated from a specification (as with `flex`, ANTLR's lexer layer, or similar tools in other ecosystems). Beyond compilers, the same character-to-token reduction underlies JSON and XML parsers, configuration-file readers, regular-expression engines themselves, SQL query parsers in database engines, and syntax highlighters and language servers in editors like VS Code, which re-run lightweight lexers on every keystroke to colorize code in real time. Network protocol parsers and command-line shells performing word-splitting and quoting are, at heart, doing the same maximal-munch tokenization. Understanding lexical analysis is also the direct prerequisite for the two mechanisms that implement it in practice: Regular Expressions for Lexing, which formalizes the patterns, and Building Scanners with Finite Automata, which compiles those patterns into the linear-time automaton a real scanner runs.

Ask the tutor: How would you extend this scanner design to correctly handle Python-style significant indentation, which a single DFA cannot express on its own?