Chapter 3

Context-Free Grammars

The formal language that describes programming language syntax. Learn the four components, how production rules work, and why grammars define the language a parser recognizes.

Terminals & Non-Terminals Production Rules Language L(G) Left Recursion
Section 1

What Makes a Grammar?

A Context-Free Grammar (CFG) is a 4-tuple G = (V, Σ, P, S). Every grammar you'll ever encounter in compiler construction has exactly these four pieces.

🔵
Terminals (Σ)
The actual symbols of the language — the tokens that appear in source code. They cannot be expanded further. The scanner produces terminals.
id + * ( ) $
🟣
Non-Terminals (V)
Abstract categories that represent syntactic constructs. They appear on the left-hand side of productions and must eventually expand to terminals.
E E′ T T′ F
⚙️
Productions (P)
Transformation rules of the form A → α, where A is a non-terminal and α is any string of terminals and non-terminals (including ε, the empty string).
A → α
A → β | alternative
🟠
Start Symbol (S)
A designated non-terminal from which every derivation begins. The language of the grammar is all terminal strings derivable from S.
E (for our grammar)
📐 Formal Definition: G = (V, Σ, P, S)
V Set of non-terminal symbols (variables): {E, E′, T, T′, F}
Σ Set of terminal symbols (disjoint from V): {id, +, *, (, ), $}
P Finite set of production rules: A → α where A ∈ V, α ∈ (V ∪ Σ)*
S Start symbol: S ∈ V, in our case S = E
💡 Why "Context-Free"? A rule A → α can be applied anywhere A appears, regardless of surrounding context. This is what makes CFGs more powerful than regular grammars (regular expressions) but less powerful than context-sensitive grammars.
Section 2

The Running Example Grammar

We'll use this grammar throughout the entire course. It describes arithmetic expressions with addition and multiplication, handling operator precedence correctly.

Ambiguous Version (shows concepts)

1 E → E + T
2 E → T
3 T → T * F
4 T → F
5 F → ( E )
6 F → id
⚠️ Left Recursive! E → E + T and T → T * F are left-recursive. This grammar is used for LR parsing (bottom-up).

LL(1) Version (left-recursion removed)

1 E → T E′
2 E′ → + T E′ | ε
3 T → F T′
4 T′ → * F T′ | ε
5 F → ( E ) | id
✅ LL(1) Ready! No left recursion. Used for top-down parsers (recursive descent, LL(1) table).
🎯 Operator Precedence via Grammar Structure: Notice that F (Factor) is nested inside T (Term) which is nested inside E (Expression). This hierarchy enforces that * binds tighter than + — operator precedence falls directly out of the grammar structure!
Section 3 — Interactive

Identify the Symbol

Click on any symbol below to learn whether it's a terminal or non-terminal and what role it plays in the grammar.

👆 Click a symbol above to learn about it
Each symbol in a grammar has a specific type and role. Terminals are the actual tokens; non-terminals are abstract placeholders that expand via production rules.
Non-Terminal
Terminal
Section 4

Production Rules Explained

A production rule A → α says: "the non-terminal A can be replaced by the string α." Understanding the structure of production rules is key to understanding all parsing algorithms.

Anatomy of a Production Rule

E → E + T
LHS
Left-hand side — ALWAYS exactly one non-terminal. This is what gets replaced. In CFGs, the LHS constraint is what makes them "context-free."
RHS
Right-hand side — any string of terminals and non-terminals, including ε (empty). Here: E + T means "expression, then plus sign, then term."

The | Notation (Alternatives)

|
The vertical bar | means "or" — it separates alternative right-hand sides for the same non-terminal. It's purely shorthand notation.
F → (E) | id ← shorthand for the two rules below
F → (E) ← Rule 1: F can be a parenthesized expression
F → id ← Rule 2: F can be a single identifier

Epsilon (ε) Productions — The Empty String

E′ → + T E′ | ε
The ε (epsilon) production means E′ can produce the empty string — it simply disappears from the derivation. This is used to terminate the recursion. When a parser sees ε, it means "nothing more to expand here."
📝 Key Constraint: The left-hand side of every production rule must be exactly one non-terminal. This is the defining feature of context-free grammars. If you had rules like aAb → aBb (context-dependent), that would be a context-sensitive grammar.
Section 5

Language of a Grammar: L(G)

The language defined by a grammar G is the set of all strings of terminals that can be derived from the start symbol. Some strings are in L(G), some are not.

📐 Formal Definition
L(G) = { w ∈ Σ* | S ⟹* w }
Read as: "The language of grammar G is the set of all strings w of terminals such that the start symbol S can derive w in zero or more steps."
✅ Strings IN L(G)
✓ id — simplest expression: F→id, T→F, E→T
✓ id + id — addition of two identifiers
✓ id * id — multiplication of two identifiers
✓ id + id * id — mixed: * has higher precedence
✓ (id + id) * id — parentheses override precedence
✓ (id) — parenthesized single id
✓ id + id + id — chained addition (left-associative)
❌ Strings NOT in L(G)
✗ + id — no production starts with +
✗ id id — two ids with no operator
✗ * * — operators without operands
✗ (id — unmatched parenthesis
✗ id + — trailing operator, no RHS
✗ id * + id — two consecutive operators
✗ (empty) — ε not derivable from E

Derivation Trace: id + id * id ∈ L(G) (using LL(1) grammar)

Section 6

Left Recursion: A Top-Down Parser's Nightmare

Left recursion occurs when a non-terminal can eventually derive a string starting with itself. This is perfectly fine for LR parsers, but causes infinite loops in recursive descent (top-down) parsers.

⚠️ Direct Left Recursion: E → E + T

To parse E, a top-down parser tries to match rule E → E + T. So it immediately needs to parse E again — before consuming any input! This causes infinite recursion:
▶ Try to parse E
▶ Apply E → E + T, need to parse E first...
▶ Apply E → E + T, need to parse E first...
∞ Stack overflow! Infinite loop!

✅ The Fix: Eliminate Left Recursion

The general algorithm for eliminating direct left recursion converts A → Aα | β into right-recursive form using a new non-terminal A′:

BEFORE (left-recursive)
E→ E + T
E→ T
⟹
AFTER (right-recursive)
E→ T E′
E′→ +T E′ | ε
⚠️ Indirect Left Recursion — More subtle: A → Bα, B → Aβ. This also causes infinite loops. Elimination requires multiple steps. The Dragon Book (Aho et al.) Chapter 4.3 covers the full algorithm for removing all left recursion.
🔗 Coming Up:
  • Page 4 (Derivations) — See how grammars generate parse trees
  • Page 5 (Recursive Descent) — Top-down parsers that require no left recursion
  • Page 6 (LL(1)) — Table-driven top-down parsing
  • Page 7+ (LR parsers) — Bottom-up parsers that handle left-recursive grammars naturally
Summary

Key Takeaways

📦

4 Components

Every CFG has: Terminals (Σ), Non-Terminals (V), Productions (P), and Start Symbol (S). Written G = (V, Σ, P, S).

⚙️

Production Rules

Always of the form A → α (one NT on left). The | operator provides alternatives. ε means the empty string.

🌐

Language L(G)

All strings of terminals derivable from the start symbol. The grammar defines exactly which programs are syntactically valid.

⚠️

Left Recursion

A → Aα breaks top-down parsers (infinite loop). Must be eliminated for LL(1)/recursive descent. LR parsers handle it naturally.