grammar-inference-engine/AGENTS.md

# Grammar Inference Engine — Agent Guide

## Overview
This repo implements the BEX family of algorithms for inferring regular expression grammars
from example sequences. Use it whenever you need to discover the pattern behind a set of
strings or structured sequences.

## Research Positioning

**We are the only approach that infers behavioral grammars from source code execution patterns.**

```
Others:
  Parser source code → Grammar (for input validation)
  Example strings → Grammar (for language definition)
  Grammar → LLM (for output constraint)

Us:
  Source code → Behavioral sequences → Grammar (for usage patterns)
  Grammar → LLM (for context/constraint)
```

### Related Work (2024-2026)
- **Panini** (OOPSLA'25): Infers grammars for ad hoc parsers via refinement types
- **Crucio** (ICSE'26): Black-box CFG inference from input/output examples
- **XGrammar** (NeurIPS'24): Constrained decoding engine for LLMs
- **DOMINO** (ICML'25): Minimally-invasive grammar-constrained decoding
- **Typify** (ICPC'26): Usage-driven Python type inference
- **DAInfer+** (2026): API specification inference from documentation

### Our Novelty
1. First to apply BEX algorithms to behavioral sequences (not XML/input data)
2. Language-agnostic preprocessing via tree-sitter (not language-specific)
3. Package-level behavioral patterns (not per-function or per-language)
4. Grammar as LLM context (not formal verification or testing)

See `experiments/RESEARCH_POSITIONING.md` for full analysis.

## Quick Start for Agents

```python
# Fast pattern inference
from bex.crx import CRX
g = CRX().infer([['a','b','c'], ['a','b'], ['a','c']])  # a.(b+c)?

# Probabilistic k-ORE inference (handles noise better)
from bex.idregex import idregex
g = idregex([['a','b','c'], ['a','b'], ['a','c']], kmax=2, N=3)
```

## Use Cases
1. **LLM code generation guidance** — provide behavioral grammars as context for correct API usage
2. **API pattern documentation** — auto-generate usage patterns from codebases
3. **Test case generation** — use grammars to generate valid API call sequences
4. **Code review** — detect deviations from learned behavioral patterns
5. **Migration assistance** — compare behavioral patterns across framework versions

## Architecture

Three inference pipelines:

| Pipeline | When to use |
|----------|-------------|
| CRX (fast, default) | Many examples, need speed, CHAREs output |
| Refined CRX (`--crx-method refined`) | Flat bags, need tighter grammars (cluster-then-infer) |
| iDRegEx (`--idregex-refine`) | Rare: small groups with many optionals, need 100x+ improvement |

## Running Tests
```bash
python -m pytest tests/
```

## MCP Server

The primary interface is an MCP server exposing two tools:

| Tool | Parameters | What it does |
|------|-----------|-------------|
| `infer_best_grammar` | `sequences`, `prefer`, `kmax`, `N`, `min_coverage` | Infer grammar from raw sequences. Runs CRX + iDRegEx, picks best by MDL. |
| `analyze_directory` | `directory`, `slice`, `min_coverage`, `prefer`, `kmax`, `include`, `exclude`, `main_only`, `max_mdl`, `persist` | Scan source code, infer conventions per package. Returns YAML grouped by module. Auto-persists to `{directory}/.dervish/grammars.yml`. |

Start it: `python /path/to/bex/mcp_server.py`, then connect any MCP client.

## Tag Preprocessor CLI

For analyzing source code directories:

```bash
python -m bex.tag_preprocessor.analyze /path/to/codebase --verbose
python -m bex.tag_preprocessor.analyze /path/to/codebase --slice package --include '**/src/**'
```

Key flags: `--slice package` (per-directory grammars), `--split-mixed` (recursive split by first symbol), `--crx-method refined` (tighter grammars on flat bags), `--verbose` (progress), `--include`/`--exclude` (glob filters), `--main-only` (exclude test files), `--idregex-refine` (enable iDRegEx on small flat bags).