NFA compiler rejects grammar-optimizer output for grammars with a shared optional prefix

[GeorgeNgMsft]

Area: @typeagent/action-grammar (NFA compiler + grammar optimizer), @typeagent/action-grammar-compiler (agc)
Labels: bug, action-grammar, nfa, grammar-optimizer
Status: root-caused; a per-agent stopgap is already shipped (see Current mitigation). This issue tracks the proper core fix.

---

Summary

When agent-server runs the NFA grammar system (the default — grammarSystem: "nfa"), any grammar whose top-level alternatives all begin with the same optional sub-rule fails to compile to an NFA. The default agc optimizer rewrites those alternatives into a shape the NFA compiler refuses, so the schema silently loses its grammar fast-path and falls back to LLM translation. One schema (excel.excel-flow) surfaces it as a hard console.error on every startup; the rest fail quietly.

The underlying problem is an inconsistency between the two matchers in the package: the AST-walking (completion-based) matcher accepts and correctly evaluates the optimizer's output, but the NFA compiler does not.

---

Bug, or design gap? (triage framing)

Both — and they map cleanly onto the two blockers below:

• The tailCall incompatibility is a design choice that's no longer sufficient. tailFactoring /
  promoteTailRulesParts emit matcher-only constructs by design (documented at
  grammarOptimizer.ts:203-256). The original assumption was that NFA consumers would not use the
  optimized output. That assumption was broken by the pipeline + defaults: a single .ag.json is
  built once by agc (optimized) and consumed by whichever matcher is active, and agent-server now
  defaults to grammarSystem: "nfa". The seam (one artifact, two matchers with different capabilities)
  was never updated when NFA became the default. → addressed by Option B.
• The value-less multi-term rejection is a genuine bug. factorCommonPrefixes is not documented as
  matcher-only; the AST matcher accepts and correctly evaluates its output; and the NFA compiler already
  has the mechanism to handle it (getImplicitDefaultValue / its single-variable derivation) but applies
  it inconsistently and throws first. The optimizer and NFA compiler disagree about a shape that is
  supposed to be valid. → addressed by Option A.

This is why the recommended direction is A + B together: fix the inconsistency and update the
build seam that NFA-as-default outgrew.

---

How to reproduce

1. Build any agent grammar with agc (default optimizations on), where every <Start> alternative starts with a shared optional rule. Minimal example:

   <Start> = <a> | <b>;
   <a> = <P> 'foo' -> { actionName: "A" };
   <b> = <P> 'bar' -> { actionName: "B" };
   <P> = ('please')?;          // shared, fully optional prefix
   

2. Compile to .ag.json with agc (i.e. with recommendedOptimizations), then load it under the NFA path (grammarSystem: "nfa") — e.g. start agent-server.

3. Observe the failure. For excel.excel-flow it is logged loudly:

   Failed to compile grammar to NFA for excel.excel-flow:
   Error: Grammar rule at index 0 has 2 terms but no value expression.
   Multi-term rules must have an explicit value expression (using ->).
   

Expected: the grammar compiles to an NFA and matches normally.
Actual: compileGrammarToNFA throws; the schema gets no NFA grammar and falls back to LLM routing.

---

Root cause

What the optimizer does

agc compiles with recommendedOptimizations by default (actionGrammarCompiler/src/commands/compile.ts; preset at actionGrammar/src/grammarOptimizer.ts:258). The factorCommonPrefixes pass (grammarOptimizer.ts:988) factors the shared optional <P>/<Polite> prefix up to the top level, turning each single-term passthrough alternative (<a>) into a two-term rule:

[ <P>(optional, value-less) , RulesPart(<the rest, carrying the -> values>) ]

The -> value now lives inside the trailing RulesPart, not at the top level.

Two distinct NFA incompatibilities (this is the important part)

Relaxing only the first check is not sufficient — there are two separate blockers, both produced by the prefix-factoring family of passes:

