Nikaia
Menu
v0.0.1343pre-alpha GitHub

ADR-296: A Grammar Is Part of the Language — Scannerless, Entered by a Call to Any pub Rule, Cut in Parallel Only Where a Checked Frame Says So, Lowered Name for Name, and Its Actions Neither Pause Nor Fail Without a Name

Status: Accepted Date: October 3, 2026 History: the records this one replaces are archived in docs/history/adr; read them only for how the decision was reached Answers: what the core parser is, and how foreign syntax ends and binds its holes; where a format assumption may be written so that a parse can be cut and run on several cores; what the lowering of a grammar onto the parser backend is and refuses to do; how a program enters a grammar, and which rule it enters through; whether a fold’s lambdas are checked (#237); what a grammar may write, from one page (#202, language-review.md §3.6); whether an action may pause; what a parse fails with Related: ADR-001 D2 and D4 (the parser backend; Stage 0 is a transpiler) · ADR-005 D4, ADR-283 D11 (the tether a view takes; content equality on views) · ADR-297 (cleanup always runs, the rule D15 relaxes) · ADR-010 (the hasher, chosen by provenance) · ADR-300 (errors reported against the .nika line) · ADR-013 (the fold adapter D17 left to a typing pass) · ADR-014 (the mapping and the parallel driver) · ADR-023 (the grammar’s bindings and its commit-point failure) · ADR-037 D1 (a switch selects a build, not a dialect) · ADR-292 and Part II 12.6 (the other places sync is demanded) · ADR-310 (asset("…"), what a build may read) · ADR-276 D16, D18 (the jump walk D31 replaced, and the lowering’s backstop that stays) · ADR-133 D3 (an options-only call writes no ;) · ADR-140 D3 (a path is ::) · ADR-177 (a grammar runs at build time by compiling the parser it generates) · ADR-186 (what an entry keeps) · ADR-280 (how a failure travels; #179) · ADR-309 (an f"…"’s holes, which are the language’s own grammar and not this protocol)

1. Question

What is a grammar in Nikaia - and what does the language promise about how it reads its input, how a program enters it, when its parse may run on several cores, how it reaches the language below, and what its actions may do?

One record, because every answer leans on the first: the core parser keeps no global token stream, so foreign syntax can be embedded (D1). That makes a grammar a construct of the language rather than a library, so its entry is an ordinary call (D24), its actions are ordinary code checked like any other (D28, D35), and what it fails with is an ordinary named type (D38). And because a grammar is already the file’s specification, it is the one place a format assumption may be written so that a parse can be cut blindly and run in parallel (D9-D13).

Without the answers the compiler cannot verify a frame, cannot know which rule a call enters, cannot tell a program what a parse threw, and leaves to the backend’s error - against a file nobody wrote - every defect in an action.

2. How others do it

Language / tool Its answer Source
winnow-grammar (the backend) parses &str/&[u8], no token stream; uppercase rules lexical, lowercase syntactic; => the cut; recover(rule, sync); one function per public rule, no main rule; action blocks required, no auto-AST D25; ADR-001 D2
ANTLR uppercase names are lexer rules D33’s neighbours, §6
pest a WHITESPACE rule steers implicit skipping; actions live outside the grammar D22, §6
Ohm semantic actions kept outside the grammar D33
The fast reference implementations of the one-billion-rows workload split the buffer blindly, repair the seam; find the separator a word at a time; hash a key from its first bytes, and some also compare only the first 8-16 bytes (unsound) D11, D12, D14
Rust asm! register constraints in the core language - what D6 removes, because WebAssembly is a stack machine D6

What transfers: the backend’s model is adopted as the language’s (D1, D25), and the case convention, WS and the cut stay with their precedent (D33’s neighbours, §6). What does not (as a construct of the language; a program may read words and scan by hand, ADR-320 D12): hand-written SWAR in user code, which is unreadable and unportable - the grammar states the assumption and the compiler exploits it (D12, D13).

3. Options, weighed

Option Why it lost See
A global lexer cannot tokenize embedded languages whose delimiters conflict (JSON’s }, Rust’s 'a) D1
A configurable or inferred DSL terminator reintroduces the delimiter ambiguity scannerless parsing removes D2
unsafe asm in the core with a WASM special case a second, register-free syntax: a DSL with extra steps and a permanent fork in the core D6
One binding mechanism for holes scope binding is right for assembly and destroys the reuse of a prepared statement D4
sync rule as the frame marker sync already has two meanings D9
Rewriting until(";") reached from a frame into until ; or newline the same rule text would parse differently depending on what reached it D9
split_aligned(n, "\n") by hand asks the user to restate what the grammar knows and to write the pipeline that follows D10
Parallelising any associative-looking fold a merge over f64 is not associative; output would depend on the core count D10
Inferring the boundary without a marker an unrelated edit would silently stop a grammar being parallel D9
Comparing only a key’s first bytes two keys sharing a prefix merge silently D14
A user-facing SWAR/SIMD construct hardware instructions live behind a backend DSL (D6); a library’s portable lanes and safe instruction functions are ADR-371’s D12
The grammar body kept as text answers none of the questions the lowering asks D16
A second frame check in Nikaia two verdicts drift; the provenance fix is spans D18
Inferring accumulator threading from a step’s shape acc.merged(m) has the shape of acc.record(m) and would be mis-lowered D17
A switch that changes more than the executor two settings that mean different things are two languages D19
dsl G from e kept; a distinguished entry rule two namespaces under one keyword; the emitter’s first pub rule pick chose wrong silently D25
A parse alias a name that appears and disappears with its neighbours D26
A second walk over a fold’s lambdas two walks over one construct are two chances to disagree, and the old one gave wrong advice D31
token NAME, a skip declaration, a change to => or # "…" each convention has precedent §6
Fields on the parse error now nobody has asked; the smaller answer can be taken back D39

4. Decision

D1 — Scannerless parsing is a language guarantee, not an implementation detail.

The core parser keeps no global token stream. A grammar consumes the raw character stream, and whitespace handling is a property of the rule. The consequence is accepted: Nikaia can never adopt a token-stream frontend without breaking dsl.

D2 — A DSL block ends explicitly, with } eod.

