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

# 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

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:

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).