1. Value-less multi-term top-level rule. nfaCompiler.ts:619 throws unconditionally when rule.parts.length > 1 && !rule.value. (This is the visible "2 terms but no value expression" error.)

2. tailCall RulesParts. With tailFactoring / promoteTailRulesParts enabled (both in recommendedOptimizations), the factored suffix is emitted as a RulesPart with tailCall: true. The NFA compiler hard-rejects these:

   compileRulesPartWithSlots: tail RulesParts are not supported by the NFA compiler.
   Disable `tailFactoring` in the grammar optimizer for NFA/DFA paths.
   

   These passes are matcher-only by design — see the doc comments at grammarOptimizer.ts:203-256: "only the AST-walking matcher understands tailCall; callers that route through the NFA compiler / DFA path must not use this preset."

I verified empirically (prototype: relax the :619 throw, rebuild, recompile the optimized grammar) that fixing only #1 immediately exposes #2. They are the same factored node: value-less at the top level and tailCall.

Optimization passes	Top-level shape	NFA (stock)	NFA (:619 relaxed)
none (--debug)	N × single-part	✅ compiles	✅
inlineSingleAlternatives + factorCommonPrefixes (no tail)	N × [<P>, RulesPart]	❌ value-less throw	✅ compiles (no tailCall)
recommendedOptimizations (adds tail passes)	N × [<P>, tailCall RulesPart]	❌ value-less throw	❌ tailCall refusal

Why the matchers disagree

The AST matcher already has well-defined semantics for a value-less multi-term rule: forward the value of the single value-bearing part. That logic exists as getImplicitDefaultValue (grammarOptimizer.ts:3313) — exactly one value-bearing part ⇒ that's the value; 0 or 2+ ⇒ genuinely ambiguous. The NFA compiler does not apply this. Its order is:

• nfaCompiler.ts:619 — throw first, before any derivation.
• nfaCompiler.ts:626-634 — only then derive an implicit value, and only for the trivial single-part isSingleVariableRule case.

So the NFA compiler rejects a rule shape the matcher considers valid and evaluable.

---

Impact / scope

This is not specific to one grammar. Confirmed real NFA-compile failures (same "2-term" class) in: excel (all sub-schemas), code (debugSchema, extensionSchema, generalSchema, vscodeShellSchema), github-cli, osNotifications. Any current or future grammar that gives every alternative a shared optional prefix (a very natural authoring pattern, e.g. an optional politeness lead-in) will trip it.

Only excel.excel-flow is loud: it provides a dynamic grammar, so its merged grammar is compiled via grammarStore.addGrammar, whose catch uses console.error (cache/src/cache/grammarStore.ts). All other schemas fail through the registry path (dispatcher/.../appAgentManager.ts ~:950-963), which logs via silent debugError and falls back — so the grammar fast-path is quietly dead for them.

---

Current mitigation (already shipped — context only)

The excel agent now builds the flow grammar with agc --debug (optimizations off), which emits the unoptimized, single-term form the NFA accepts. This is a per-grammar stopgap, not a fix: it concedes optimization for that one grammar and does nothing for the other affected agents. This issue is about fixing the root cause so the workaround can be removed.

---

Possible fixes to weigh

Option A — Teach the NFA compiler the matcher's implicit-default rule (addresses blocker #1)

At nfaCompiler.ts:617-634, replace the unconditional throw with implicit-value derivation mirroring getImplicitDefaultValue: one value-bearing part ⇒ forward it; only error when truly ambiguous.

• Pro: removes the matcher/NFA inconsistency at its source.
• Caveat: in the factored case the value-bearing part is a nested RulesPart whose alternatives carry their own -> object values (not a single variable), which getImplicitDefaultValue returns undefined for. So Option A likely must let the rule compile with no top-level actionValue and rely on the nested RulesPart alternatives' own actionValues propagating at accept time. Whether the NFA already propagates those correctly is the key open question (see below).
• Necessary but not sufficient on its own, because of blocker Fix .vscode directory casing #2.

