Context-Free Grammars

The workhorse of programming language design — context-free grammars let you describe nested, recursive structures like expressions and blocks with simple, elegant rules.

Why Do We Need Context-Free Grammars?

You already know that regular grammars (right/left linear) describe regular languages — things like identifiers, numbers, and keywords. But regular grammars have a hard limit: they cannot count or match pairs.

Consider:

Balanced parentheses: (), (()), ((())) — regular grammars cannot express this
Matching if…end blocks — same problem
Nested arithmetic: (a + (b * c)) — same problem

Regular grammars have no memory of what they have seen. They can't "remember" that they opened a parenthesis and need to close it later.

Context-free grammars (CFGs) solve this. A CFG can handle any recursively nested structure, which is exactly what programming languages are built from.

Example

Regular grammar can describe: Context-free grammar can also describe:

a, ab, abc, ... (a), ((a)), (((a))), ...

a*, aab*, aabb*, ... aⁿbⁿ, i.e., ab, aabb, aaabbb, ...

keywords, identifiers if-else blocks, while loops, expressions

Formal Definition

A context-free grammar (CFG) is a grammar G = (V, T, P, S) where every production rule has the form:

Example

A → α

where:

A is a single non-terminal (just one, on the left)
α is any string of terminals and non-terminals (or ε), on the right

That's it. The only rule: the left-hand side must be a single non-terminal. There is no surrounding context required — A can always be replaced by α regardless of what is around it.

This is what makes a grammar "context-free": the replacement of A does not depend on the context (the symbols surrounding A).

Contrast with Other Grammar Types

Grammar Type	Production Form	Power
Regular (Type 3)	A → aB or A → a	Least — no nested structures
Context-Free (Type 2)	A → α (any string)	Medium — nested structures ✓
Context-Sensitive (Type 1)	αAβ → αγβ	More — depends on context
Unrestricted (Type 0)	α → β (anything)	Most — Turing complete

The Key Insight

In a context-sensitive grammar, the rule αAβ → αγβ says:

"A can be replaced by γ, but only when it has α on its left and β on its right."

In a context-free grammar, the rule A → α says:

"A can be replaced by α, always, no matter what surrounds it."

Context-free is a special case of context-sensitive where α = β = ε (empty context).

Building CFGs — Three Core Examples

Example 1 — Balanced Parentheses

Language: L = { all strings of balanced parentheses } = { ε, (), (()), ()(), ((())), ()(()), … }

Grammar:

Example

G: S → (S) | SS | ε

Reading the rules:

S → (S) — wrap whatever S generates in one pair of parentheses
S → SS — concatenate two balanced sequences side by side
S → ε — the empty string is valid (zero pairs)

Derivation of "(())()":

Example

→ SS (S → SS)

→ (S)S (first S → (S))

→ ((S))S (inner S → (S))

→ (())S (innermost S → ε)

→ (())(S) (remaining S → (S))

→ (())() (S → ε)

Example 2 — The Language aⁿbⁿ

Language: L = { aⁿbⁿ | n ≥ 1 } = { ab, aabb, aaabbb, … }

Grammar:

Example

G: S → aSb | ab

S → ab — the base case: one a followed by one b
S → aSb — wrap the current S with one more a on the left and one more b on the right

Derivation of "aaabbb":

Example

→ aSb (S → aSb)

→ aaSbb (S → aSb)

→ aaabbb (S → ab)

No regular grammar can generate this language — CFGs are more powerful.

Example 3 — Arithmetic Expressions

Language: Arithmetic expressions with +, *, parentheses, and identifiers.

Grammar:

Example

E → E + T | T

T → T * F | F

F → ( E ) | id

This grammar captures operator precedence and associativity:

* binds tighter than + because T is nested inside E
Both + and * are left-associative because E → E + T and T → T * F recurse on the left

Derivation of "id + id * id":

Example

→ E + T

→ T + T

→ F + T

→ id + T

→ id + T * F

→ id + F * F

→ id + id * F

→ id + id * id

The multiplication is in a deeper subtree (T level), so it has higher precedence than addition (E level). This is the same structure used in real compiler front ends.

What CFGs Can Do That Regular Grammars Cannot

The key difference is nesting and counting. A CFG has unlimited "memory" through recursion in non-terminals. A regular grammar has no such memory — once a symbol is consumed it's gone.