The core parser cannot find the end of foreign syntax by counting braces, so it scans for the marker, skips the body and parses the rest of the file while the DSL parser works. A body that contains the literal } eod is read from a file and handed to its grammar by a call (D24, D27), never by a configurable terminator.

D3 — One spelling at build time and at run time; when is said by comptime, where the bytes come from by asset("…").

comptime CONFIG: Json::Value = Json::value(asset("config.json"))
let data = Json::value(user_input)
let query = dsl mysql { … } eod

A parse has one spelling at either stage, and its position never decides its meaning: the same call reads its argument’s text at run time, and at build time only because comptime asks for it and asset names the file. A dsl block is an expression. How a grammar runs while the program is built is ADR-177; what a build may read is ADR-310.

D4 — A hole binds in one of two ways, and the grammar author says which.

meta::capture(id) is immediate, resolved from the surrounding scope at compile time (assembly: $v = in(reg) val means this val). meta::parameter(name, type) is deferred, a named runtime parameter (a prepared statement, which baking values in would destroy). It is the same immediate/deferred axis as lambda capture and teardown (ADR-297 D5), and Part II 10.5 states it as a principle.

D5 — A DSL with deferred parameters generates a shadow type.

The :name holes of a body become a type the call site is checked against: a missing name is NK1112, an unknown one NK1113, on the .nika line. The parameters are configuration, passed as named arguments after the subject - query.execute(db; target_age: min_age), or stm.execute(target_id: 501) with no ; when there is no subject (ADR-133 D3) - and a driver receives them with the typed spread ...args: Self::dsl, which keeps its ; in the signature. Following D17, the field types come from the call site (the struct is generic and monomorphised where it is built), there is one struct per parameter list rather than per DSL string, Self::dsl also names the result, and a hole is found by scanning, so SELECT ':id' is read as one until a grammar’s meta::parameter says otherwise. The driver’s own half, args.values(), needs a value type for the parameters and is not decided further here. Flagged as the least proven decision of the protocol.

D6 — Hardware instructions leave the language core.

unsafe asm, its register-constraint table and clobber are removed. Assembly is a library DSL, dsl x86::Asm { … } eod (ADR-299 D20), using D4’s immediate capture. A core construct that cannot be given meaning on WebAssembly, a stack machine, is a defect in the core. unsafe stays reserved for FFI.

D7 — Auto-AST and regex terminals are goals, not behaviour.

Actions are required (no generated structs for labelled sequences); fixed built-in terminals meet the intent of regex terminals. Specification text promises neither.

D8 — Zero-copy is two mechanisms, and the grammar picks per rule.

Identifiers and keywords are interned Symbols; bulk text (string literals, comments, doc text, DSL bodies) is a tethered slice (ADR-005 D4, ADR-283 D11). The guarantee is stated positively: the source buffer cannot be freed while a token points into it.

