Lexer Design

A lexer slices source code into tokens for the parser while retaining enough information to support error reporting, formatting, and editing. The design focuses on clarifying input encoding, rule priority, position units, error behavior, and who owns the referenced source text.

Tokens: Classification, Raw Text, and Position Responsibilities

A representation suitable for immutable source snapshots is as follows. The integers in the example are decimal digit strings; only two operators are listed; actual languages can extend this further.

#[derive(Clone, Copy)]
struct Span {
    file: u32,
    revision: u64,
    start: usize,
    end: usize, // UTF-8 byte offset, half-open interval
}

enum Operator { Add, Subtract }
enum TokenKind {
    Identifier,
    Integer,
    Operator(Operator),
    Eof,
    Invalid,
}
struct Token {
    kind: TokenKind,
    span: Span,
}

The raw text can be sliced from a still-living snapshot via the span, eliminating the need to store a string copy for each token. Alternatively, one can borrow the text directly or intern identifiers as SymbolId; the key is to ensure references do not outlive the source buffer's lifetime. The raw spelling of strings and their escaped values should be distinguished, and syntactic recognition of numbers and target type overflow checks can be performed in separate phases.

The parser can determine it is an addition operator via Operator(Add); it does not require every operator to be a top-level enum variant. Granularity should serve the consumer, not be deduced inversely from the number of DFA states.

Matching Rules: Keywords Are Just One Classification Strategy

Prioritize the longest match, then resolve ties for equal-length matches. ifx should be treated as a complete identifier, not split into the keyword if and x.

Keywords can either be written directly into generator rules or recognized first as identifiers and then looked up in a keyword table. The former allows the automaton to share common prefixes; the latter facilitates centralized management of language versions and reserved words. Regular hash tables, perfect hash functions, sorted tables, or length-based branching all have their use cases; a small number of keywords does not necessarily lead to state explosion.

Contextual keywords might initially be retained as Identifier and then checked for positional validity by the parser. Raw identifiers, string interpolation, indentation tokens, and nested comments may require lexical states, a state stack, or counters. The boundary between the lexer and parser is a matter of language design and implementation choice; not all rules can be handled by a single regular expression.

Spans: Binding to Snapshots, Using Half-Open Intervals

[start, end) facilitates length calculation and slicing; an empty interval can also represent the insertion point for a missing token. Byte offsets are only valid within the source version they belong to: inserting a character at the beginning shifts all subsequent offsets. An IDE must re-parse using the new snapshot or translate via edit mappings; old offsets cannot be treated as stable identities across versions.

The line-start table stores the byte offset where each line begins, typically starting with 0. To find the line containing a position offset, you should find the last line start that is less than or equal to offset, rather than requiring offset to exactly hit a line start.

from bisect import bisect_right

def byte_line_column(line_starts, offset):
    # Precondition: the table belongs to the same snapshot, and 0 <= offset <= file byte count
    row = bisect_right(line_starts, offset) - 1
    return row + 1, offset - line_starts[row] + 1

assert byte_line_column([0, 6], 4) == (1, 5)
assert byte_line_column([0, 6], 6) == (2, 1)

This is the byte column, not the Unicode code-point column, UTF-16 column, or screen column. Tabs, combining characters, and wide characters also affect display width. When exchanging positions with editor protocols, convert according to the negotiated encoding; see the Language Server Protocol for relevant conventions. How CRLF counts as a single newline and how empty lines at the end of a file are represented must also be unified at the source file management layer.

Iteration Interface and Lookahead Buffer

The basic interface can simply be next_token(). The parser's token buffering layer then provides peek, advance, and expect. The first peek can trigger scanning, and subsequent peeks reuse the cache; there is no need to force all scanning to happen upfront just to claim peek is O(1).

Fixed-k lookahead can use a small queue. When supporting speculative parsing, checkpoints should cover the token cursor and relevant parser state; if the lexer is switched modes by the parser, rollback also requires restoring the mode or ensuring cache compatibility. You cannot assume all state is restored by simply rolling back the byte cursor.

EOF should be a stable terminal state. Repeatedly peeking at EOF from the upper layer should not trigger out-of-bounds errors; the recovery loop should not mistake repeatedly receiving EOF as making progress.

Input Management: Reading the Whole File or Streaming Windows Are Both Reasonable

Ordinary source files are often read entirely into an immutable buffer, facilitating span slicing, multiple analyses, and diagnostics. Reading the entire file is a valid design; whether it consumes too much memory depends on project scale, concurrent file count, and retention policies.

Streaming scanning reduces resident input, but tokens can still cross buffer boundaries. The implementation must retain incomplete tokens and rollback intervals, expanding, moving, or copying as necessary; long strings do not naturally lose validity just because they exceed 4 KiB.

Double buffering does not automatically imply parallel I/O and scanning; parallelism requires explicit asynchronous or threading mechanisms. mmap provides on-demand mapping but does not exempt you from considering file lifecycle, mapping invalidation, and random access costs. re2c leaves buffer refilling and boundary checking to integration code configuration. re2c Input Handling

End of Input Block Is Not Necessarily End of Token, Nor End of Character

Assume the first input block is exactly if. You cannot immediately output the keyword, because the next block might start with x, making the complete token ifx. The input block might also stop in the middle of the three UTF-8 bytes of the character 中; the decoder needs to wait for continuation bytes, and the lexer needs to wait for enough characters to determine the token boundary. The two layers of state have distinct responsibilities.

The following implementation uses a small batch feed interface: identifiers are limited to ASCII, keywords are only if, integers accept only decimal digits; operators are = and ==, and whitespace is only space/tab/CR/LF. Other valid Unicode code points produce Invalid, and illegal UTF-8 terminates and throws a decoding error. This is not treating 中 or emoji as "illegal UTF-8".

