# Action Grammar

A grammar engine for [TypeAgent](../../README.md) that parses, compiles, and matches natural language input against grammar rules to produce structured JSON action objects. It converts user utterances like `"play Shape of You by Ed Sheeran"` into typed actions like `{ actionName: "play", parameters: { track: "Shape of You", artist: "Ed Sheeran" } }`.

Grammar rules are defined in **`.agr` files** — a custom DSL that supports literals, wildcards, alternation, optionals, repetition, rule references, imports, and entity declarations.

## Architecture

```
.agr file → parseGrammarRules() → GrammarParseResult (AST)
                                       ↓
                                 compileGrammar() → Grammar (in-memory)
                                       ↓
              ┌────────────────────────┴────────────────────────┐
              │ Recursive Backtracking                          │ NFA/DFA Pipeline
              │ matchGrammar()                                  │ compileGrammarToNFA()
              │                                                 │       ↓
              │                                                 │   matchNFA()
              │                                                 │       ↓
              │                                                 │ compileNFAToDFA()
              │                                                 │       ↓
              │                                                 │   matchDFA()
              └─────────────────────────────────────────────────┘
```

Two matching backends are available, each with different trade-offs:

- **Recursive backtracking matcher** (`matchGrammar()`) — Operates directly on the `Grammar` AST with backtracking for wildcards and nested rules. Simpler and more flexible for certain grammar patterns.
- **NFA/DFA pipeline** (`compileGrammarToNFA()` → `matchNFA()` / `matchDFA()`) — Compiles grammar to a token-based NFA with parallel execution threads, epsilon closures, and priority-based result selection; optionally further compiled to a deterministic DFA for faster matching.

## `.agr` Grammar Syntax

```agr
entity CalendarDate, Ordinal;                         // Entity declarations
import { Helper } from "./other.agr";                 // Grammar imports

<Start> = <PlaySong> | <SkipTrack>;                   // Start rule
<PlaySong> [spacing=optional] =                        // Spacing annotation
    play $(track:wildcard) by $(artist:wildcard)        // Wildcards with captures
    -> { actionName: "play",                            // Action value expression
         parameters: { track, artist } };
<SkipTrack> = (skip | next) (track | song)?            // Optionals, alternation
    -> { actionName: "skip" };
<Items> = $(item:string) (, $(item:string))*;          // Repetition (Kleene star)
```

## Exports

The package exposes three entry points:

### Main (`"."`)

Core grammar types, parsing, compilation, matching, serialization, entity system, NFA/DFA system, and dynamic loading:

| Category                | Key Exports                                                                                                                      |
| ----------------------- | -------------------------------------------------------------------------------------------------------------------------------- |
| **Loading/Parsing**     | `loadGrammarRules()`, `loadGrammarRulesNoThrow()`, `parseGrammarRules()`                                                         |
| **Serialization**       | `grammarToJson()`, `grammarFromJson()`                                                                                           |
| **Recursive Matching**  | `matchGrammar()`, `matchGrammarCompletion()`                                                                                     |
| **NFA/DFA**             | `NFA`, `compileGrammarToNFA()`, `matchNFA()`, `matchNFAWithIndex()`, `buildFirstTokenIndex()`, `compileNFAToDFA()`, `matchDFA()` |
| **Collision Analysis**  | `findGrammarOverlap()`, `scanGrammarCollisions()`, `stripTailCalls()`, `formatRulePartsText()`, `collectTopLevelRules()`         |
| **Writer**              | `writeGrammarRules()`                                                                                                            |
| **Entity System**       | `EntityRegistry`, `globalEntityRegistry`, `createValidator()`, `createConverter()`                                               |
| **Built-in Entities**   | `Ordinal`, `Cardinal`, `CalendarDate`, `CalendarTime`, `CalendarTimeRange`, `CalendarDayRange`                                   |
| **Phrase Set Matchers** | `globalPhraseSetRegistry`, `PhraseSetMatcher`                                                                                    |
| **Dynamic Loading**     | `DynamicGrammarLoader`, `DynamicGrammarCache`                                                                                    |
| **Environment**         | `Environment`, `SlotMap`, `SlotAssignment`, `ValueExpression`                                                                    |

### Rules (`"./rules"`)

Lightweight export for tooling — exposes parser AST types and the pretty-printer:

- `ValueNode`, `Expr`, `Rule`, `RuleDefinition`
- `writeGrammarRules()`

### Generation (`"./generation"`)