Option B — Make agc emit NFA-safe optimizations for NFA targets (addresses blocker #2)

Add an nfaSafeOptimizations preset (inlineSingleAlternatives + factorCommonPrefixes, without tailFactoring / promoteTailRulesParts) and select it in agc for NFA-bound builds (new flag, or make it the default). I confirmed this subset avoids tailCall and compiles once blocker #1 is handled.

• Pro: keeps inlining + prefix-factoring (smaller/faster grammar) while staying NFA-compatible.
• Coupling: the prefix-factoring still yields value-less multi-term rules, so B is useless without A. A + B ship together.

Option C — Make the NFA compiler natively support tailCall RulesParts

Implement tailCall-equivalent semantics in the NFA compiler so recommendedOptimizations output compiles as-is.

• Con: tailCall is a matcher-specific frame-skip optimization; re-implementing it in the NFA is a large change that arguably defeats its purpose. Listed for completeness; not recommended as the first move.

Option D — Formalize "NFA target ⇒ build unoptimized"

Generalize the current --debug stopgap: treat unoptimized as the standard for NFA-bound grammars, and make agc express that explicitly (e.g. an --nfa flag) plus fix the docs.

• Pro: lowest effort/risk; the NFA does its own first-token dispatch, so the AST-level passes are largely redundant for it anyway.
• Con: forgoes prefix-factoring/inlining for the (rarely-used) completionBased consumers of the same .ag.json; doesn't reconcile the underlying matcher/NFA inconsistency.

Suggested direction: A + B together for the real fix (reconciles the inconsistency and keeps useful optimization), with D as the acceptable fallback if A's value-propagation turns out to be costly.

---

Open question to resolve first

Before committing to Option A, answer this with a focused test: for a factored [<optional-prefix>, RulesPart(alts each with ->)] rule, does the NFA produce the correct action value at match time if the :619 validation is bypassed? I could not confirm this with an ad-hoc harness (it failed to match even trivial literal grammars), so value-correctness must be proven by the package's own match/test infrastructure, not by hand. This single unknown determines whether Option A is a small validation-relaxation or needs real value-propagation work.

---

Acceptance criteria / validation

1. A new unit test that builds a factored [<optional-prefix>, RulesPart(values)] grammar, NFA-compiles it, and asserts the correct action value per branch.
2. cd ts/packages/actionGrammar && npm test green (compiler / matcher / optimizer suites).
3. NFA integration green: ts/packages/defaultAgentProvider/test/grammarNfaIntegration.spec.ts.
4. Every agent .ag.json compiles to an NFA (bulk-compile check over ts/packages/agents/**/dist/*.ag.json).
5. End-to-end spot check in an NFA-mode dispatcher for excel.excel-flow (run-flow-by-name + one lifecycle command), then remove the --debug stopgap from the excel build.

---

Key references

• NFA validation throw (blocker updating readme #1): ts/packages/actionGrammar/src/nfaCompiler.ts:619
• Existing implicit-value derivation (single-part only): ts/packages/actionGrammar/src/nfaCompiler.ts:626-634; passthrough normalization at :598-599
• tailCall rejection (blocker Fix .vscode directory casing #2): compileRulesPartWithSlots in nfaCompiler.ts
• Matcher's value semantics: getImplicitDefaultValue, ts/packages/actionGrammar/src/grammarOptimizer.ts:3313
• Optimizer preset + passes: recommendedOptimizations grammarOptimizer.ts:258; factorCommonPrefixes :988; tail-pass "matcher-only" docs :203-256
• agc optimization choice / --debug: ts/packages/actionGrammarCompiler/src/commands/compile.ts:66-91
• Loud vs silent error paths: ts/packages/cache/src/cache/grammarStore.ts (console.error); ts/packages/dispatcher/dispatcher/src/context/appAgentManager.ts loadDynamicGrammar (:1402-1496) and registry path (:898-964)
• NFA default for agent-server: ts/packages/commandExecutor/src/config/configLoader.ts:200; agentServerConfig.example.json