Course contentsShow
← AI Engineering
Lesson 778 of 1,88619. Structured Output and ValidationFree lesson

Context-Free Grammars (CFG) Basics

Understand CFG notation and how production rules define valid token sequences for structured output.

Context-Free Grammars (CFG) Basics

What you'll learn: How CFG notation works and defines valid token sequences to generate precisely structured output from language models.

What is a Context-Free Grammar?

A Context-Free Grammar (CFG) is a formal system of rules that specifies which sequences of tokens (words, symbols, or characters) are valid in a language. In AI engineering, CFGs let you constrain LLM output to follow exact patterns—like ensuring JSON is valid, numbers follow specific formats, or responses match domain-specific syntax.

Think of a CFG as a recipe book where each recipe (called a production rule) tells you how to build valid pieces of text. Each rule has a left side (a placeholder name) and a right side (what that placeholder can become).

CFG Notation

CFG rules look like this:

<number> ::= <digit> | <digit> <number>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Breaking this down:

  • <number> and <digit> are non-terminals (placeholders)
  • "0", "1", etc. are terminals (actual characters)
  • ::= means "can be replaced by"
  • | means "OR" (choose one option)

This grammar says "a number is either a single digit, or a digit followed by more digits."

Why This Matters for Structured Output

When you combine CFGs with grammar-based generation, the LLM can only produce tokens that follow your rules—guaranteeing valid output without post-hoc validation. This is more reliable than hoping the model formats correctly or fixing errors after generation.

Key Takeaway: Context-Free Grammars use production rules to formally define which token sequences are valid, enabling LLMs to generate guaranteed-correct structured output.