Lexer Design

From token representation to buffer management to Unicode handling — an engineering-focused lexer considers far more than automata theory; the quality of position tracking and error recovery directly determines the user experience of compiler error messages.

Overview

Regular Expressions and Automata covered the mathematical foundations of lexical analysis — regular expressions → NFA → DFA → minimization. This article covers engineering: how to design a real-world lexer, including token kinds, disambiguating keywords from identifiers, tracking source positions, error recovery, and the choice between hand-written vs. generated lexers. These are not "nice-to-haves" — the quality of position tracking and error recovery directly determines the user experience of downstream compilation errors, yet these aspects are often glossed over in textbooks.

Token Kind Design

A token requires at least three fields:

Token {
    kind: TokenKind,       ← Enum: Number, Plus, Identifier, If, ...
    text: &str,            ← Actual text from source (e.g., "42", "+", "my_var")
    span: Span,            ← Position in source (start line/col → end line/col)
}

Separating kind and text is a key design choice: kind is used by the parser (which makes decisions based on token kinds, e.g., entering if-statement parsing upon seeing If); text is used for semantic analysis and error reporting (e.g., the numeric value of 42 is 42, and highlighting the source string "my_var" during errors).

Token kind design follows two mutually constraining principles: the granularity required by the parser (each operator needs its own kind, e.g., +, -, * each have a distinct kind, otherwise the parser cannot make decisions) and consistency in lexer recognition (the token type must be determinable within a single DFA state).

Keywords do not take separate DFA branches in the lexer — the lexer only recognizes "an identifier" (starting with a letter, followed by digits/underscores), then looks it up in a keyword table:

Identifier "if" recognized → lookup_keyword("if") → TokenKind::If
Identifier "myvar" recognized → lookup_keyword("myvar") → not in table → TokenKind::Identifier

The keyword table is typically a perfect hash or trie constructed at compile time, offering lookup in O(1) or O(len) time. This is cleaner than creating separate terminal states for each keyword in the DFA — state explosion in the DFA is a real risk (every distinct prefix of every keyword becomes a different state).

Position Tracking: The World of Lines

Source code is a one-dimensional byte stream, but errors must be translated back into human-readable line:column. The lexer must track two quantities:

Current offset:     Byte offset from the file header to the current character (span start/end use offset)
Current line:       1-based
Current column:     1-based (or 0-based, depending on editor conventions)

Upon encountering a newline \n (or \r\n): line += 1, column = 1, offset += length of newline.

Span stores offset rather than line/col — offset can be used directly to "slice this source code from the file" (substring) and does not require knowing newline positions. line/col are only inferred from offset + line start offset table (line table) when reporting errors:

line_table: Vec<offset>   ← Offset of the first character of each line in the file

span_to_linecol(span):
    line = line_table.binary_search(span.start).unwrap() + 1
    col = span.start - line_table[line - 1] + 1

Why infer rather than store directly? Because the same source position may be queried multiple times in diagnostics (e.g., multiple passes report errors on the same line). Storing offset is stable (does not change with file edits, which is crucial in IDE incremental re-parsing), while line/col can be re-derived from offset + line table.

peek / consume / unget: The Lexer's Control Interface

The interface exposed by the lexer to the parser consists of only a few operations:

• peek(): Returns the current token without consuming it (reading a token does not advance). The parser uses this for branching decisions — "if the next token is +, take this path; if *, take that path".
• consume(): Returns the current token and advances to the next.
• consume(kind): Asserts that the current token must be kind, otherwise errors — used when the parser knows the expected syntax structure (e.g., after "consuming (", a ) is expected).

peek is the most frequent parser operation (called for every decision) and must be O(1) — meaning the lexer must have already scanned the next token before peek is called. In implementation, the lexer always "scans one token ahead" and caches it; peek returns the cache directly, and consume returns the cache and triggers the next scan.

Note: The consume(kind) API has different responsibilities in different implementations. Some lexers provide consume(kind) at the lexer layer for asserted consumption; more commonly, this is the parser's responsibility — the parser calls peek() to get the token, compares token.kind == expected, and then decides whether to call consume(). Regardless of the approach, the semantics are consistent.

