Use -1 as the BNF EOF symbol - #1492

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: bca9d02e25

Approving. Reviewed at bca9d02. One new todo/ file, no code — so the review is whether the proposal's premises are true and its plan is self-consistent. I checked each factual claim against the tree rather than reading past them.

The one that most deserved checking is the range-map note, because it reads as forward-looking. It isn't — bigint-symbols.md:163 currently states outright that "-1n is not a BNF symbol and must never be accepted from an alphabet adapter or terminal range. It exists only inside the range-map representation." This proposal makes -1 exactly a BNF symbol, so those two documents will contradict each other. That is acknowledged rather than accidental: the task list has an explicit item to update bigint-symbols.md to depend on this task instead of reserving the maximal value, and the -2 suggestion gives internal cut points somewhere to go.

Worth noting the proposal also fixes a latent inconsistency that exists today: fullRange is [0, 16777215], which includes the EOF symbol value, so the current alphabet and the EOF sentinel already overlap. Restricting fullRange to ordinary symbols is a correctness improvement, not only a width-independence one.

Mechanical checks:

• All 7 relative links in the document resolve.
• No CHANGELOG entry, correctly — §8.3 exempts PRs touching only todo/.
• npx tsc clean, 2357 pass / 0 fail, unchanged from main as expected for a doc-only change.
• CI green.

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 69426c130b

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 0ae15d1386

Re-approving at 0ae15d1. The five new commits reconcile the sibling documents, which resolves the contradiction I flagged — and the fix went further than the one document I named.

The contradiction is gone, repo-wide

I swept all of fjs/bnf/todo/ rather than just re-reading bigint-symbols.md:

• No document asserts a maximal-value EOF any more. EOF = 2^256 - 1 and "Reserve the maximal value" are both gone.
• The `-1n` is not a BNF symbol and must never be accepted statement is gone.
• Every EOF definition across the five documents now reads -1 — bigint-symbols.md, eof-minus-one.md, terminal-range-representation.md, unicode-rules.md, and utf8-token-symbols.md all agree.

The four remaining "maximal value" mentions are all correct rather than residue: two describe the current behaviour being changed (the Problem statement and a task item to update callers that assume it), and two state the new rule — utf8-token-symbols.md in particular now validates against 0n <= encoded && encoded < 2^256 explicitly "not against a reserved maximal value."

The new section closes a real gap

6688a55 adds Logical EOF in parser input, which answers the question the original draft left open: if EOF is semantic and not in the physical alphabet, who produces it? The answer — adapters supply only physical symbols and never append -1, each backend synthesizes exactly one logical EOF after the last symbol, public positions stay in 0 <= idx <= input.length, and eofConsumed lives in internal state — is consistent with the task item that already said EOF is parser semantics rather than an alphabet value. Worth having written down before implementation rather than discovered during it.

Also a small correctness touch: the bigint reservation is now described in the past tense, since that document no longer proposes it.

Mechanical

• Links 144/144 against main, none added, 0 label/target mismatches.
• npx tsc clean, 2357 pass / 0 fail — unchanged, as expected for a documentation-only change.
• No CHANGELOG entry, correct under §8.3.
• CI green.

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 7cd6d51192

Re-approving at 73da4ac. Three commits that take the logical-EOF section from "who synthesizes it" to "what it does to control flow" — and the addition is the part of this design most likely to bite during implementation, so it is good to see it settled on paper.

Making EOF count as progress is the right call

7cd6d51 widens the cursor to (idx, eofConsumed) and states that matching EOF is progress even though the public idx does not move. That distinction is load-bearing in exactly the places the document lists:

• repetition's no-progress termination check would otherwise treat EOF as a nullable match;
• alternative selection would be free to discard an EOF-consuming branch for a later nullable one on the grounds that idx is unchanged;
• backtracking that restored only idx would leave EOF spuriously consumed for a sibling branch.

Each of those is a real miscompile waiting to happen once EOF stops being an ordinary in-band symbol, and none is obvious from the EOF = -1 decision alone.

b547dda's lexicographic (idx, false) < (idx, true) for failure high-water tracking is consistent with that: a failure that got as far as consuming EOF genuinely is further along than one that did not.

The recognizer side agrees

73da4ac gives the streaming counterpart: chunk boundaries are not end-of-input, EOF is synthesized only at explicit finalization, and finish(state) = λ(δTerminal(EOF, state)) pins the semantics without over-specifying the representation. recognizer-backend.md now also declares itself blocked by the EOF task, which it genuinely is.

Consistency and mechanics

