functionalscript · sergey-shandar · Aug 13, 2026 · Aug 13, 2026 · Aug 13, 2026 · Aug 13, 2026
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -20,6 +20,11 @@ history.
 
 ## Unreleased
 
+- **BREAKING CHANGES:** BNF EOF is the semantic symbol `-1`, not `2^24 - 1`:
+  `fullRange` is `0 .. 2^24 - 2`, and the parser backends synthesize one
+  logical EOF after the physical input. Serialized ranges that ended at the
+  old EOF must be regenerated
+  [#1516](https://github.com/functionalscript/functionalscript/pull/1516)
 - `fjs/protocol/json_rpc` `dispatch` looks up handlers by own property.
   An `Object.prototype` method name arriving as `method` no longer throws
   or emits a malformed response; it answers `-32601` like any other

diff --git a/fjs/bnf/README.md b/fjs/bnf/README.md
@@ -9,6 +9,54 @@ See [Backus-Naur form](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form).
   - LL(1) dispatch/matcher [./ll1/](./ll1/),
   - recursive descent matcher [./descent/](./descent/).
 
+## Terminals and EOF
+
+A terminal is a semantic symbol. The domain is
+
+```text
+EOF              = -1
+ordinary symbols = 0 .. 2^24 - 2
+```
+
+`-1` is outside the non-negative physical-symbol domain, so EOF does not depend
+on how wide a physical symbol is, and no alphabet — Unicode code points, bytes,
+[token symbols](./token_symbol/) — has to give up one of its own values for it.
+`eof` is the singleton range `[-1, -1]`; `fullRange` is `[0, 2^24 - 2]` and holds
+ordinary symbols only, so `not()` / `notSet()` never produce EOF.
+
+### Stored codes are not semantic values
+
+A `TerminalRange` still packs two **24-bit stored endpoint codes** into one JS
+number, and the codes are unchanged: EOF is stored as `2^24 - 1`, every ordinary
+symbol is stored as itself. `rangeEncode` / `rangeDecode` convert between the two
+with a branchless wrap (`(value + 2^24) & mask` and its inverse), so the domain
+still holds exactly `2^24` terminals — one per code — and a packed literal such
+as `0x000030_000039` still reads as its endpoints.
+
+The consequence is that stored order is not semantic order: `2^24 - 1` is the
+largest code but the smallest terminal. Anything that compares terminals —
+containment, complements, dispatch ranges — compares **decoded** values.
+
+Moving EOF to `-1` was a breaking change to serialized BNF ranges rather than a
+representation change: a range whose endpoint used to be the ordinary symbol
+`2^24 - 1` now decodes as EOF. There is no compatibility layer for grammar data
+written against the old semantics; regenerate it instead.
+
+### Logical EOF in parser input
+
+Callers and alphabet adapters supply physical ordinary symbols only and never
+append `-1`. Each parser backend synthesizes exactly one logical EOF after the
+physical input, so a grammar can require the end of input with the `eof`
+terminal, and a grammar that does not mention `eof` is unaffected.
+
+Public positions and remainders stay physical (`0 <= idx <= input.length`).
+Internally a backend tracks the complete cursor `(idx, eofConsumed)`, because
+consuming EOF is progress even though `idx` does not move — sequencing,
+alternatives, repetition, backtracking, and failure ordering all use the complete
+cursor, and `(idx, true)` is further than `(idx, false)`. The synthesized EOF has
+no physical source element, so it contributes no leaf to the AST, and diagnostics
+about it point at `input.length`.
+
 ## Functional Representation
 
 Define grammar using this representation.

diff --git a/fjs/bnf/data/README.md b/fjs/bnf/data/README.md
@@ -5,6 +5,11 @@ The pure, parser-agnostic BNF intermediate representation (IR).
 A `RuleSet` is a serializable map of `Rule = Variant | Sequence | TerminalRange`.
 The function `toData()` converts a functional grammar into this representation.
 
+A `TerminalRange` packs stored endpoint codes rather than semantic terminal
+values — see [Terminals and EOF](../README.md#terminals-and-eof). The codes are
+unchanged since EOF moved to `-1`, but their meaning at the top of the space is
+not: serialized ranges whose endpoint was the old EOF must be regenerated.
+
 `emptyTagMap()` computes, for every rule in a `RuleSet`, whether it can match
 empty input — shared by both automaton builders below so nullability is
 derived once, consistently.

diff --git a/fjs/bnf/descent/README.md b/fjs/bnf/descent/README.md
@@ -8,6 +8,25 @@ per-code-point metadata, producing a metadata-aware AST. Nullability (whether
 each rule can match empty input) is computed once by `emptyTagMap()` in
 [`../data`](../data).
 
+## Logical EOF and the complete cursor
+
+The caller passes physical code points only; the matcher synthesizes the one
+logical EOF after them ([`../README.md`](../README.md#logical-eof-in-parser-input)).
+Internally a position is therefore a cursor over `0 .. cp.length + 1`, where
+`cp.length + 1` means the synthesized EOF has been consumed — the
+`(idx, eofConsumed)` pair of the shared design, written as one number because
+`eofConsumed` can only be true at the physical end. One number is enough to make
+every ordering the matcher needs a plain `<`: progress inside a variant,
+backtracking to a frame's start, and the furthest-failure high-water mark.
+
+The public `idx` clamps that cursor back to `input.length`, so consuming EOF
+never moves a reported position, and the EOF leaf never reaches the AST.
+
+Treating EOF consumption as progress is load-bearing, not bookkeeping: a variant
+counts a zero-consumption success as its empty result and keeps trying later
+branches, so if EOF matched "without moving", `repeat0Plus` over a rule that can
+match EOF would take that branch forever.
+
 ## Failure reporting
 
 A failed match's own index is not where matching stopped: a failing sequence

diff --git a/fjs/bnf/descent/module.f.mjs b/fjs/bnf/descent/module.f.mjs
@@ -7,6 +7,10 @@
  * AST ({@link AstRuleMeta}). Nullability (which rule can match empty input) is
  * computed once by {@link emptyTagMap} in `fjs/bnf/data`.
  *
+ * The caller passes physical symbols only; the matcher synthesizes the one
+ * logical EOF ({@link eofSymbol}) after them, so a grammar can require the end
+ * of input with the `eof` terminal.
+ *
  * A failed result also carries a {@link DescentFailure}: the furthest position a
  * terminal was rejected at, which — unlike the result's own index — never
  * rewinds and is what diagnostics should be built from.
@@ -18,25 +22,89 @@
  * @import { TerminalRange } from '../types.ts'
  * @import { Rule as DataRule, Sequence } from '../data/types.ts'
  * @import { Rule as FRule } from '../types.ts'
- * @import { AstTag, AstSequenceMeta, DescentFailure, DescentMatch, DescentMatchResult, DescentMatchRule } from './types.ts'
+ * @import { AstRuleMeta, AstTag, AstSequenceMeta, CodePointMeta, DescentFailure, DescentMatch, DescentMatchResult, DescentMatchRule } from './types.ts'
  */
 
-import { rangeDecode } from '../module.f.mjs'
+import { eofSymbol, rangeDecode } from '../module.f.mjs'
 import { contains as rangeContains } from '../../types/range/module.f.mjs'
 import { definedEntries } from '../../types/object/module.f.mjs'
 import { emptyTagMap, toData } from '../data/module.f.mjs'
 
+/**
+ * A match position that includes EOF consumption: `0 .. cp.length` are the
+ * physical positions, and `cp.length + 1` is where the one synthesized EOF has
+ * been consumed.
+ *
+ * This is the complete cursor the design calls `(idx, eofConsumed)`, written as
+ * one number: `eofConsumed` can only be true at the physical end, so the pair
+ * and the extended position hold the same information, and comparing cursors
+ * compares progress — consuming EOF *is* progress even though the public index
+ * does not move.
+ *
+ * @typedef {number} _Cursor
+ */
+
+/**
+ * The furthest-failure record while matching, positioned by the complete
+ * cursor. {@link DescentFailure} is its public, physically-positioned form.
+ *
+ * @typedef {{
+ *     readonly pos: _Cursor
+ *     readonly expected: readonly TerminalRange[]
+ * }} _Failure
+ */
+
+/**
+ * The machine's own result: a {@link DescentMatchResult} positioned by the
+ * complete cursor, and with no failure record — that one is tracked per match
+ * rather than per frame.
+ *
+ * @template T
+ * @typedef {{
+ *     readonly ast: AstRuleMeta<T>
+ *     readonly success: boolean
+ *     readonly pos: _Cursor
+ * }} _Result
+ */
+
+/**
+ * The public, physical index of a cursor. Consuming EOF moves the cursor past
+ * the physical end, and both cursors report `input.length`.
+ *
+ * @type {(length: number) => (pos: _Cursor) => number}
+ */
+const physicalIdx = length => pos => Math.min(pos, length)
+
+/**
+ * The semantic symbol a cursor points at: a code point inside the physical
+ * input, and the synthesized {@link eofSymbol} at its end. Only meaningful
+ * where the cursor still has a symbol, `pos <= cp.length`.
+ *
+ * @type {<T>(cp: readonly CodePointMeta<T>[], pos: _Cursor) => number}
+ */
+const symbolAt = (cp, pos) => pos < cp.length ? cp[pos][0] : eofSymbol
+
+/**
+ * What consuming the symbol at a cursor contributes to the AST: the code point
+ * with its metadata, and nothing for the synthesized EOF — it has no physical
+ * source element.
+ *
+ * @type {<T>(cp: readonly CodePointMeta<T>[], pos: _Cursor) => AstSequenceMeta<T>}
+ */
+const leafAt = (cp, pos) => pos < cp.length ? [cp[pos]] : []
+
 /**
  * Folds one rejected terminal into the furthest-failure record: further along
- * replaces, the same position accumulates (ignoring repeats), earlier is
- * discarded.
+ * replaces, the same cursor accumulates (ignoring repeats), earlier is
+ * discarded. The comparison is on the complete cursor, so a failure after EOF
+ * was consumed is further than one at the same physical index before it.
  *
- * @type {(failure: DescentFailure, idx: number, terminal: TerminalRange) => DescentFailure}
+ * @type {(failure: _Failure, pos: _Cursor, terminal: TerminalRange) => _Failure}
  */
-const recordFailure = (failure, idx, terminal) => {
-    if (idx > failure.idx) { return { idx, expected: [terminal] } }
-    if (idx < failure.idx || failure.expected.includes(terminal)) { return failure }
-    return { idx, expected: [...failure.expected, terminal] }
+const recordFailure = (failure, pos, terminal) => {
+    if (pos > failure.pos) { return { pos, expected: [terminal] } }
+    if (pos < failure.pos || failure.expected.includes(terminal)) { return failure }
+    return { pos, expected: [...failure.expected, terminal] }
 }
 
 /**
@@ -51,6 +119,11 @@ export const descentParser = fr => {
     const data = toData(fr)
     const emptyTags = emptyTagMap(data[0])
 
+    /** @type {(tag: AstTag, sequence: AstSequenceMeta<T>, pos: _Cursor) => _Result<T>} */
+    const mrSuccess = (tag, sequence, pos) => ({ ast: {tag, sequence}, success: true, pos })
+    /** @type {(tag: AstTag, sequence: AstSequenceMeta<T>, pos: _Cursor) => _Result<T>} */
+    const mrFail = (tag, sequence, pos) => ({ ast: {tag, sequence}, success: false, pos })
+
     // A suspended sequence match: items[itemIndex] is being matched by the current
     // task; `seq` holds the ASTs of the items already matched.
     /**
@@ -59,7 +132,7 @@ export const descentParser = fr => {
      *     readonly tag: AstTag
      *     readonly items: Sequence
      *     readonly itemIndex: number
-     *     readonly startIdx: number
+     *     readonly startPos: _Cursor
      *     readonly seq: AstSequenceMeta<T>
      * }} _SeqFrame
      */
@@ -72,8 +145,8 @@ export const descentParser = fr => {
      *     readonly kind: 'variant'
      *     readonly entries: readonly (readonly [string, string])[]
      *     readonly entryIndex: number
-     *     readonly idx: number
-     *     readonly emptyResult: DescentMatchResult<T>
+     *     readonly pos: _Cursor
+     *     readonly emptyResult: _Result<T>
      * }} _VariantFrame
      */
 
@@ -93,7 +166,7 @@ export const descentParser = fr => {
      * @typedef {{
      *     readonly name: string
      *     readonly tag: AstTag
-     *     readonly idx: number
+     *     readonly pos: _Cursor
      * }} _Task
      */
 
@@ -104,97 +177,101 @@ export const descentParser = fr => {
     // grammar recursion depth — right-recursive rules (e.g. repeat0Plus chains) no longer
     // overflow on long input (see the longInput proof group).
     /** @type {DescentMatchRule<T>} */
-    const f = (name, tag, cp, idx) => {
-        /** @type {(tag: AstTag, sequence: AstSequenceMeta<T>, idx: number) => DescentMatchResult<T>} */
-        const mrSuccess = (tag, sequence, idx) => ({ ast: {tag, sequence}, success: true, idx })
-        /** @type {(tag: AstTag, sequence: AstSequenceMeta<T>, idx: number) => DescentMatchResult<T>} */
-        const mrFail = (tag, sequence, idx) => ({ ast: {tag, sequence}, success: false, idx })
+    const f = (name, tag, cp, startPos) => {
+        const physical = physicalIdx(cp.length)
 
         /** @type {_Stack} */
         let stack = null
         /** @type {_Task | null} */
-        let task = { name, tag, idx }
-        /** @type {DescentMatchResult<T>} */
-        let result = mrFail(undefined, [], idx)
+        let task = { name, tag, pos: startPos }
+        /** @type {_Result<T>} */
+        let result = mrFail(undefined, [], startPos)
         // High-water mark across the whole match, so it survives the rewinds a
         // failing sequence item does to `result`.
-        /** @type {DescentFailure} */
-        let furthest = { idx: 0, expected: [] }
+        /** @type {_Failure} */
+        let furthest = { pos: 0, expected: [] }
 
         while (true) {
             if (task !== null) {
                 // The explicit annotation cuts a control-flow inference cycle (TS7022):
                 // `name`'s narrowed type feeds `rule`, whose type would otherwise feed the
                 // later `task` assignments that `name`'s narrowing depends on.
-                const { name, tag, idx } = /** @type {_Task} */ (task)
+                const { name, tag, pos } = /** @type {_Task} */ (task)
                 task = null
                 /** @type {DataRule} */
                 const rule = data[0][name]
                 if (typeof rule === 'number') {
                     // No nullable case: `emptyTagOf` in `bnf/data` returns `undefined`
                     // for every terminal, so `emptyTags[name]` here is always
                     // `undefined` and a terminal either consumes one symbol or fails.
-                    if (idx < cp.length && rangeContains(...rangeDecode(rule))(cp[idx][0])) {
-                        result = mrSuccess(tag, [cp[idx]], idx + 1)
+                    // Past the synthesized EOF there is no symbol left to consume.
+                    if (pos <= cp.length && rangeContains(...rangeDecode(rule))(symbolAt(cp, pos))) {
+                        result = mrSuccess(tag, leafAt(cp, pos), pos + 1)
                     } else {
                         // The only place a terminal is rejected, so the only place
                         // the furthest failure can advance.
-                        furthest = recordFailure(furthest, idx, rule)
-                        result = mrFail(undefined, [], idx)
+                        furthest = recordFailure(furthest, pos, rule)
+                        result = mrFail(undefined, [], pos)
                     }
                 } else if (rule instanceof Array) {
                     if (rule.length === 0) {
-                        result = mrSuccess(tag, [], idx)
+                        result = mrSuccess(tag, [], pos)
                     } else {
-                        stack = { top: { kind: 'seq', tag, items: rule, itemIndex: 0, startIdx: idx, seq: [] }, rest: stack }
-                        task = { name: rule[0], tag: undefined, idx }
+                        stack = { top: { kind: 'seq', tag, items: rule, itemIndex: 0, startPos: pos, seq: [] }, rest: stack }
+                        task = { name: rule[0], tag: undefined, pos }
                     }
                 } else {
                     const entries = definedEntries(rule)
                     const emptyTag = emptyTags[name]
-                    const emptyResult = mrFail(emptyTag, [], idx)
+                    const emptyResult = mrFail(emptyTag, [], pos)
                     if (entries.length === 0) {
                         result = emptyResult
                     } else {
-                        stack = { top: { kind: 'variant', entries, entryIndex: 0, idx, emptyResult }, rest: stack }
+                        stack = { top: { kind: 'variant', entries, entryIndex: 0, pos, emptyResult }, rest: stack }
                         const [entryTag, entryName] = entries[0]
-                        task = { name: entryName, tag: entryTag, idx }
+                        task = { name: entryName, tag: entryTag, pos }
                     }
                 }
                 continue
             }
 
             if (stack === null) {
+                const { ast, success, pos } = result
+                /** @type {DescentMatchResult<T>} */
+                const mr = { ast, success, idx: physical(pos) }
                 // A success has nothing to diagnose; only a failure carries it.
-                return result.success ? result : { ...result, failure: furthest }
+                return success
+                    ? mr
+                    : { ...mr, failure: { idx: physical(furthest.pos), expected: furthest.expected } }
             }
             const frame = stack.top
             stack = stack.rest
 
             if (frame.kind === 'seq') {
-                const { ast: astRule, success, idx: nidx } = result
+                const { ast: astRule, success, pos } = result
                 if (success === false) {
-                    result = mrFail(frame.tag, [], frame.startIdx)
+                    result = mrFail(frame.tag, [], frame.startPos)
                 } else {
                     const seq = [...frame.seq, astRule]
                     const itemIndex = frame.itemIndex + 1
                     if (itemIndex < frame.items.length) {
                         stack = { top: { ...frame, itemIndex, seq }, rest: stack }
-                        task = { name: frame.items[itemIndex], tag: undefined, idx: nidx }
+                        task = { name: frame.items[itemIndex], tag: undefined, pos }
                     } else {
-                        result = mrSuccess(frame.tag, seq, nidx)
+                        result = mrSuccess(frame.tag, seq, pos)
                     }
                 }
             } else {
                 // success that consumed input wins immediately: the frame stays popped and
                 // `result` propagates to the frame below, matching the recursive `return m`.
-                if (!(result.success && frame.idx !== result.idx)) {
+                // Consuming EOF counts as consumption, because the cursor moved.
+                if (!(result.success && frame.pos !== result.pos)) {
                     const emptyResult = result.success ? result : frame.emptyResult
                     const entryIndex = frame.entryIndex + 1
                     if (entryIndex < frame.entries.length) {
                         stack = { top: { ...frame, entryIndex, emptyResult }, rest: stack }
                         const [entryTag, entryName] = frame.entries[entryIndex]
-                        task = { name: entryName, tag: entryTag, idx: frame.idx }
+                        task = { name: entryName, tag: entryTag, pos: frame.pos }
                     } else {
                         result = emptyResult
                     }