D9 — @frame declares a resynchronisation unit, and the compiler checks it; it never rewrites the grammar.

rule NAME -> ref String = s:until(";" | frame_end) { s }

@frame(boundary: "\n")
rule MEASUREMENT -> Reading = name:NAME ";" => temp:TENTHS frame_end { Reading { name, temp } }

A frame can be found from any offset by scanning to its boundary. The frontend walks everything the rule reaches; safe: a literal without the boundary, a built-in whose alphabet excludes it, lookahead, an until(t) whose terminator covers the boundary (frame_end, the boundary literal or a prefix of it, line_ending for a newline); rejected, naming rule and pattern: a literal containing it, a built-in that can consume it (any, multispace0), the implicit whitespace of a syntactic rule, an until that does not cover it (the message says until(… | frame_end)), and recover(…) - recover per frame instead, (item | until(frame_end)) frame_end. frame_end names the boundary of the frame the rule is reached from and resolves statically. The attribute is keyed - @frame, @frame(boundary: "\n"), @frame(boundary: "\n", unchecked) - and unchecked is the greppable assertion for formats a byte string cannot cut (quotes, start markers, escapes), each a future key. A frame ends in its boundary. A syntactic (lowercase) rule the frame reaches skips whitespace before each element, so it is refused unless the grammar declares its own WS, which is then checked as part of what the frame reaches. The par_fold rule that folds the frames skips no whitespace whatever its name - not at its entry, not at its start, not between frames - so whitespace between frames is not a frame and fails at any chunk count (D10).

D10 — Parallel parsing is a frame plus a monoid: par_fold, written, never inferred.

par_fold(ITEM, init, step, merge) is fold plus a merge, over an @frame item, and the whole body of its rule; the split, seam repair, per-chunk accumulators and merge are generated, and the program writes Measurements::file(data). A written par_fold says results from different chunk counts are the same to me. Chunk count changes neither what is accepted nor what is rejected: a par_fold rule is lexical in all but name (D9). At user_parallelism = no it is a sequential fold - same accumulator, same merge, same result - which keeps it compiling for wasm32.

D11 — The lowering is a blind split, then a seam repair.

n equal byte ranges (n = cpu::count() by default); every chunk but the first advances past the first boundary at or after its start, so each frame is owned by exactly one chunk, the one that finds its end; the last runs to EOF, an unterminated last frame is still yielded and no empty trailing frame is; a frame longer than a chunk is not an error; errors carry absolute offsets, and under recover one chunk’s failure does not abort the others; chunk count does not change results and is overridable for benchmarking. The driver takes Parallelism::Off | Pieces(n) | Auto, Off identical to the plain parser, and the cut and merge are public so the pieces can run on Nikaia’s own pool.

Changed by ADR-372 D4-D5: pieces are claimed while the work runs, not cut into n ranges first; cpu::count() is task::cores(); order: decides how accumulators are kept.

D12 — Scanning is a specified complexity: never one byte at a time.

A boundary or until terminator is found by a portable word-at-a-time (SWAR) scan - no target feature, works on wasm32; SIMD is a layer on top, never the baseline. Up to three fixed alternatives are one pass. The same primitive serves recover’s skip.

D13 — Fixed-width numeric parsing needs bounded repetition in the grammar.

p{n,m} (as in digit{1,2}) is the only route by which a fixed-width fast path may be emitted; digit+ says unbounded, and a compiler that assumed a width would be inventing a constraint.

D14 — Hash a view from its first bytes if you like; never truncate the comparison.

Hashing a view key from its first 8 bytes mixed with its length is sound; comparing only a prefix on a probe hit is not. Equality on views is content equality (ADR-283 D11). Which hash is used is chosen by provenance (ADR-010), never at the cost of this property.

D15 — Teardown of a large read-only buffer may be skipped at process exit.

A read-only mapping with no Cleanup and nothing observable attached may be left to the kernel at exit - the one relaxation of “cleanup always runs” (ADR-297), by proof of non-observability, not by a flag. It is an allowance; ADR-014 records that it is not taken.

D16 — A grammar is parsed, not carried as text.

grammar Name { … } becomes a structure: rules, alternatives, patterns, the commit point, repetition bounds, fold/par_fold with their expressions, and the keyed @frame. Which rule a call enters, whether it is a par_fold, and whether the grammar declares a frame are answered from the rules.

D17 — The lowering is syntactic, and never guesses a meaning.

Changed by ADR-013 D2: a step that calls a &mut self method returning nothing has its accumulator threaded by the emitter, found by a lookup in the program’s declarations rather than guessed from the step’s shape.

