Course contentsShow
← Machine Learning and Deep Learning
Lesson 1915 of 3,53841. Structured Output and Tool CallingFree lesson

Grammar-Based Generation

Explore context-free grammars and how they guide token generation to match desired output formats.

Grammar-Based Generation

What you'll learn: How context-free grammars act as explicit rules that guide LLM token generation to produce syntactically valid, structured outputs.

The Core Idea

Grammar-based generation uses formal grammar rules (like those defining programming languages or data formats) to restrict which tokens an LLM can produce at each step. Instead of letting the model freely sample from its entire vocabulary, you enforce that every generated token must follow the grammar's syntax rules—ensuring the output is valid by construction.

Think of it like auto-complete with strict rules: when you're typing JSON and just opened a brace {, grammar-based generation only allows keys (strings) next, not closing braces or random text. The grammar acts as a filter over the model's token probabilities.

How Context-Free Grammars Work

A context-free grammar (CFG) defines:

  • Terminals: actual tokens (like {, "name", :, numbers)
  • Non-terminals: structural elements (like <object>, <array>, <value>)
  • Production rules: how non-terminals expand (e.g., <object> → { <key-value-pairs> })

During generation, the grammar determines what tokens are legal at each position based on the current parse state. The LLM's logits are masked to zero probability for illegal tokens, then re-normalized before sampling.

Why This Matters

Unlike prompt engineering alone (which asks the model to follow format), grammar-based generation guarantees syntactic validity. You'll never get malformed JSON with unclosed brackets or illegal characters—the grammar simply won't allow it.

Key Takeaway: Grammar-based generation enforces structural validity by using context-free grammar rules to constrain which tokens the model can produce at each step, guaranteeing well-formed outputs like valid JSON or code.