5.1 Token Contracts and Source Positions: Passing Characters to the Parser

The previous theoretical discussion established boundaries: regular languages are well-suited for describing many token rules, context-free grammars for nested syntax, while Turing machines and undecidability remind us that analytical power is not infinite. In this chapter, we move beyond theory and build a lexer that reports positions and errors, starting from these boundaries.

int count = 42;

This can be broken down into:

KW_INT  IDENT(count)  ASSIGN  INT(42)  SEMICOLON  EOF

Learning Objectives

• Define the token contract between lexer and parser;
• Distinguish between token kind, lexeme, and parsed value;
• Design byte offsets, line-and-column positions, and span accurately;
• Determine how whitespace, comments, keywords, and lexical errors should be handled.

1. Token Kind, Position, and Optional Value

A practical token typically includes:

kind    Type, such as IDENT, INTEGER, PLUS
span    The start and end positions in the source file
value   An optional normalized or parsed result

lexeme represents a raw slice from the source file. In a teaching language that permits leading-zero decimal literals, 0012 has kind INTEGER, lexeme 0012, and value 12. This is language-specific: C interprets a leading-zero integer literal as octal. Preserving the raw slice aids in error reporting, formatting, and refactoring; storing only the value loses the original syntax.

Do not confuse kind and lexeme: both identifiers belong to IDENT, and the same + can have different meanings depending on the language mode.

2. Span Uses Half-Open Intervals

Commonly represented as:

$$[start,end)$$

Includes start and excludes end. The length is end - start, and adjacent token boundaries can be directly concatenated.

Positions can be stored simultaneously:

• Byte offset: most reliable for slicing and integration with file APIs;
• Line and column: useful for user-facing display;
• File ID: supports multi-file contexts, macro expansion, and include processing;
• Origin chain: maps generated code or macro tokens back to their original source.

Offsets must use the same unit as the sliced buffer. A lexer counting positions in a Python string gets code-point offsets, which cannot directly index the original UTF-8 bytes. In 中a, a starts at UTF-8 byte offset 3 but code-point offset 1.

The "column" must specify whether it is calculated based on bytes, Unicode code points, grapheme clusters, or display width. Tabs and full-width characters can cause display columns to differ from byte offsets. Internally, compilers typically use byte offsets as the authoritative position, then compute display positions during diagnostics rendering.

3. Input decoding is a contract before lexical analysis

The source file begins as bytes. The lexer either receives a decoded character stream or handles the decoding itself, and must clearly specify:

• The encoding it expects;
• How to report invalid byte sequences;
• Whether line endings are normalized to LF, CRLF, or CR;
• Whether Unicode identifiers are permitted;
• Whether Unicode normalization is applied.

If decoding normalizes newlines or Unicode, retain a mapping to the original file. Offsets in transformed text need not equal original byte offsets.

Different Unicode characters may appear visually similar, and normalization can alter the equality relationship between identifiers. If a language specification allows Unicode identifiers, it must explicitly define which character properties and versions are used, never simply relying on a library function isalpha as a complete language rule.

4. Are Whitespace and Comments Becoming Tokens?

Compilers' parsers typically don't need ordinary whitespace or comments, lexers can route them into trivia channels or simply skip them. However, formatters, IDEs, and source transformation tools require that such elements be preserved, at a minimum, so they can be associated with adjacent tokens.

Three common strategies:

• Discard trivia entirely: simplest for compilers;
• Output trivia as standalone tokens: preserves fidelity, but parsers must filter them out;
• Attach trivia to the before-and-after of syntax tokens: enables construction of lossless syntax trees.

The choice depends on downstream consumers. If a project requires both compilation and formatting, the minimal token structure of the compilation path should not constrain all tools.

5. Identifiers and Keywords Share the Same Scanning Rules

First, scan the longest possible lexeme according to identifier rules, then check against the keyword table:

if   → scanned as an identifier shape → matches keyword table → KW_IF
ifx  → scanned as an identifier shape → no match → IDENT

ifx will not fall back to if plus x, because the entire ifx forms a longer and valid identifier. The longest match determines token boundaries; when lexemes are of equal length, the priority rule decides the token kind.

Contextual keywords (such as those found in certain languages (e.g., async)) may initially remain as IDENT in the lexer, with interpretation deferred to the parser based on context. Alternatively, they may be categorized using lexer modes. Fixing such tokens as keywords too early can compromise backward compatibility.

6. Literals Have Original Form, Value, and Error State

In a language supporting hexadecimal and underscore digit separators, the literals 0xff, 255, and 2_55 might evaluate to the same numeric value but have different lexemes. Parsing a literal requires at least two steps:

1. Determine character boundaries and the base form;
2. Remove digit separators, determine the base, detect overflow, and convert the value.

Whether the lexer processes numeric literals depends on the architecture. Regardless of the layer where parsing occurs, silent overflow must be avoided, and the original source span must be preserved.

Strings are more complex:

• The raw lexeme includes quotes and escape sequences;
• Decoding the value converts \n into a newline;
• Invalid escape sequences must have precise error positions;
• Interpolated strings may switch between text and expression modes.

7. Error Tokens Allow Tools to Continue Working

When encountering unknown characters, a lexer can:

• Immediately halt and report an error;
• Emit an ERROR token and continue parsing;
• Record a diagnostic and skip a bounded, controllable range of input.

Batch compilers may stop on the first error, but IDEs require resilience, continuing to provide autocompletion. Recovery must ensure forward progress: at least one input unit must be consumed, otherwise recovery could loop forever at the same position.

EOF should also be treated as a well-defined token with a zero-length span. This enables the parser to distinguish between "expected closing parenthesis but reached end of file" and a typical mismatched character.

8. Token Contract Example

This C99+ declaration stores only kind and span; value parsing belongs to a later stage:

#include <stddef.h>

typedef enum {
    TOK_EOF,
    TOK_ERROR,
    TOK_IDENTIFIER,
    TOK_INTEGER,
    TOK_KW_INT,
    TOK_ASSIGN,
    TOK_SEMICOLON
} TokenKind;

typedef struct {
    size_t start;   // inclusive byte offset
    size_t end;     // exclusive byte offset
    size_t line;    // 1-based line number
    size_t column;  // contract must define its unit
} SourceSpan;

typedef struct {
    TokenKind kind;
    SourceSpan span;
} Token;

Here, the lexeme is not copied; the caller can slice from an immutable source buffer using [start,end). The source buffer must outlive every token referring to it. A source store can retain it, or tokens can own the text they need. IDE tokens also need a source version: an old offset into a newly edited buffer may select entirely different text.

Common Misconceptions

• Tokens only need a type: Diagnostics, IDEs, and refactoring tools require at least a span to function properly.
• Character position equals byte position: In UTF-8, a single character can span multiple bytes.
• Whitespace has no semantic meaning, so it can be discarded entirely: Python indentation, preprocessor line joining, and formatting tools are counterexamples.
• Errors don’t consume input, so processing can continue: This can cause recovery loops to get stuck at the same position.

Exercise

1. Identify the half-open byte ranges for each token in int count = 42;.
2. Design a trivia storage scheme that supports both compilers and formatters.
3. Explain how if and ifx should be processed using "longest match + keyword table".
4. Specify the span and recovery position for the ERROR token when a string is not properly closed.

Summary

The output of a lexer is not a fragmented string of text, but a stable interface: the kind tells the parser what was seen, the span allows diagnostics to map back to the source file, and lexeme and value preserve the distinction between the literal form and its interpretation.

In the next lesson, we will implement this interface and check buffer boundaries, EOF, ctype input ranges, and two-character operators. Agree on coordinate units first, so diagnostics do not point accusingly at the wrong character.