Every action, every init/step/merge and every body is emitted as written, name for name. Where Nikaia and Rust disagree about a name, the emitted program fails to compile rather than the printer inventing semantics. A step fn(acc, m) { acc.record(m) } with a &mut self method is not threaded from the shape of its tail; that adapter is a typing question.

D18 — @frame lowers key for key, and Nikaia does not re-implement its check.

@frame(boundary: "\n") becomes #[frame(boundary = "\n")], unchecked passes through, and the boundary keeps its escape text. The check that a boundary cannot occur inside a frame lives once, in the backend: two implementations would drift, and the harmful drift is Nikaia accepting what the backend rejects.

D19 — user_parallelism chooses the Parallelism, and nothing else.

A call to a par_fold rule lowers to the piece driver with Parallelism::Auto or, at no, the identical call with Parallelism::Off; the two programs differ in one token. A switch selects a build, not a dialect (ADR-037 D1). A rule that is not a par_fold gets its own parser, run once over the whole input.

D20 — A rule that is a par_fold gets its binding from the compiler; every other alternative carries an action.

A par_fold is the whole body of its rule, so its value is the rule’s and nothing is written after it. Everywhere else an action is required, and the pattern ends where its action block begins (D33).

D21 — A view takes the input’s lifetime, and the struct holding it comes along.

A view in a rule’s result type is emitted with the backend input’s lifetime; a struct with a view field carries the lifetime wherever it is named, named inside the grammar module and elided in a function signature. Every view is emitted as Borrowed; the tether-state lattice is not implemented here - a named limitation.

D22 — Comments are whitespace, and string literals are Nikaia’s own.

WS = (WSE | COMMENT)* is where comment skipping is said. The compiler brings its own lexical STRING, which keeps escapes as written, because the backend’s string does not know \n - and keeping them is what makes D18’s “the backend is handed the same "\n"” true.

D23 — A grammar reaches the parser backend as a macro invocation.

The lowering emits grammar! { … }, name for name with the .nika file. A grammar item is never dropped silently.

D24 — A grammar is entered by an ordinary call, and the rule’s name is the function’s.

let data = Json::value(input)

Json is the grammar, value an entry rule in it, reached as every qualified name is, by a path (ADR-140 D3; Json.value(x) is NK1147). A call gets ?, catch, being passed on and being chained for free. dsl X from e is refused at the parse with the call in the message; dsl takes a driver name and only that.

D25 — Every entry rule is an entry, the compiler distinguishes none, and pub belongs to the grammar.

Changed by ADR-299 D21: the author may mark one entry main.

As the backend does: one function per entry. The compiler picks no rule as the grammar’s main one - such a pick chooses wrong silently - so there is no “grammar has no entry to enter through” to refuse. The grammar’s author may say which one is main (main entry rule, ADR-299 D21); that is a decision written down, not a pick. Naming a rule that is not an entry has its own message.

Whether a rule is an entry and whether other packages may use it are two questions, and each has its word. entry is a decision about the rule: it was written to be entered on its own - a helper such as 1BRC’s NAME, whose frame_end means something only inside a frame, was not. So an entry is never inferred from a call, which would make one out of a typo. pub is a contract with other packages, and a grammar’s contract is all its entries: pub grammar offers every one of them, as a pub enum offers its variants, and a rule is never pub on its own - pub rule is refused with both words in the message. A grammar is entered only from its own file today, so pub grammar is decided and not built, and refused as such.

D26 — There is no parse alias.

A program that wants Json::parse(x) names its rule parse.

D27 — Where the bytes come from is said separately, by asset("…").

comptime ROUTES = Routes::table(asset("routes.txt")): comptime says when, asset where the bytes come from (ADR-310), the call what is done with them.

D28 — A fold’s init, step and merge are walked by the ordinary expression walk.

They are expressions inside a pattern; they get every rule the language has - NK1117, NK1132, NK1128, and whatever comes next.

D29 — Inside the frame the rule’s own pattern makes.

A binding beside the fold in the same sequence is in scope in its lambdas.

D30 — Outside expected.

The rule’s declared type is what an action builds; a fold’s init and step build the backend’s running value, and holding them to the declared type would refuse the arithmetic every fold is made of.

D31 — One walk, not two.

A jump in a fold’s step meets NK1132 through the lambda path every other lambda takes - the nearest loop is outside this lambda - and no second walk of the fold’s own exists beside it. ADR-276 D18’s backstop in the lowering stays. Measured: nothing in the corpus is newly refused.