Task	Regular Grammar	CFG
Match "aaaa…" (any number of a's)	✓ S → aS	ε
Match aⁿbⁿ (equal a's and b's)	✗ impossible	✓ S → aSb
Match balanced parentheses	✗ impossible	✓ S → (S)
Match nested if-else	✗ impossible	✓ Stmt → if E then Stmt
Describe token patterns (identifiers, numbers)	✓	✓ (but overkill)

Why Programming Languages Use CFGs

Almost every mainstream programming language (C, Java, Python, Go…) is defined using a CFG in a Backus-Naur Form (BNF) or extended BNF. For example, a simplified BNF for an if-statement:

Example

Stmt → if Expr then Stmt

| if Expr then Stmt else Stmt

| while Expr do Stmt

| { StmtList }

| id = Expr ;

Expr → Expr + Term | Expr - Term | Term

Term → Term * Factor | Term / Factor | Factor

Factor → ( Expr ) | id | num

This grammar precisely defines what is and is not a valid statement in the language. The parser (phase 2 of a compiler) uses this grammar to check and understand the program's structure.

One Important Limitation

CFGs cannot express context-dependent constraints like:

"A variable must be declared before it is used"
"A function call must have the same number of arguments as its definition"

These rules are handled by semantic analysis (phase 3), not by the CFG. This is intentional — keeping the grammar context-free makes parsing fast and predictable.

Practice Questions

Question 1 — Construct a CFG for the language of all Non-Palindromes.

Given: Σ = {a, b}. Construct a context-free grammar G such that L(G) is the set of all strings over Σ that are not palindromes.

Answer:

Step 1 — Understand the language.

A string w is a palindrome if w = reverse(w), e.g. ε, a, b, aa, aba, abba, …

A string w is a non-palindrome if w ≠ reverse(w), e.g. ab, ba, aab, abb, aabb, abab, …

Step 2 — Key observation (how a non-palindrome arises).

A string w is a non-palindrome if and only if one of the following holds:

The outermost characters differ — w starts with a and ends with b, or starts with b and ends with a.
The outermost characters are the same, but the inner string is a non-palindrome — w = a·w'·a where w' is a non-palindrome, or w = b·w'·b where w' is a non-palindrome.

This gives a clean recursive structure that a CFG can express directly.

Step 3 — Write the grammar.

Let S generate all non-palindromes, and A generate any string over {a, b}* (including ε).

Example

S → a A b (1)

| b A a (2)

| a S a (3)

| b S b (4)

A → ε (5)

| a A (6)

| b A (7)

Step 4 — Explain each production.

Production	Meaning
S → aAb	w starts with a and ends with b — outermost chars differ, so w is guaranteed a non-palindrome regardless of the middle
S → bAa	w starts with b and ends with a — same reasoning, outer mismatch
S → aSa	Outermost chars are both a (no outer mismatch), but the inner string S is a non-palindrome — so the whole string is also a non-palindrome
S → bSb	Same as above with b on both ends
A → ε	aA

Step 5 — Derivation examples.

Example 1 — Derive "ab" (a non-palindrome):

Example

S → a A b (rule 1)

→ a ε b (rule 5: A → ε)

= ab ✓

"ab" reversed is "ba" ≠ "ab", so it is indeed a non-palindrome.

Example 2 — Derive "aab" (a non-palindrome):

Example

S → a A b (rule 1)

→ a a A b (rule 6: A → aA)

→ a a ε b (rule 5: A → ε)

= aab ✓

"aab" reversed is "baa" ≠ "aab". ✓

Example 3 — Derive "aaba" (a non-palindrome):

Example

S → a S a (rule 3)

→ a (a A b) a (rule 1 applied to inner S)

→ a (a ε b) a (rule 5: A → ε)

= aaba ✓

"aaba" reversed is "abaa" ≠ "aaba". ✓

Step 6 — Verify the grammar does NOT generate palindromes.

Consider "abba" (a palindrome). Try all rules:

S → aAb: w must end in b. "abba" ends in a. ✗
S → bAa: w must start with b. "abba" starts with a. ✗
S → aSa: strip outer a's → inner string is "bb". Is "bb" a non-palindrome? No — "bb" is a palindrome. S cannot generate "bb". ✗
S → bSb: w must start with b. "abba" starts with a. ✗

"abba" cannot be derived. ✓

Final Grammar (clean form):

Example

G = ( {S, A}, {a, b}, P, S )

S → aAb | bAa | aSa | bSb

A → ε | aA | bA

L(G) = { w ∈ {a,b} | w is not a palindrome }*

Question 2 — Construct a CFG for the language L = { 0ⁿ 1⁴ⁿ | n ≥ 1 }.

Given: Σ = {0, 1}. Construct a context-free grammar G such that L(G) = { 0ⁿ 1⁴ⁿ | n ≥ 1 }, i.e., strings of n zeros followed by exactly 4n ones.

Examples: 01111, 0011111111, 000111111111111, …

Answer:

Step 1 — Understand the language.

n	String	Pattern
1	0 1111	1 zero, 4 ones
2	00 11111111	2 zeros, 8 ones
3	000 111111111111	3 zeros, 12 ones

The rule is: every time one 0 is added on the left, exactly four 1s must be added on the right.

Step 2 — Key observation.

This is a counting/pairing problem — the kind CFGs handle through recursion.

Base case (n = 1): the shortest string is 0 followed by 1111.
Recursive case: to go from n to n+1, wrap the current string with one extra 0 on the left and four extra 1s on the right.

This recursive "wrap" structure maps directly to a CFG production.

Step 3 — Write the grammar.

Example

S → 0 1 1 1 1 (1) base case: n = 1

| 0 S 1 1 1 1 (2) recursive case: add one 0 and four 1s

That is all. No helper non-terminal is needed.

Step 4 — Explain each production.

Production	Meaning
S → 0 1111	Base case — generates the shortest string in L (n = 1)
S → 0 S 1111	Recursive case — wraps the current S with one more 0 on the left and four more 1s on the right, incrementing n by 1 each time

Step 5 — Derivation examples.

Example 1 — Derive "01111" (n = 1):

Example

S → 0 1 1 1 1 (rule 1)

= 01111 ✓

Example 2 — Derive "0011111111" (n = 2):

Example

S → 0 S 1 1 1 1 (rule 2)

→ 0 (0 1 1 1 1) 1 1 1 1 (rule 1 applied to inner S)

= 00 11111111 ✓

2 zeros, 8 ones = 4 × 2. ✓

Example 3 — Derive "000111111111111" (n = 3):

Example

S → 0 S 1111 (rule 2)

→ 0 (0 S 1111) 1111 (rule 2 again)

→ 0 (0 (0 1111) 1111) 1111 (rule 1)

= 000 111111111111 ✓

3 zeros, 12 ones = 4 × 3. ✓

Step 6 — Verify correctness.

Claim: S derives exactly 0ⁿ 1⁴ⁿ for all n ≥ 1.

Rule 1 gives 0¹ 1⁴ = 0¹ 1⁴·¹. ✓
Rule 2 takes any derivation of 0ⁿ 1⁴ⁿ and produces 0 · 0ⁿ · 1⁴ⁿ · 1⁴ = 0ⁿ⁺¹ 1⁴⁽ⁿ⁺¹⁾. ✓

By induction, every n ≥ 1 is reachable. And the grammar can only produce strings of this exact form — no other shapes are derivable.

Final Grammar (clean form):

Example

G = ( {S}, {0, 1}, P, S )

S → 0 1111 | 0 S 1111

L(G) = { 0ⁿ 1⁴ⁿ | n ≥ 1 }

CFGs in the Compiler Pipeline

In practice, CFGs are the foundation of the syntax analysis (parsing) phase of every compiler.

Example

Source code text

↓ Lexer (uses Regular Grammar / DFA)

Token stream: id + id * id

↓ Parser (uses Context-Free Grammar / PDA)

Parse tree (Abstract Syntax Tree)

↓ Semantic Analysis

Annotated AST

The parser reads the token stream and checks whether it matches the CFG. If it does, the parser builds a parse tree (or abstract syntax tree) that represents the program's structure. This tree is passed to the next phases.

Two main parser families are used in practice:

Parser Family	Grammar Class	Example Tools
LL(k) — Top-Down	LL grammars (subset of CFG)	ANTLR, recursive descent
LR(k) — Bottom-Up	LR grammars (larger subset of CFG)	yacc, bison, LALR parsers

Both families work on CFGs and produce a parse tree in O(n) time for most practical grammars.

Grammars and Expressions

Context-Free Grammars

The workhorse of programming language design — context-free grammars let you describe nested, recursive structures like expressions and blocks with simple, elegant rules.

Why Do We Need Context-Free Grammars?

Consider:

Balanced parentheses: (), (()), ((())) — regular grammars cannot express this
Matching if…end blocks — same problem
Nested arithmetic: (a + (b * c)) — same problem

Regular grammars have no memory of what they have seen. They can't "remember" that they opened a parenthesis and need to close it later.

Context-free grammars (CFGs) solve this. A CFG can handle any recursively nested structure, which is exactly what programming languages are built from.

Example

Regular grammar can describe: Context-free grammar can also describe:

a, ab, abc, ... (a), ((a)), (((a))), ...

a*, aab*, aabb*, ... aⁿbⁿ, i.e., ab, aabb, aaabbb, ...

keywords, identifiers if-else blocks, while loops, expressions

Formal Definition

A context-free grammar (CFG) is a grammar G = (V, T, P, S) where every production rule has the form:

Example

A → α

where:

A is a single non-terminal (just one, on the left)
α is any string of terminals and non-terminals (or ε), on the right

That's it. The only rule: the left-hand side must be a single non-terminal. There is no surrounding context required — A can always be replaced by α regardless of what is around it.

This is what makes a grammar "context-free": the replacement of A does not depend on the context (the symbols surrounding A).

Contrast with Other Grammar Types

Grammar Type	Production Form	Power
Regular (Type 3)	A → aB or A → a	Least — no nested structures
Context-Free (Type 2)	A → α (any string)	Medium — nested structures ✓
Context-Sensitive (Type 1)	αAβ → αγβ	More — depends on context
Unrestricted (Type 0)	α → β (anything)	Most — Turing complete

The Key Insight

In a context-sensitive grammar, the rule αAβ → αγβ says:

"A can be replaced by γ, but only when it has α on its left and β on its right."

In a context-free grammar, the rule A → α says:

"A can be replaced by α, always, no matter what surrounds it."

Context-free is a special case of context-sensitive where α = β = ε (empty context).

Building CFGs — Three Core Examples

Example 1 — Balanced Parentheses

Language: L = { all strings of balanced parentheses } = { ε, (), (()), ()(), ((())), ()(()), … }

Grammar:

Example

G: S → (S) | SS | ε

Reading the rules:

S → (S) — wrap whatever S generates in one pair of parentheses
S → SS — concatenate two balanced sequences side by side
S → ε — the empty string is valid (zero pairs)

Derivation of "(())()":

Example

→ SS (S → SS)

→ (S)S (first S → (S))

→ ((S))S (inner S → (S))

→ (())S (innermost S → ε)

→ (())(S) (remaining S → (S))

→ (())() (S → ε)

Example 2 — The Language aⁿbⁿ

Language: L = { aⁿbⁿ | n ≥ 1 } = { ab, aabb, aaabbb, … }

Grammar:

Example

G: S → aSb | ab

S → ab — the base case: one a followed by one b
S → aSb — wrap the current S with one more a on the left and one more b on the right

Derivation of "aaabbb":

Example

→ aSb (S → aSb)

→ aaSbb (S → aSb)

→ aaabbb (S → ab)

No regular grammar can generate this language — CFGs are more powerful.

Example 3 — Arithmetic Expressions

Language: Arithmetic expressions with +, *, parentheses, and identifiers.

Grammar:

Example

E → E + T | T

T → T * F | F

F → ( E ) | id

This grammar captures operator precedence and associativity:

* binds tighter than + because T is nested inside E
Both + and * are left-associative because E → E + T and T → T * F recurse on the left

Derivation of "id + id * id":

Example

→ E + T

→ T + T

→ F + T

→ id + T

→ id + T * F

→ id + F * F

→ id + id * F

→ id + id * id

The multiplication is in a deeper subtree (T level), so it has higher precedence than addition (E level). This is the same structure used in real compiler front ends.

What CFGs Can Do That Regular Grammars Cannot

The key difference is nesting and counting. A CFG has unlimited "memory" through recursion in non-terminals. A regular grammar has no such memory — once a symbol is consumed it's gone.

Task	Regular Grammar	CFG
Match "aaaa…" (any number of a's)	✓ S → aS	ε
Match aⁿbⁿ (equal a's and b's)	✗ impossible	✓ S → aSb
Match balanced parentheses	✗ impossible	✓ S → (S)
Match nested if-else	✗ impossible	✓ Stmt → if E then Stmt
Describe token patterns (identifiers, numbers)	✓	✓ (but overkill)

Why Programming Languages Use CFGs

Almost every mainstream programming language (C, Java, Python, Go…) is defined using a CFG in a Backus-Naur Form (BNF) or extended BNF. For example, a simplified BNF for an if-statement:

Example

Stmt → if Expr then Stmt

| if Expr then Stmt else Stmt

| while Expr do Stmt

| { StmtList }

| id = Expr ;

Expr → Expr + Term | Expr - Term | Term

Term → Term * Factor | Term / Factor | Factor

Factor → ( Expr ) | id | num

This grammar precisely defines what is and is not a valid statement in the language. The parser (phase 2 of a compiler) uses this grammar to check and understand the program's structure.

One Important Limitation

CFGs cannot express context-dependent constraints like:

"A variable must be declared before it is used"
"A function call must have the same number of arguments as its definition"

These rules are handled by semantic analysis (phase 3), not by the CFG. This is intentional — keeping the grammar context-free makes parsing fast and predictable.

Practice Questions

Question 1 — Construct a CFG for the language of all Non-Palindromes.

Given: Σ = {a, b}. Construct a context-free grammar G such that L(G) is the set of all strings over Σ that are not palindromes.

Answer:

Step 1 — Understand the language.

A string w is a palindrome if w = reverse(w), e.g. ε, a, b, aa, aba, abba, …

A string w is a non-palindrome if w ≠ reverse(w), e.g. ab, ba, aab, abb, aabb, abab, …

Step 2 — Key observation (how a non-palindrome arises).

A string w is a non-palindrome if and only if one of the following holds:

The outermost characters differ — w starts with a and ends with b, or starts with b and ends with a.
The outermost characters are the same, but the inner string is a non-palindrome — w = a·w'·a where w' is a non-palindrome, or w = b·w'·b where w' is a non-palindrome.

This gives a clean recursive structure that a CFG can express directly.

Step 3 — Write the grammar.

Let S generate all non-palindromes, and A generate any string over {a, b}* (including ε).

Example

S → a A b (1)

| b A a (2)

| a S a (3)

| b S b (4)

A → ε (5)

| a A (6)

| b A (7)

Step 4 — Explain each production.

Production	Meaning
S → aAb	w starts with a and ends with b — outermost chars differ, so w is guaranteed a non-palindrome regardless of the middle
S → bAa	w starts with b and ends with a — same reasoning, outer mismatch
S → aSa	Outermost chars are both a (no outer mismatch), but the inner string S is a non-palindrome — so the whole string is also a non-palindrome
S → bSb	Same as above with b on both ends
A → ε	aA

Step 5 — Derivation examples.

Example 1 — Derive "ab" (a non-palindrome):

Example

S → a A b (rule 1)

→ a ε b (rule 5: A → ε)

= ab ✓

"ab" reversed is "ba" ≠ "ab", so it is indeed a non-palindrome.

Example 2 — Derive "aab" (a non-palindrome):

Example

S → a A b (rule 1)

→ a a A b (rule 6: A → aA)

→ a a ε b (rule 5: A → ε)

= aab ✓

"aab" reversed is "baa" ≠ "aab". ✓

Example 3 — Derive "aaba" (a non-palindrome):

Example

S → a S a (rule 3)

→ a (a A b) a (rule 1 applied to inner S)

→ a (a ε b) a (rule 5: A → ε)

= aaba ✓

"aaba" reversed is "abaa" ≠ "aaba". ✓

Step 6 — Verify the grammar does NOT generate palindromes.

Consider "abba" (a palindrome). Try all rules:

S → aAb: w must end in b. "abba" ends in a. ✗
S → bAa: w must start with b. "abba" starts with a. ✗
S → aSa: strip outer a's → inner string is "bb". Is "bb" a non-palindrome? No — "bb" is a palindrome. S cannot generate "bb". ✗
S → bSb: w must start with b. "abba" starts with a. ✗

"abba" cannot be derived. ✓

Final Grammar (clean form):

Example

G = ( {S, A}, {a, b}, P, S )

S → aAb | bAa | aSa | bSb

A → ε | aA | bA

L(G) = { w ∈ {a,b} | w is not a palindrome }*

Question 2 — Construct a CFG for the language L = { 0ⁿ 1⁴ⁿ | n ≥ 1 }.

Given: Σ = {0, 1}. Construct a context-free grammar G such that L(G) = { 0ⁿ 1⁴ⁿ | n ≥ 1 }, i.e., strings of n zeros followed by exactly 4n ones.

Examples: 01111, 0011111111, 000111111111111, …

Answer:

Step 1 — Understand the language.

n	String	Pattern
1	0 1111	1 zero, 4 ones
2	00 11111111	2 zeros, 8 ones
3	000 111111111111	3 zeros, 12 ones

The rule is: every time one 0 is added on the left, exactly four 1s must be added on the right.

Step 2 — Key observation.

This is a counting/pairing problem — the kind CFGs handle through recursion.

Base case (n = 1): the shortest string is 0 followed by 1111.
Recursive case: to go from n to n+1, wrap the current string with one extra 0 on the left and four extra 1s on the right.

This recursive "wrap" structure maps directly to a CFG production.

Step 3 — Write the grammar.

Example

S → 0 1 1 1 1 (1) base case: n = 1

| 0 S 1 1 1 1 (2) recursive case: add one 0 and four 1s

That is all. No helper non-terminal is needed.

Step 4 — Explain each production.

Production	Meaning
S → 0 1111	Base case — generates the shortest string in L (n = 1)
S → 0 S 1111	Recursive case — wraps the current S with one more 0 on the left and four more 1s on the right, incrementing n by 1 each time

Step 5 — Derivation examples.

Example 1 — Derive "01111" (n = 1):

Example

S → 0 1 1 1 1 (rule 1)

= 01111 ✓

Example 2 — Derive "0011111111" (n = 2):

Example

S → 0 S 1 1 1 1 (rule 2)

→ 0 (0 1 1 1 1) 1 1 1 1 (rule 1 applied to inner S)

= 00 11111111 ✓

2 zeros, 8 ones = 4 × 2. ✓

Example 3 — Derive "000111111111111" (n = 3):

Example

S → 0 S 1111 (rule 2)

→ 0 (0 S 1111) 1111 (rule 2 again)

→ 0 (0 (0 1111) 1111) 1111 (rule 1)

= 000 111111111111 ✓

3 zeros, 12 ones = 4 × 3. ✓

Step 6 — Verify correctness.

Claim: S derives exactly 0ⁿ 1⁴ⁿ for all n ≥ 1.

Rule 1 gives 0¹ 1⁴ = 0¹ 1⁴·¹. ✓
Rule 2 takes any derivation of 0ⁿ 1⁴ⁿ and produces 0 · 0ⁿ · 1⁴ⁿ · 1⁴ = 0ⁿ⁺¹ 1⁴⁽ⁿ⁺¹⁾. ✓

By induction, every n ≥ 1 is reachable. And the grammar can only produce strings of this exact form — no other shapes are derivable.

Final Grammar (clean form):

Example

G = ( {S}, {0, 1}, P, S )

S → 0 1111 | 0 S 1111

L(G) = { 0ⁿ 1⁴ⁿ | n ≥ 1 }

CFGs in the Compiler Pipeline

In practice, CFGs are the foundation of the syntax analysis (parsing) phase of every compiler.

Example

Source code text

↓ Lexer (uses Regular Grammar / DFA)

Token stream: id + id * id

↓ Parser (uses Context-Free Grammar / PDA)

Parse tree (Abstract Syntax Tree)

↓ Semantic Analysis

Annotated AST

Two main parser families are used in practice:

Parser Family	Grammar Class	Example Tools
LL(k) — Top-Down	LL grammars (subset of CFG)	ANTLR, recursive descent
LR(k) — Bottom-Up	LR grammars (larger subset of CFG)	yacc, bison, LALR parsers

Both families work on CFGs and produce a parse tree in O(n) time for most practical grammars.