• Ten EOF = -1 definitions across the bnf/todo set, all in agreement.
• The three "append EOF" hits are the prohibition stated in both documents, not a contradiction — callers never append, backends synthesize.
• Links 144/144 against main, none added, 0 label/target mismatches, including the new "Blocked by" reference.
• npx tsc clean, 2357 pass / 0 fail, unchanged as expected for documentation.
• CI green.

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 73da4ac9ee

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 17bdecd0de

Re-approving at 17bdecd. Clarify recognizer EOF acceptance fixes something real, not a wording nit, so it is worth stating what it fixes.

The previous finalization would have silently broken existing grammars

The formulation this replaces was:

finish(state) = λ(δTerminal(EOF, state))

That forces every grammar through the EOF transition. An existing whole-input grammar that never mentions eof, and that is already accepting after its last physical symbol, would be rejected if δTerminal moved that accepting state to a sink — which is the ordinary thing for a transition on a symbol the grammar does not expect. No grammar author would have written anything wrong; the recognizer would just have stopped accepting inputs it accepts today.

The new form is backward-compatible:

beforeEOF = λ(state)
afterEOF  = λ(δTerminal(EOF, state))
finish(state) = beforeEOF || afterEOF

and the document states the consequence directly — the EOF transition may not erase acceptance already established at the physical end, while a grammar whose final rule requires eof can still return false before and true after. Allowing a backend to compile an optional final EOF path instead of literally evaluating both states, as long as the accepted language matches, is the right level to pin: contract over representation.

The two documents still agree

I checked this specifically, because the commit also drops the sentence calling finalization "the streaming equivalent of the parser cursor transition." Dropping it is correct rather than a loss: in eof-minus-one.md the parser only takes the (len, false) → (len, true) step when the grammar actually matches eof, whereas the old recognizer text took it unconditionally. Both documents now say the same thing — one EOF opportunity is made available, and the grammar decides whether to use it. "Synthesize exactly one logical EOF" means availability, not forced consumption, and nothing in either file now claims otherwise.

The added task item covers both acceptance paths explicitly, which is the right thing to prove.

Mechanics

• Only markdown changed (0 non-.md files).
• Links 144/144 against main, none added, 0 label/target mismatches.
• npx tsc clean, 2357 pass / 0 fail — unchanged, as expected.
• CI: everything green except macos-intel, still running when I checked; the other platforms and CodeQL all passed, and nothing here can affect a build.

💡 Codex Review

Here are some automated review suggestions for this pull request.

Reviewed commit: 9831f49e6d

Re-approving at 7c5eb6d. Nine commits, and they materially simplify the design rather than polishing it — net −241 lines across the three documents.

The simplification is a real improvement

What I approved previously required a +1 offset on every endpoint, a temporary 25-bit packed form, and therefore a wire-format change. That is all gone. Semantic EOF is still -1, but the stored representation is untouched: EOF keeps stored code 2^24 - 1, every ordinary symbol keeps its existing code, and the packed range stays two 24-bit endpoints. There are exactly 2^24 terminal values before and after.

I verified the proposed codec exhaustively rather than eyeballing the three sample rows:

encodeTerminal = value => (value + terminalSize) & terminalMask
decodeTerminal = value => ((value + 1) & terminalMask) - 1

Over the whole semantic domain -1 .. 2^24 - 2: 16777216 values → 16777216 distinct codes, zero round-trip failures. Bijective and exact.

It is not order-preserving — encode(-1) is 2^24 - 1, above every ordinary code — and the document says so itself in the right place: "The stored codes are an implementation representation, not semantic terminal ordering. Range operations that care about semantic ordering must compare decoded terminal values." That was my first concern on reading the new mapping, and it is already answered.

The breaking consequence is stated plainly too: fullRange moves from [0, 2^24 - 1] to [0, 2^24 - 2], old serialized ranges whose endpoint was EOF now decode to -1, and the resolution is to regenerate in-repo data rather than carry a compatibility layer. For content-addressed BNF data that is the honest call.

Cross-document consistency

Two things looked like leftovers and are not:

• terminal-range-representation.md still shows encodeTerminal(value) = value + 1, but it now sits under Alternatives to investigate for the bigint domain, where 2^256 + 1 semantic values genuinely cannot fit a 256-bit code. Correctly scoped to the future decision rather than the current one.
• eof-minus-one.md still contains EOF = 2^24 - 1 twice — both inside before:/current-state blocks describing today's representation.

That document also now states outright that moving semantic EOF does not require changing the current packing, which is what makes the two tasks independent.

Mechanics

• Markdown only (0 non-.md files).
• Links 144/144 against main, none added, 0 label/target mismatches.
• npx tsc clean.
• CI green.