First-char gating — making the compiler dispatch your choices

The single biggest hot-path lever in a Parséman grammar is whether each choicefirst-char-gates: when every arm starts with a disjoint character, the choice becomes an O(1) character dispatch, so a non-matching position is rejected with one comparison. When it doesn't, the choice falls back to ordered first-match: every position speculatively ENTERS each arm in turn (context save/restore, a child array, the recognizer, then rollback) until one matches or all fail.

Gating is decided by the shared first-set analysis, so both run paths benefit: the interpreter dispatches through a prebuilt ASCII lookup table (src/combinators/choice.ts), and the JS-codegen lowering used by compile() and the macro build emits a switch/jump table inline. The diagnostics below report the gating decision itself, which is a property of the grammar, not of how you run it.

Here's the trap: PEG grammars are correct regardless of whether a choice gates. An ungated hot choice passes every test and produces the right tree — it just does a lot more work per input character. The only symptom is a CPU profile, and the stakes are large: on real Parséman grammars, fixing the single arm that breaks a hot choice's dispatch is worth 25–48% of total parse time. None of that requires profiling to find — the compiler can tell statically which choices don't gate, and why.

So Parséman will tell you — when you ask.

Ask for it: `diagnoseGrammar()`

// [verify]
import { choice, literal, regex, diagnoseGrammar, formatGrammarDiagnosis } from 'parseman'

const grammar = { value: choice(literal('a'), regex(/[\s\S]*/)) }
const d = diagnoseGrammar(grammar)

d.ok
// → false
d.findings[0].code
// → 'ungated-choice'
d.findings[0].id
// → 'value'
formatGrammarDiagnosis(d)[0]
// → 'parseman: grammar NOT OK — 1 blocking finding(s) over 1 examined choice(s).'

diagnoseGrammar takes any grammar shape — a bare combinator, an array of [name, combinator] entries, a rules() map, or a compose() result — and returns a plain, JSON-serializable GrammarDiagnosis. formatGrammarDiagnosis(d) renders it for a human, with the offending arm, the cause, and the fix inline:

text

parseman: grammar NOT OK — 1 blocking finding(s) over 1 examined choice(s).
✗ [ungated-choice] value: choice is UNGATED [firstMatch] — no first-char dispatch;
    every position speculatively enters doomed arms
    arm[7] first-set ANY (cross-artifact-ref): via ref g.anyValue → broad recognizer (regex)
    fix: parseman resolves a g.Foo ref first-set at fuse time; if still ANY the
         target rule is itself ungated — analyze it and give it a concrete non-nullable lead.
    arm[0] ∩ arm[1] overlap on '+','-'-'.','0'-'9'
    fix: arms share a first char — left-factor. …
    intentional? add to the gating snapshot: { accept: ['value'] }

It is precise, not spammy: it fires only on choices that genuinely can't dispatch — never on a recoverable choice (one that looks ungated at construction because its arms are ref()s, but whose deep/fuse-resolved first-sets are actually disjoint, so the compiled code still guards each arm).

Why this is not a compile-time warning

It used to be. compile() ran the analysis by default and printed it through console.warn, so importing one example grammar emitted 51 lines of advice before a single byte was parsed. The advice was correct and nobody read it: it arrived unasked, in the middle of an unrelated build log, on a build that had not gone wrong.

Since 0.45.0 the two acts are separate. compile(), compileRuleMap(), compose() and the macro transform produce an artifact and say nothing — there is no gating compile option, no PARSEMAN_GATING env var, and no CompiledParser.gating field. Diagnosing is diagnoseGrammar(), and you run it where a diagnosis belongs: a test, a lint script, a CI job.

(This does not apply to the [parseman] degraded channel, which stays default-on — see Degradation diagnostics. A degradation is not advice: it is parseman reporting that it could not do what you asked for.)

What poisons a first-set

A choice gates only when the compiler can prove each arm's set of possible first characters is disjoint from the others and finite. These are the things that widen an arm's first-set to any (or make two arms overlap) and break that proof:

Poison	Why	Fix
broad `regex` — `regex(/[\s\S]*/)`, an over-broad value token	its first-set is every character	narrow it; for keywords use `word()`/`keywords()`
keyword `regex` — `regex(/color/)` used as a keyword	works, but the analyzer can't always give it an exact first-set, and it invites the boundary bug	`word('color', boundary)` / `keywords([...])` — exact first-set, same compiled scan
leading `not(...)` — `sequence(not(x), y)` as an arm	`not()`'s first-set is `any`	let the arm lead with its consuming terminal; keep `not()` as a TRAILING boundary
`not(not(...))` — hand-rolled first-char gating	first-set `any` and it miscompiles among shared-first-char siblings	delete it; first-char gating is automatic
leading `optional`/`many`	a skippable prefix lets a later, possibly-broad term start the arm	split the empty case into its own arm, or gate on the prefix
`gate()` / `guard()` as a leading arm term	a state predicate's first-set is `any`	use the gated-arm field to SELECT a branch (it keeps dispatch); put `gate()` after a terminal
cross-artifact `g.Foo` ref → `any`	a composed rule's first-set couldn't resolve across the artifact boundary	the ref is resolved at fuse time; if it is still `any`, the target rule is itself ungated — fix it there. In a shared shape the ref is a HOLE, and the finding is reported against the artifact that binds it
shared prefix — two arms starting with the same terminal	first-sets overlap, so no unique dispatch key	left-factor: parseman auto-detects `sharedPrefix` for bare sequences — make the arms bare sequences with the common leading terminal

Common mistakes (and what the diagnosis tells you)

These are the exact mistakes real authors — humans and LLMs — make. The point of the diagnostic is that you don't have to remember them; one call names them.

Using regex(/keyword/) for a keyword.

choice(sequence(regex(/@supports/), prelude), otherAtRule)   // ⚠️
choice(sequence(word('@supports', '-\\w'), prelude), otherAtRule)  // ✅ exact first-set

→ anti-pattern [keyword-regex]: use word('…', boundary) / keywords([…]) for an exact resolvable first-set.

Hand-rolling first-char gating with not(not(...)).
ts
```
choice(sequence(not(not(literal('@'))), atRule), ruleset)   // ⚠️ MISCOMPILES
```
→ anti-pattern [double-not]: not(not(...)) hand-rolls automatic first-char gating and MISCOMPILES among shared-first-char sibling arms. Remove it. First-char dispatch is automatic — just let the arm lead with literal('@').
A scanTo / broad fallback arm in an otherwise-fine choice.
ts
```
const stmt = choice(atRule, ruleset, scanTo(literal(';')))   // ⚠️ ungated (a recovery fallback)
```
A recovery fallback legitimately can't gate. That's fine — accept it in the gating snapshot (below) so it's silent and doesn't fail the CI gate.
Two arms sharing a leading token (Dimension and Num both leading with the number regex). → overlap on + - . 0-9 … left-factor. Parse the shared prefix once and branch on what follows.

Accepting an intentional ungated choice (the snapshot allowlist)

Not every choice is hot. A top-level statement dispatcher with a broad error-recovery arm should fall through arm by arm. Rather than a per-node marker, there is one suppression mechanism: list the choice's stable id in the gating snapshot's accept allowlist. The id is the finding's id — for statement here it is statement (or statement#0, statement#1, … when a rule holds several choices), and diagnosis.acceptSnapshot hands you the whole list ready to paste.

const ACCEPTED = ['statement', 'value#1']   // ideally kept with a reason per entry
const d = diagnoseGrammar(grammar, { accept: ACCEPTED })

An accepted choice is excluded from ok; any ungated choice NOT in accept still blocks. Stale entries come back as advisory stale-accept findings (and in d.gating.acceptedUnused), so a stale allowlist is easy to prune. Prefer fixing the gating (a concrete leading terminal, word()/keywords(), reordering a leading not) over accepting it; the allowlist is for the genuinely-unavoidable cases (recovery fallbacks), not the default.

Shared shapes: the verdict belongs to the fuse

A shared shape is a rules() map that references a rule it does not define — the shape written once, each dialect binding the hole:

// shape.ts — `Value` is a HOLE; this module never defines it
export const shape = rules(g => ({
  Term: choice(sequence(g.Value, literal('/')), sequence(literal('@'), regex(/[a-z]+/))),
}))

Does Term gate? The shape cannot know. g.Value has no body here, so its first-set reads any — and whether the arms collide depends entirely on what a consumer binds. The shape module is never executed as a parser, and its author has nothing to fix.