LLM-powered grammar generation from schemas and examples:

- `ClaudeGrammarGenerator` — Uses Claude to analyze request/action pairs and generate grammar rules
- `SchemaToGrammarGenerator` — Auto-generates `.agr` grammar from a full action schema (`.pas.json`)
- `ScenarioBasedGrammarGenerator` — Generates grammar using predefined scenario templates
- `loadSchemaInfo()`, `SchemaInfo`, `ActionInfo` — Schema reading utilities

## Key Source Files

| File                         | Purpose                                                                   |
| ---------------------------- | ------------------------------------------------------------------------- |
| `grammarRuleParser.ts`       | Recursive descent parser for `.agr` files                                 |
| `grammarCompiler.ts`         | Compiles parsed rules into the in-memory `Grammar` representation         |
| `grammarTypes.ts`            | Types for in-memory and serialized grammar representations                |
| `grammarMatcher.ts`          | Recursive backtracking matcher                                            |
| `grammarCompletion.ts`       | Completion system (partial-match completions from grammar rules)          |
| `nfaCompiler.ts`             | Compiles `Grammar` → token-based NFA with slot-based variable capture     |
| `nfaInterpreter.ts`          | Parallel NFA execution with priority ranking                              |
| `nfaIntersection.ts`         | NFA product-construction overlap detector — `findGrammarOverlap()`        |
| `grammarCollisionScanner.ts` | Pairwise cross-schema scanner with tail-call strip + JSON-friendly result |
| `dfaCompiler.ts`             | NFA→DFA subset construction                                               |
| `dfaMatcher.ts`              | DFA-based matching and completion                                         |
| `entityRegistry.ts`          | Entity registry with validators and converters                            |
| `builtInEntities.ts`         | Built-in entity converters (dates, times, ordinals, cardinals)            |
| `builtInPhraseMatchers.ts`   | Phrase set registry (Polite, Greeting, Acknowledgement, FillerWord)       |
| `environment.ts`             | Slot-based environment system for NFA/DFA variable capture                |
| `grammarStore.ts`            | Persists dynamically generated grammar rules with auto-save               |
| `grammarMerger.ts`           | Utilities for merging and combining grammars                              |
| `grammarMetadata.ts`         | Enriches grammars with checked-variable metadata from `.pas.json` schemas |
| `dynamicGrammarLoader.ts`    | Runtime rule loading, entity validation, NFA compilation                  |
| `agentGrammarRegistry.ts`    | Per-agent grammar management with dynamic rule addition                   |
| `grammarRuleWriter.ts`       | Pretty-prints grammar parse results back to `.agr` format                 |

## File Formats

| Format      | Description                                                                                               |
| ----------- | --------------------------------------------------------------------------------------------------------- |
| `.agr`      | Source grammar files — human-readable DSL with entities, imports, rules, wildcards, and value expressions |
| `.ag.json`  | Compiled grammar JSON (`GrammarJson`) for sharing/caching without re-parsing                              |
| `.pas.json` | Parsed Action Schema JSON (from `action-schema`) used for checked-variable enrichment                     |

## Building

```bash
# Build
npm run build

# Run unit tests
npm test

# Run integration tests (requires API keys)
npm run test:integration

# Run a specific test suite
pnpm run jest-esm --testPathPattern="grammarMatcherBasic"
```

Key test suites:

- `grammarMatcherBasic.spec.ts` — Core recursive backtracking behavior
- `grammarMatcherVariables.spec.ts` — Variable capture and value expressions
- `grammarMatcherSpacingBasic.spec.ts` — Spacing mode handling
- `grammarCompletionKeywordSpacePunct.spec.ts` — Completion with keyword spacing and punctuation
- `nfa.spec.ts` — NFA builder and compilation
- `nfaDfaParity.spec.ts` — NFA/DFA equivalence verification
- `nfaPriority.spec.ts` — Match priority and ranking
- `nfaRealGrammars.spec.ts` — End-to-end tests with production grammars
- `dfa.spec.ts` — DFA compiler correctness
- `dfaBenchmark.spec.ts` — Performance benchmarks
- `grammarOptimizer*.spec.ts` — Compile-time AST optimizer (inline + factor passes)

## CLI: `analyze-grammar-collisions`

Standalone counterpart to the in-shell `@grammar collisions` command — discovers `*.ag.json` files under a directory, runs the same NFA-product-construction collision detector ([`grammarCollisionScanner.ts`](src/grammarCollisionScanner.ts)), and emits a JSON report keyed by canonical `"schemaA|schemaB"` (alphabetical) for offline post-processing or CI gates.

