Syntax | Atoll Book

atoll-syntax owns the lossless-enough source model required by analysis and editor tooling: typed tokens, interned strings, source ranges, diagnostics, and an arena-backed AST. It deliberately does not resolve names or assign types.

Data flow

UTF-8 source bytes
    ↓ lexer
Token { kind, range }
    ↓ recursive-descent parser
Ast arenas + StringInterner + diagnostics

Lexing and parsing return diagnostics alongside usable outputs. Consumers do not need to choose between “tree” and “errors”; recovery keeps later declarations available whenever the parser can find a safe boundary.

Tokens and ranges

The lexer classifies punctuation, operators, literals, identifiers, keywords, comments, and whitespace-sensitive boundaries. Every token is anchored to a byte range. LineMap converts byte offsets into user-facing line and column locations when a diagnostic is rendered.

Byte offsets are the stable internal coordinate. Line and column values depend on the complete source text and are derived for display. Compiler stages should carry ranges forward rather than storing formatted locations or slicing source text repeatedly.

Malformed tokens produce syntax diagnostics. The lexer must still advance: failure to consume input would trap the parser in an infinite recovery loop.

Arena AST

AST nodes are stored in flat typed arenas. A parent refers to children through typed IDs or compact ranges of IDs rather than Box pointers:

Property	Consequence
Typed arena IDs	A declaration ID cannot accidentally index an expression arena
Dense vectors	Traversal and bulk allocation have predictable locality
Interned strings	Nodes carry compact `StringId` handles instead of owned strings
Explicit ranges	Lists of parameters, fields, statements, and arms avoid linked allocation
In-process lifetime	No AST serialization contract constrains internal layout

IDs are meaningful only with the AST and interner that created them. Persisting an integer ID or comparing it across independent parses is invalid. Cross-edit tools should use source anchors and the incremental APIs designed for that purpose.

Parser structure

The handwritten recursive-descent parser is split by grammar domain: declarations, statements, expressions, patterns, types, and specialized forms. This makes precedence and recovery policy local to the construct that owns it.

The parser’s job is structural:

establish grouping and precedence;
distinguish declarations, patterns, types, and expressions;
preserve modifiers, decorators, and annotations;
create missing/error nodes where recovery requires them;
report an unexpected or incomplete form at the closest useful range.

It does not decide whether a symbol exists, a call is legal, a pattern is exhaustive, or an effect is permitted. Those questions require project context and belong to Analysis.

Recovery

Recovery is part of the syntax contract, not an afterthought. A parser error should satisfy three properties:

Locality: point at the token or missing boundary that prevented the production from completing.
Progress: consume or synthesize enough structure to avoid reporting the same error forever.
Containment: synchronize at a delimiter or declaration boundary so unrelated later code remains parseable.

Recovered nodes must never be mistaken for checked source. Semantic analysis can suppress derivative errors around explicit syntax-error nodes while still checking unaffected declarations.

Incremental parsing

The crate exposes cold parse, incremental relex, and incremental reparse entry points. A long-lived editor path can retain parse state, apply a text edit, relex the affected region, and reuse unaffected arena content when the edit is eligible. The implementation may fall back to a cold parse when safe reuse cannot be proven.

That fallback is a correctness feature. Incremental and cold parsing of the same complete text must be observationally equivalent for downstream stages: same accepted structure, source ranges, and diagnostics. Performance must not create a second grammar.

atoll-db memoizes parsing per SourceFile. Unedited files retain their shared Arc<ParsedFile> even when another file changes. The language server can additionally supply an incrementally updated parse for the exact same file contents; a content mismatch bypasses that cache.

Extension checklist

Adding syntax requires more than an AST variant:

add or reuse token kinds and keyword handling;
define the arena node and all child ranges;
implement parsing at the correct precedence or declaration layer;
add malformed-input and recovery tests;
update source indexing and incremental remapping where the new node carries IDs;
add semantic lowering before documenting the construct as checked.

If only the first three steps exist, the feature is represented, not implemented. See Feature Status for the book’s maturity ladder.

Debugging syntax

When a later compiler failure appears syntax-related, isolate the boundary:

inspect the token stream for keyword or literal classification;
dump the AST and confirm the expected node shape and range;
compare cold and incremental parse results for edit-only failures;
reduce malformed input until the first recovery diagnostic is clear;
do not patch semantic analysis to compensate for a structurally wrong AST.

The AST is the first durable statement of what the source contains. Every later source mapping depends on getting that statement and its ranges right.