import codecs
import re

class StreamingLexer:
    def __init__(self):
        self.decoder = codecs.getincrementaldecoder("utf-8")("strict")
        self.pending = ""
        self.offset = 0
        self.closed = False

    def feed(self, data, final=False):
        if self.closed:
            raise ValueError("input already finalized")
        self.pending += self.decoder.decode(data, final=final)
        result = []
        while self.pending:
            first = self.pending[0]
            match = re.match(r"[A-Za-z_][A-Za-z_0-9]*|[0-9]+", self.pending)
            if match:
                text = match.group()
                if len(text) == len(self.pending) and not final:
                    break  # Might have more identifier/digit characters
                kind = "If" if text == "if" else "Integer" if text[0].isdigit() else "Identifier"
            elif first == "=":
                if len(self.pending) == 1 and not final:
                    break  # Next block might extend = to ==
                text = "==" if self.pending.startswith("==") else "="
                kind = "Equal" if text == "==" else "Assign"
            else:
                text = first
                kind = "Whitespace" if first in " \t\r\n" else "Invalid"
            end = self.offset + len(text.encode("utf-8"))
            if kind != "Whitespace":
                result.append((kind, text, self.offset, end))
            self.offset = end
            self.pending = self.pending[len(text):]
        if final:
            self.closed = True
            result.append(("Eof", "", self.offset, self.offset))
        return result


def lex_chunks(chunks):
    lexer, result = StreamingLexer(), []
    for chunk in chunks:
        result.extend(lexer.feed(chunk))
    return result + lexer.feed(b"", final=True)

raw = "ifx == 中 😀 if 12".encode("utf-8")
expected = lex_chunks([raw])
assert [(kind, text) for kind, text, start, end in expected] == [
    ("Identifier", "ifx"), ("Equal", "=="), ("Invalid", "中"),
    ("Invalid", "😀"), ("If", "if"), ("Integer", "12"), ("Eof", "")]
for cut in range(len(raw) + 1):
    assert lex_chunks([raw[:cut], raw[cut:]]) == expected
assert lex_chunks([bytes([b]) for b in raw]) == expected
for kind, text, start, end in expected:
    assert raw[start:end].decode("utf-8") == text
for invalid in (b"\xff", b"\xe4\xb8", b"\xc0\xaf"):
    try:
        lex_chunks([invalid])
    except UnicodeDecodeError:
        pass
    else:
        raise AssertionError("invalid UTF-8 accepted")

Trying every possible byte cut point simultaneously covers cuts within if/x, =/=, and inside 中 and emoji. The raw text and byte intervals of the output tokens should be completely consistent, regardless of I/O chunking. The ending final=True is crucial: it classifies the pending if as a keyword and requires the decoder to report incomplete UTF-8 sequences. Python Incremental Decoder Interface

This teaching implementation copies the pending string and re-matches from the start for long tokens that haven't ended, so it has no linear time or fixed memory guarantees; a real streaming lexer should save scan state and cursor, and set reasonable resource budgets. It also skips whitespace, failing to form a lossless token stream. After feed is closed, it refuses to accept more data; a peek/next wrapper layer for the parser can cache the final Eof to implement stable termination queries.

When Bytes Arrive, Are Characters and Tokens Complete?

Reception progress cannot be directly equated with scanning completion progress. The following deliberately stops the slider after if, after a single equals sign, in the middle of the Chinese character's bytes, and in the middle of the emoji's bytes: these positions lack either token boundary evidence or complete characters. Confirmed tokens use raw byte intervals; bytes not yet decoded are not disguised as illegal Unicode characters. EOF is an additional fact; declaring EOF early might yield a valid short input or a truncation error.

Unicode: Decoding Rules and Identifier Rules Are Separate

UTF-8 decoding requires checking continuation bytes, overlong encodings, surrogate code points, and code point limits; you cannot blindly skip bytes based solely on the first byte's length. If the input type already guarantees valid UTF-8, you can leverage standard library iteration boundaries; otherwise, first decide on the diagnostic and recovery strategy for illegal bytes.

After decoding to code points, you must also determine if the identifier is valid according to the language specification. Rust uses rules related to XID_Start and XID_Continue, allows underscores, and specifies requirements such as NFC normalization; single underscores and raw identifiers have additional rules. \w is not a universal language identifier specification. Rust Identifiers

Normalized symbol comparison and raw source spelling can be retained simultaneously: name resolution uses the normalized form, while diagnostics still highlight user input. Unicode versions are also part of language compatibility.

Error Recovery: Consumption Strategy Must Match Current State

Illegal characters can generate an Invalid token and consume one valid code point; illegal UTF-8 advances according to the established byte recovery strategy. Unclosed strings, comments, or interpolations need their own termination conditions and cannot uniformly "skip one character". When multi-line strings are valid, newlines are certainly not error boundaries.

A single recovery step should consume input, change state, and guarantee that the next step can proceed, or explicitly stop at EOF. Generating placeholder tokens but staying in the same position repeatedly reporting the same error leads to infinite loops. Diagnostics can be returned separately from tokens, letting the parser know the error interval without having to repeatedly report the same lexical issue.

Hand-Written vs. Generator

The choice should be supported by language rules and measurement results. Both must verify longest match, cross-buffer tokens, Unicode boundaries, EOF, and recovery progress. For how to compose tokens into a tree retaining error information, see AST Design and Error Recovery.

Keywords: lexer, token, span, source snapshot, maximal munch, lookahead, Unicode, UTF-8, line table, recovery, re2c