So the shape has no finding to give. Such a choice is deferred: excluded from ok, counted in d.summary.deferred, and visible programmatically as d.gating.deferred. Ask the question again of the fused grammar, where the hole is bound:

diagnoseGrammar(compose([shape, rules(_g => ({ Value: regex(/[0-9]+/) }))]))    // ✅ '0'-'9' vs '@' — gates
diagnoseGrammar(compose([shape, rules(_g => ({ Value: regex(/@[0-9]+/) }))]))   // ✗ Term is UNGATED
//                                                                      arm[0] ∩ arm[1] overlap on '@'

The finding lands on the artifact that can act on it, and names the real cause — a concrete overlap on '@', not "unresolved ref g.Value". Fix it where you'd expect: bind a narrower Value, or left-factor the shape's arms.

Asking a composed grammar directly

diagnoseGrammar handles a compose() result for you. The lower-level analyzeGrammarGating() does the same and returns the raw GatingReport:

import { analyzeGrammarGating } from 'parseman'

const report = analyzeGrammarGating(myComposedGrammar)
if (report.unanalysable.length > 0) throw new Error('gating report is PARTIAL')

Do not reach for analyzeGatingRules(Object.entries(composed)) instead. A compose() result is a map of fused rule functions — fusion lowers each rule to executable code, so there is no combinator graph left in that map to walk. analyzeGrammarGating recovers the graph from the composition's carried IR first.

Two things this buys you over analyzing a contributing rules() map on its own: the cross-artifact holes are bound, so choices that were deferred resolve to a real verdict; and you see the union of every contributing grammar's rules, which no single rules() map contains.

Always check report.unanalysable before reading report.ungated as a pass. It is non-empty when part of the grammar could not be examined — for instance a contributing piece that is an opaque precompiled artifact — and an empty ungated then means "nothing was looked at", not "nothing is wrong".

CI: one call, one exit code

d.ok is the whole contract — it is false when there is any blocking finding, and an analysis that could not run counts as blocking. Keep an accept allowlist of the choice ids you've reviewed, so a refactor that ungates a NEW hot choice fails the build:

// scripts/check-gating.ts
import { diagnoseGrammar, formatGrammarDiagnosis } from 'parseman'
import { grammar } from '../src/grammar.ts'

const ACCEPTED = ['statement', 'value#1']    // reviewed, intentional (keep a reason each)
const d = diagnoseGrammar(grammar, { accept: ACCEPTED })
if (!d.ok) {
  console.error(formatGrammarDiagnosis(d).join('\n'))
  process.exit(1)
}

It fails closed: ok is false when part of the grammar could not be examined (an opaque precompiled contributing artifact, a value that is not a combinator, an analysis that threw), so an empty ungated can never be mistaken for "nothing is wrong". Write JSON.stringify(d.findings) to a committed file if you want a diffable snapshot — the findings are sorted, so two runs over the same grammar are byte-identical.

Why this is implicit in Parséman (the Chevrotain contrast)

A tokenizing parser like Chevrotain forces you to declare dispatch: the lexer assigns each input a token type, and the parser branches on that type. You cannot forget to dispatch — the cliff is impossible to hit — but you also can't do scannerless things (overlapping tokens, per-position re-lexing, context-dependent tokenization).

Parséman is scannerless: dispatch is implicit in first-sets, computed from the combinators themselves. That's more flexible — no lexer, tokens can overlap, a rule can mean different things in different positions — but it hides the cliff, because a choice that doesn't dispatch is still correct. diagnoseGrammar() buys back Chevrotain's "you can't forget to dispatch" guarantee without the lexer: the compiler already knows which choices dispatch and, for the ones that don't, exactly which arm to fix — wire the call into CI and forgetting becomes a failed build rather than a silent tax.

First-char gating — making the compiler dispatch your choices ​

Ask for it: diagnoseGrammar() ​

Why this is not a compile-time warning ​

What poisons a first-set ​

Common mistakes (and what the diagnosis tells you) ​

Accepting an intentional ungated choice (the snapshot allowlist) ​

Shared shapes: the verdict belongs to the fuse ​

Asking a composed grammar directly ​

CI: one call, one exit code ​

Why this is implicit in Parséman (the Chevrotain contrast) ​

See also ​