Context-Free Grammars

Definition

A context-free grammar (CFG) is a 4-tuple $G = (V, \Sigma, R, S)$ where:

• $V$ = finite set of variables (non-terminals)
• $\Sigma$ = finite set of terminals (disjoint from $V$)
• $R$ = finite set of production rules of form $A \to \alpha$
  • $A \in V$ (single variable on left)
  • $\alpha \in (V \cup \Sigma)^*$ (string of variables and terminals)
• $S \in V$ = start symbol

Example Grammar

Grammar for balanced parentheses: $S \to (S) \mid SS \mid \epsilon$

Notation Conventions

• Capital letters: variables ($S, A, B$)
• Lowercase letters: terminals ($a, b, c$)
• $\epsilon$: empty string
• $\mid$: separates alternatives

Derivations

A derivation shows how to generate a string from the start symbol.

One-Step Derivation ($\Rightarrow$)

$\alpha A \beta \Rightarrow \alpha \gamma \beta$ if $A \to \gamma$ is a rule.

Multi-Step Derivation ($\Rightarrow^*$)

Zero or more derivation steps.

Example

Grammar: $S \to aSb \mid \epsilon$

Derivation of "aabb": $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$

Language of a Grammar

$L(G) = \{w \in \Sigma^* \mid S \Rightarrow^* w\}$

All terminal strings derivable from the start symbol.

Context-Free Languages

A language is context-free if some CFG generates it.

Examples

Language	Grammar
$\{a^n b^n\}$	$S \to aSb \mid \epsilon$
Balanced parentheses	$S \to (S) \mid SS \mid \epsilon$
Palindromes	$S \to aSa \mid bSb \mid a \mid b \mid \epsilon$
$\{a^n b^m c^m d^n\}$	$S \to aSd \mid B$, $B \to bBc \mid \epsilon$

Parse Trees

A parse tree visualizes a derivation:

• Root = start symbol
• Internal nodes = variables
• Leaves = terminals (or $\epsilon$)
• Children of node $A$ match right side of some rule $A \to ...$

Yield

Reading leaves left-to-right gives the derived string.

Leftmost and Rightmost Derivations

Leftmost derivation: Always expand the leftmost variable.

Rightmost derivation: Always expand the rightmost variable.

Every parse tree corresponds to exactly one leftmost and one rightmost derivation.

Ambiguity

A grammar is ambiguous if some string has two or more parse trees.

Example: Ambiguous Grammar

$E \to E + E \mid E \times E \mid (E) \mid a$

String "$a + a \times a$" has two parse trees:

• $(a + a) \times a$ (add first)
• $a + (a \times a)$ (multiply first)

Resolving Ambiguity

Rewrite grammar to enforce precedence/associativity: $E \to E + T \mid T$ $T \to T \times F \mid F$ $F \to (E) \mid a$

Inherently Ambiguous Languages

Some CFLs have no unambiguous grammar.

Example: $\{a^i b^j c^k \mid i = j \text{ or } j = k\}$

Chomsky Normal Form (CNF)

Every rule has form:

• $A \to BC$ (two variables), or
• $A \to a$ (single terminal)

(Start symbol may have $S \to \epsilon$)

Conversion to CNF

1. Eliminate $\epsilon$-rules (except from start)
2. Eliminate unit rules ($A \to B$)
3. Replace terminals in long rules with variables
4. Break long rules into binary rules

Importance

• Simplifies parsing algorithms (CYK)
• Guarantees $O(n^3)$ parsing

Greibach Normal Form (GNF)

Every rule has form: $A \to a\alpha$

where $a$ is a terminal and $\alpha$ is a (possibly empty) string of variables.

Pumping Lemma for CFLs

If $L$ is context-free, there exists $p$ such that:

For any $w \in L$ with $|w| \geq p$, we can write $w = uvxyz$ where:

1. $|vxy| \leq p$
2. $|vy| \geq 1$
3. For all $i \geq 0$: $uv^i xy^i z \in L$

Example: $\{a^n b^n c^n\}$ is not context-free

Choose $w = a^p b^p c^p$. Any pumping produces imbalance. $\square$

Closure Properties

Operation	CFLs Closed?
Union	Yes
Concatenation	Yes
Kleene star	Yes
Intersection	No
Complement	No
Intersection with regular	Yes

Parsing Algorithms

Algorithm	Time	Notes
CYK	$O(n^3)$	Any CFG in CNF
Earley	$O(n^3)$	Any CFG
LL(k)	$O(n)$	Restricted grammars
LR(k)	$O(n)$	Most programming languages

Applications

Programming Languages

• Syntax defined by CFGs
• Parsed by compiler front-end

Natural Language Processing

• Sentence structure analysis
• Machine translation

Markup Languages

• HTML, XML structure
• JSON format