D32 — Part II 10.8 lists every element a grammar may write, and it is complete.

An element not on the page is not in the language; a built-in the engine offers that the page does not name is unreachable from a .nika grammar.

D33 — A rule’s action stands after ->; a brace after a pattern is a bound.

rule pair -> Pair = key:string ":" => val:value -> { Pair { key, val } }. The first -> is the result type, the one before each block its action. A brace after a pattern is a bound (digit{1}, digit { 1 } alike), and a brace in the input is the literal "{". The form without the arrow is refused by name, with the form to write in the message.

Changed by ADR-grammar-1 D1.

D34 — tag and digit1 are not spelled.

"x" and digit+; either engine name is NK1187, carrying the spelling. The emitter keeps writing the engine’s own spelling.

D35 — An action may not pause, and a call that can is refused where it stands.

sync is asked of every call an action makes and of every call a fold’s init, step and merge make; a call that can pause is NK2209, naming the rule. A parse that can be cut and run on several cores (D10) is one whose steps do not wait on the world. Refused only where the ledger answered, as every sync rule is.

D36 — So a grammar’s entry is sync, and says so in the ledger.

[fn."Nums::number"]
sync = "asserted"
throws = ["ParseError"]

asserted because it is a rule of the language, not an inference; the entry is a leaf of the sync fixpoint that holds, so a function whose body is one call to it is sync again.

D37 — What this does not restrict.

An action may fail, may call anything that does not pause, and a grammar may be entered from a body that pauses; what is refused is a pause inside the parse.

D38 — A parse fails with ParseError, and every entry says so.

throws = ["ParseError"]. The type is nikaia-std’s, in the prelude, keyed in std.contracts with no module in front, as Overtaken is. The lowering wraps the backend’s rendered message, so a program prints exactly what it did before; what changes is the channel - with a second named member a caller’s set is a sum a program can match on (ADR-280).

D39 — It carries the message and nothing else.

Fields a program could read - line, column, expectation - are a second question nobody has asked.

D40 — A callee the throws graph does not hold still has a set.

A grammar entry is not an Item::Fn, so the fixpoint reads its set from the ledger; otherwise what a parse throws would reach no caller.

D41 — What a fold’s step calls directly is written #[inline(always)]. (The first case of ADR-370 D2.)

The step is the loop body over the input, so it runs once per item, and what it calls usually has that one call site. LLVM left 1BRC’s Summary::record out of line all the same, because hashbrown’s insert path makes it too big for its heuristic; no profile setting changed that (16 or 1 codegen unit, thin LTO: 319.1 instructions a row; fat LTO 317.0). With the hint: 300.1, the same output (#433). So a function or method a fold’s or a par_fold’s step calls is written #[inline], found by name, because the step’s receiver is the accumulator, whose type this emitter does not know (D17). Only here: every function inlined would bloat the code and the build.

#[inline] alone was not enough: with rustc 1.97 whether LLVM honoured it depended on how the codegen units were cut. At one unit record was inlined but hashbrown’s entry stayed a call; at sixteen the other way round, 1BRC 274 against 231 instructions a row (#695). So the hint is #[inline(always)]: the callee has one call site, the loop’s, and no heuristic of the backend’s decides it.

D42 — A map is std’s own type over hashbrown’s table; text keys are hashed and compared a word at a time.

Every Nikaia map lowers to one type of std’s own, built on hashbrown::HashTable, with the hash and the equality std chooses per key type. For a key that is text (a &str view or an owned String) both read the key a word at a time through its pointer: the hash from its first one or two words and its length, the equality word by word and then the tail, with no call of memcmp. Which key type it is, is known when compiling (a type-id test the optimiser removes), so one type serves every key and a map handed to a generic function stays the same Rust type. Keys are not copied into the slot: keys(), drain and a Map[ref String, V] hand back views that outlive the map, and counting instructions shows no gain from an inline copy. A map’s order is not promised (Part I), so the order a different hash gives is no change of meaning.

In 1BRC’s plain program the name’s memcmp cost 31.5 instructions a row and its hash 27.1 (#695’s attribution): Rust’s &str == always calls memcmp, which hashbrown’s map with a &str key cannot avoid.

Rejected: a second map type only for text keys (a Map[String, V] given to a generic function would be a different Rust type, and rustc would refuse it); keys stored inline (the views above cannot be handed back).

Decided by the supervising session on the owner’s direction (October 20, 2026: decide what is needed for the goal).

5. Consequences

6. What this does not decide

This site is open source. Improve this page.