Context-Free Grammar (CFG)

A CFG is defined by a set of recursive production rules that map a single non-terminal symbol to a sequence of terminals and non-terminals. This structure allows for the generation of infinitely long strings from a finite set of rules.

• Non-terminals: Abstract syntactic categories (e.g., JsonObject, KeyValuePair).
• Terminals: The literal tokens that appear in the final output (e.g., {, "name", :).
• Start Symbol: The root non-terminal from which all valid strings are derived.

During grammar-constrained generation, the CFG is compiled into a state machine. At each decoding step, the model's logits are masked to set the probability of any token that would violate the grammar to zero.

• Token Masking: Physically prevents the model from sampling an invalid character.
• State Tracking: The parser maintains the current position in the grammar, determining the exact set of permissible next tokens.
• Guarantee: The final output is mathematically guaranteed to parse successfully against the defined schema.

GGML BNF (GBNF) is the specific grammar notation used by inference engines like llama.cpp to define syntactical rules for constrained decoding. It extends standard BNF to define the exact character-level rules a model must follow.

• Rule Definition: root ::= object defines the entry point.
• Character Sets: [a-zA-Z] defines permissible character ranges.
• Repetition: string ::= "\"" [^"\]* "\"" defines a valid JSON string pattern.

The 'Context-Free' property means a rule can reference itself, enabling the representation of arbitrarily nested structures like JSON objects within objects or balanced parentheses.

• Self-Reference: A rule like value ::= object | array | string allows an object to contain another object.
• Stack-Based Parsing: Requires a push-down automaton (PDA) with a stack to track nesting depth, unlike simpler regular expressions.
• Critical for JSON: This recursion is essential for generating complex, real-world data schemas.

A JSON Schema defines the expected data types and constraints, which can be automatically compiled into a CFG. This bridges the gap between a developer's data contract and the low-level token constraints.

• Schema Compilation: Tools convert a JSON Schema into a GBNF grammar string.
• Type Enforcement: The grammar ensures a field defined as an integer cannot be generated as a string.
• Required Fields: The grammar forces the model to generate all mandatory keys, preventing incomplete outputs.

While Regular Expressions can define simple token patterns, they lack the memory to handle nested structures. CFGs are strictly more powerful and are the minimal formalism required to describe most programming and data interchange languages.

• Regular Language: Cannot match balanced {} or [].
• Context-Free Language: Can enforce that every opening bracket has a corresponding closing bracket at the correct depth.
• Use Case: Use CFGs for JSON, XML, and code; use regex for simple date or ID format masking.

CFGs enable language models to reliably generate syntactically correct code in domain-specific languages (DSLs) such as SQL queries, regex patterns, or proprietary configuration formats where syntax errors are catastrophic.

• SQL Generation: Guarantees valid SELECT, JOIN, and WHERE clause structures
• Regex Synthesis: Ensures balanced character classes and valid quantifier syntax
• Configuration Files: Produces parseable YAML, TOML, or custom config formats without syntax errors

CFGs enforce the ReAct agent format and other chain-of-thought paradigms by constraining the model to output specific structural tokens like 'Thought:', 'Action:', and 'Observation:' in precise sequence. This guarantees parseable reasoning traces for downstream orchestration.

• Deterministic Parsing: Every reasoning step is machine-extractable without regex fragility
• Action Validation: Tool calls are constrained to valid function names and argument schemas
• Loop Prevention: Grammar rules can enforce termination conditions and maximum step counts

In task-oriented dialogue systems, CFGs constrain the model to populate predefined semantic frames with extracted entities. This ensures that virtual assistants collect all required information before executing backend transactions.

• Required Slot Enforcement: The grammar prevents dialogue completion until all mandatory slots are filled
• Type-Constrained Extraction: Dates are guaranteed ISO format, currencies have valid decimal precision
• Multi-Turn State Tracking: Grammar rules maintain valid slot states across conversation turns

The runtime process of forcing a language model's token generation to adhere to a predefined grammar. Unlike post-hoc validation, guided decoding modifies the sampling step directly.

• Token Masking: Dynamically sets the log probability of invalid tokens to negative infinity.
• Index-Based Generation: Pre-computes a trie of valid continuations for O(1) lookups.
• Guarantee: Ensures the final string is a member of the language defined by the grammar.

GGML BNF (GBNF) is the formal grammar notation used by llama.cpp and related runtimes for constrained decoding. It defines production rules that map directly to a finite-state machine.

• Syntax: Uses ::= for rule definitions and supports character ranges, alternation, and repetition.
• Integration: Passed directly as a grammar parameter to the inference server.
• Use Case: Defining JSON schemas or custom data formats without external libraries.

An open-source Python library for robust structured generation. It compiles a context-free grammar into an indexable finite-state machine before inference begins.

• Pre-compilation: Converts a Pydantic model or JSON Schema into a character-level FSM.
• Guarantee: Provides a mathematical guarantee of output validity, not just a probabilistic nudge.
• Workflow: model + generator → guaranteed structured output.

A declarative vocabulary for annotating and validating JSON documents. It serves as the most common interface for defining structured output constraints.

• Type Safety: Enforces string, number, array, and object types.
• Constraints: Defines required fields, enum values, and pattern regex.
• Adoption: The universal standard for API contracts, making it the default target for grammar-constrained generation.

The computational engine underlying grammar-constrained generation. An FSM tracks the current valid state of the output sequence.

• States: Represent positions within the grammar rules (e.g., 'inside a string', 'expecting a colon').
• Transitions: Define the set of permissible next characters or tokens.
• Determinism: The FSM ensures that from any valid state, only legal transitions are allowed, physically preventing syntax errors.

A Python data validation library that uses type hints to define schemas. It has become the de facto standard for structuring language model outputs in the Python ecosystem.

• BaseModel: Defines the expected fields, types, and validators.
• Integration: Libraries like Instructor and Outlines accept a Pydantic model as the target schema.
• Serialization: Provides built-in methods to dump the validated object back to a JSON string.