```bash
# After build, the bin is registered in package.json:
node ./dist/generation/analyze-grammar-collisions-cli.js [options]

# Or via pnpm-link / npm-link:
analyze-grammar-collisions [options]
```

| Option             | Description                                                  |
| ------------------ | ------------------------------------------------------------ |
| `-d, --dir <path>` | Recurse this directory for `*.ag.json` files (default: cwd). |
| `-o, --out <path>` | Write JSON report to this file (default: stdout).            |
| `-q, --quiet`      | Suppress progress messages on stderr.                        |
| `-h, --help`       | Show usage and exit.                                         |

The report shape is `CollisionScanResult` (see [`grammarCollisionScanner.ts`](src/grammarCollisionScanner.ts)):

```jsonc
{
  "scannedAt": "2026-05-05T18:04:51.234Z",
  "schemas": { "<schemaName>": { "schemaName", "rulesCount", "compiledWithStripping" } },
  "skipped": [ { "schemaName", "reason": "compile-error" | "parse-error" | "no-grammar" | "wrong-format", "error?" } ],
  "totalRules": 520,
  "collisions": {
    "schemaA|schemaB": {
      "schemaA", "schemaB",
      "witness": ["token", "..."],          // token sequence both grammars accept
      "witnessText": "token ...",
      "hasPlaceholders": false,             // true → witness contains synthetic <TypeName>
      "ruleIndexA": 8, "ruleIndexB": 6,
      "rulePatternA": "<rules>",            // pretty-printed colliding rule
      "rulePatternB": "<rules>",
      "matchA": { "actionName": "expand", "parameters": { "archivePath": "x" } },
      "matchB": { "actionName": "openWebPage", "parameters": { "site": "archive x" } }
    }
  }
}
```

Duplicate schema names (e.g. multiple build outputs of the same agent) are deduped by name — first occurrence wins; warnings go to stderr. Grammars carrying optimizer `tailCall` markers are auto-stripped before NFA compile and counted in `schemas[].compiledWithStripping`.

## Optimizer benchmarks

Standalone benchmarks for the opt-in compile-time grammar optimizer
([`src/bench/`](src/bench/)) are not part of the jest suite. They
execute the compiled output, so a build is required first:

```bash
pnpm run tsc
pnpm run bench:synthetic   # synthetic pass-through / wide-prefix grammars
pnpm run bench:real        # real agent grammars (player, list, calendar)
pnpm run bench             # both
```

Each script prints a per-configuration table comparing baseline,
inline-only, factor-only, and both. Speedup is colored once it moves
more than 10% from baseline.

## Downstream consumers

| Package                 | Usage                                              |
| ----------------------- | -------------------------------------------------- |
| `dispatcher`            | Per-agent grammar matching; dynamic rule loading   |
| `cache`                 | Serialized grammar storage; grammar store          |
| `agentSdkWrapper`       | Schema-to-grammar generation bridge                |
| `defaultAgentProvider`  | Grammar integration tests with real agent grammars |
| `cli`                   | Grammar matching commands                          |
| `actionGrammarCompiler` | Standalone compilation and formatting tools        |

## Debugging

Enable debug logging with environment variables:

```bash
DEBUG=typeagent:grammar:*        # Parsing and matching
DEBUG=typeagent:nfa:*            # NFA execution
DEBUG=typeagent:dfa:*            # DFA operations
DEBUG=typeagent:actionGrammar:*  # Grammar generation
```

## Dependencies

| Dependency                  | Purpose                                                                               |
| --------------------------- | ------------------------------------------------------------------------------------- |
| `action-schema` (workspace) | Reading `.pas.json` schema files for checked-variable enrichment                      |
| `debug`                     | Debug logging (`typeagent:grammar:*`, `typeagent:nfa:*`, `typeagent:actionGrammar:*`) |
| `regexp.escape`             | Safe regex escaping for the simple recursive backtracking matcher                     |

## Trademarks

This project may contain trademarks or logos for projects, products, or services. Authorized use of Microsoft
trademarks or logos is subject to and must follow
[Microsoft's Trademark & Brand Guidelines](https://www.microsoft.com/en-us/legal/intellectualproperty/trademarks/usage/general).
Use of Microsoft trademarks or logos in modified versions of this project must not cause confusion or imply Microsoft sponsorship.
Any use of third-party trademarks or logos are subject to those third-party's policies.