Buffer Management: Large Files and Streaming Input

You cannot read the entire file into a single String for lexical analysis — large files will cause memory exhaustion. Lexers use ring buffers or double buffering:

Ring Buffer:
  Maintains a fixed-size window (e.g., 4KB), pointing to the current scan position.
  Consumed data is discarded.
  When approaching the end of the window, the next chunk is read from the file into the beginning of the buffer.

  However, tokens cannot be split across buffer boundaries → the lexer ensures the buffer is advanced only when no lookback is needed.

Double buffering (two alternating buffers filled in turn) is a classic approach used by flex — YY_BUFFER_SIZE defaults to 16KB. When the current buffer is consumed, it switches to the other pre-filled buffer, allowing IO and scanning to proceed in parallel.

In modern contexts, memory is generally abundant, and many implementations simply mmap the entire file into the virtual address space — the OS loads pages on demand, and the compiler does not need its own buffer logic. However, the lexer still needs to track offsets to support span construction.

Unicode: The Alphabet of Tokens is No Longer 128 ASCII Characters

In the C era, lexers only handled ASCII — 128 characters, each 1 byte. Modern languages (Rust, Go, Swift) support Unicode at the source level:

• Identifiers can contain Unicode letters (的, 蛇, é, α).
• The character class \w is no longer equivalent to [a-zA-Z0-9_] — Rust's identifier character class is XID_Start + XID_Continue (characters deemed "safe for programming language identifiers" as defined by the Unicode standard).

The strategy for lexers to handle Unicode is to keep the tokenizer operating at the byte level, recognizing multi-byte sequences according to UTF-8 rules:

When recognizing an identifier:
  Scan byte by byte.
  If ASCII letter/digit/underscore → consume 1 byte, continue.
  If UTF-8 multi-byte start byte (quickly determined via bit pattern: 110xxxxx=2 bytes, 1110xxxx=3 bytes, 11110xxx=4 bytes)
    → Consume the complete sequence according to rules, decode the code point.
  Check Unicode table to confirm if the code point is in XID_Start/XID_Continue.
  Otherwise: identifier ends.

There is no need to pre-decode the entire file into a Vec<char> — only decode the current character when a multi-byte sequence is encountered, maintaining memory efficiency.

Error Recovery: The Lexer Must Not Crash

When the lexer encounters an illegal character (@ in C, an unclosed string literal), it must not crash. It must:

1. Report the error (which line/column, what the illegal character is).
2. Skip the character and continue scanning — without interrupting the parser's subsequent work (allowing users to see all lexical errors in one compilation run, rather than fixing one and reporting another).

Unclosed strings are the most common lexical error:

"hello world          ← Missing closing quote

Handling: When " is followed by end-of-line or EOF without closure → report "unterminated string literal, expected closing "", pretend to close it at the current position (or skip the entire line), and continue scanning.

Hand-written vs. Generator: Real-world Choices in Industry

The vast majority of industrial compilers are hand-written — because the quality of compilation error messages is the face of the product, and generators cannot compete with hand-written code in this regard. The greatest value of generators lies in the automatic conversion of "regular expressions to DFA" (eliminating the need for manual subset construction), but mixing generated DFAs with hand-written error recovery leads to poor maintainability.

Clang's lexer is a paradigm of hand-written design: the consumption logic for each token kind is clear and readable, branching is done for each character class or token start, and error recovery strategies are embedded within the handling logic for each token type.

References

• flex manual: The Fast Lexical Analyzer — Complete usage of the generator, buffer management, YY_CURRENT_BUFFER
• re2c: http://re2c.org — Another generator approach, producing embedded code rather than full DFA tables
• Clang: lib/Lex/Lexer.cpp — The industrial benchmark for hand-written lexers, covering line numbers, buffers, and error recovery

Keywords: lexer design, token kind, span, line/column tracking, line table, peek, consume, unget, ring buffer, double buffer, mmap, Unicode, XID_Start, XID_Continue, UTF-8, identifier, keyword table, error recovery, invalid character, unterminated string, hand-written lexer, lexer generator, flex, re2c