Context-Free Grammars, Derivations and Ambiguity: short notes (Theory of Computation)

Introduction

A context-free grammar (CFG) generates a language by rewriting nonterminals one at a time, independently of surrounding context. The languages of CFGs are the context-free languages (CFLs), recognized by pushdown automata. CFGs are the backbone of programming-language syntax and of GATE questions on derivations, parse trees and ambiguity.

Prerequisites

Alphabets, Strings and Languages: terminals as alphabet symbols; strings and languages.

Core concepts

Formal definition

A CFG is $G = (V, \Sigma, R, S)$ where $V$ is a finite set of variables (nonterminals), $\Sigma$ is the terminal alphabet ( $V \cap \Sigma = \emptyset$ ), $S \in V$ is the start symbol, and $R$ is a finite set of productions $A \to \alpha$ with $A \in V$ and $\alpha \in (V \cup \Sigma)^*$ .

A derivation step replaces one occurrence of a variable by a production's right-hand side. Write $\Rightarrow$ for one step, $\Rightarrow^*$ for zero or more. The language is

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

Leftmost and rightmost derivations

A leftmost derivation always rewrites the leftmost variable of the current sentential form; rightmost rewrites the rightmost. Every parse tree corresponds to exactly one leftmost and one rightmost derivation.

Parse trees

A parse tree has root $S$ , internal nodes labelled by variables, children ordered as a production's right-hand side, and leaves that concatenate to the derived terminal string (the yield).

Ambiguity

A grammar is ambiguous if some string has two different parse trees (equivalently, two different leftmost derivations, or two different rightmost derivations). A language is inherently ambiguous if every CFG for it is ambiguous. The classic example is $\{a^n b^n c^m \mid n, m \ge 0\} \cup \{a^n b^m c^m \mid n, m \ge 0\}$ : strings $a^n b^n c^n$ lie in both parts, and every grammar for the language is ambiguous. That is a known result proved with Ogden's lemma (sketch in Example 4); finding two trees in one grammar does not prove it. Ambiguity is a property of a grammar; inherent ambiguity is a property of a language.

Facts to know.

Deciding whether an arbitrary CFG is ambiguous is undecidable. There is no general algorithm, so ambiguity is shown by exhibiting a second tree for one specific string.
Every regular language and every DCFL has an unambiguous grammar. So an inherently ambiguous language is never a DCFL.
Two different derivations do not mean ambiguity: a leftmost and a rightmost derivation of the same tree are different derivations. Only two different trees (or two leftmost derivations) count.

Ambiguity versus nondeterminism. Ambiguity is about multiple trees for one string. Nondeterministic PDAs may still define unambiguous languages.

How it works

Designing CFGs

Matching counts. $S \to aSb \mid \varepsilon$ for $\{a^n b^n\}$ .
Union. New start $S \to S_1 \mid S_2$ .
Concatenation. $S \to S_1 S_2$ .
Star. $S \to S_1 S \mid \varepsilon$ .
Expressions. $E \to E+T \mid T$ , $T \to T*F \mid F$ , $F \to (E) \mid a$ yields a standard unambiguous arithmetic grammar.

Algorithms and pseudocode

Membership for general CFGs is decidable (CYK after Chomsky normal form; see later notes). For small exam grammars, try to derive the string by hand or build a parse tree.

Text

LEFTMOST-DERIVE(G, target)
1  sentential <- G.S
2  while sentential has a variable
3      A <- leftmost variable
4      choose production A -> alpha   // nondeterministic search
5      replace that A by alpha
6      if sentential is all terminals: return sentential == target

Mathematical explanation

Leftmost derivations and trees

Theorem: a string has two distinct leftmost derivations iff it has two distinct parse trees. Proof idea: a tree determines a unique leftmost expansion order; different trees disagree at the first production choice on the leftmost variable path.

Catalan numbers and $S \to S+S \mid a$

The number of leftmost derivations of $a+a+\cdots+a$ ( $n$ summands, $n-1$ plus signs) in the ambiguous grammar $S \to S+S \mid a$ is the Catalan number $C_{n-1}$ . So $n=3$ gives $C_2=2$ , $n=4$ gives $C_3=5$ .

Worked examples

Example 1: $\{a^n b^n\}$

Grammar $S \to aSb \mid \varepsilon$ . Leftmost derivation of $aabb$ : $S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb$ .

Example 2: ambiguous plus grammar

$S \to S+S \mid a$ . Two leftmost derivations of $a+a+a$ :

$S \Rightarrow S+S \Rightarrow a+S \Rightarrow a+S+S \Rightarrow a+a+S \Rightarrow a+a+a$
$S \Rightarrow S+S \Rightarrow S+S+S \Rightarrow a+S+S \Rightarrow a+a+S \Rightarrow a+a+a$ , where the second step rewrites the first $S$ as $S+S$ , giving the tree $(a+a)+a$ .

The first derivation expands the second $S$ at step 3 and builds $a+(a+a)$ . The two derivations differ at the first choice point, so the trees differ.

Two parse trees; Catalan $C_2=2$ .

Two parse trees for a+a+a in the ambiguous plus grammar — Figure 1. Two distinct parse trees for the string a+a+a under $S \to S+S \mid a$ : left-associated and right-associated sums.

Example 3: balanced parentheses

$S \to (S)S \mid \varepsilon$ . Generates exactly the balanced strings (Dyck words). It is unambiguous: the first symbol ( must match a unique ), which fixes the split. By contrast $S \to SS \mid (S) \mid \varepsilon$ generates the same language ambiguously (()()() splits by $S \to SS$ as $S_1 S_2$ with $S_1 =$ ()() and $S_2 =$ (), or with $S_1 =$ () and $S_2 =$ ()(); and $\varepsilon$ can be inserted anywhere, giving infinitely many trees).

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

$S \to AC \mid BD$ , $A \to aAb \mid \varepsilon$ , $C \to cC \mid \varepsilon$ , $B \to aB \mid \varepsilon$ , $D \to bDc \mid \varepsilon$ . The $AC$ branch generates $a^n b^n c^m$ and the $BD$ branch generates $a^m b^n c^n$ . The language is a CFL that is not a deterministic CFL (treated in the DPDA note).

This grammar is ambiguous. abc has one tree through $AC$ ( $A \Rightarrow ab$ , $C \Rightarrow c$ ) and one through $BD$ ( $B \Rightarrow a$ , $D \Rightarrow bc$ ). A string has two trees in this grammar exactly when $i = j = k$ . Two trees in one grammar prove only that this grammar is ambiguous; they say nothing about other grammars for the same language.

The language is inherently ambiguous. This is a known result: every CFG for the language is ambiguous. The standard proof uses Ogden's lemma, a stronger pumping lemma in which only marked positions count. By contrast, the balanced-parentheses language in Example 3 has both an ambiguous grammar and an unambiguous grammar.

Related material. A proof sketch, not a full proof. Let $G$ be any CFG for the language, let $p$ be its Ogden constant, and let $N = p!$ .

Take $z = a^N b^N c^{2N}$ and mark the $a$ 's. Ogden's lemma splits $z = uvwxy$ with at least one marked symbol in $vx$ , at most $p$ marked symbols in $vwx$ , and $uv^m w x^m y$ in the language for every $m \ge 0$ . Every split except $v = a^s$ , $x = b^s$ with $1 \le s \le p$ leaves the language for some $m$ : pumping breaks the order $a^* b^* c^*$ , or makes $i \ne j$ while $j \ne k$ .
Since $s$ divides $N$ , pumping with $m = N/s + 1$ gives $a^{2N} b^{2N} c^{2N}$ . The pumped tree has a node whose subtree yields $v^m w x^m$ : no $c$ , and more than $N$ $b$ 's.
Symmetrically, starting from $a^{2N} b^N c^N$ with the $c$ 's marked gives a tree for the same string $a^{2N} b^{2N} c^{2N}$ with a node whose subtree yields no $a$ and more than $N$ $b$ 's.
Two subtrees of one tree are nested or disjoint. These two cannot be nested (one yield has an $a$ and no $c$ , the other a $c$ and no $a$ ), and two disjoint yields would hold more than $2N$ $b$ 's. So the two trees differ, and $G$ is ambiguous.

Step 1 compresses a longer case analysis; the sketch shows the structure of the argument only.

Example 5: counting parse trees in three grammars

Grammar	String	Parse trees	Pattern
$S \to SS \mid a$	$a^n$	1, 1, 2, 5, 14, 42 for $n = 1..6$	Catalan $C_{n-1}$
$S \to aS \mid Sa \mid a$	$a^n$	1, 2, 4, 8, 16 for $n = 1..5$	$2^{n-1}$ : each step adds the next $a$ on the left or the right
$S \to S+S \mid S*S \mid a$	`a+a*a`	2	$(a+a)a$ and $a+(aa)$

The layered grammar $E \to E+T \mid T$ , $T \to T*F \mid F$ , $F \to (E) \mid a$ gives a+a*a exactly one tree, with $*$ below $+$ . Precedence comes from the layer (lower layer binds tighter) and left associativity from left recursion ( $E \to E+T$ , not $E \to T+E$ ).

Example 6: the dangling else

$S \to iCtS \mid iCtSeS \mid a$ , $C \to b$ ( $i$ = if, $t$ = then, $e$ = else). The string ibtibtaea has 2 trees: the e attaches to the inner if or to the outer one. Programming languages resolve it by the rule "else matches the nearest unmatched then", which an unambiguous grammar can encode with separate "matched" and "unmatched" statement variables.

Example 7: grammars for common languages

Language	Grammar
palindromes over $\{a,b\}$	$S \to aSa \mid bSb \mid a \mid b \mid \varepsilon$
$\{a^n b^{2n} \mid n \ge 0\}$	$S \to aSbb \mid \varepsilon$
$\{a^i b^j \mid i \ne j\}$	$S \to aSb \mid A \mid B$ , $A \to aA \mid a$ , $B \to bB \mid b$
$\{a^i b^j c^k \mid j = i + k\}$	$S \to AB$ , $A \to aAb \mid \varepsilon$ , $B \to bBc \mid \varepsilon$
$\{w \mid \#_a(w) = \#_b(w)\}$	$S \to aSbS \mid bSaS \mid \varepsilon$
$\{a^i b^j \mid i \le j \le 2i\}$	$S \to aSb \mid aSbb \mid \varepsilon$

The third row shows the standard trick for " $\ne$ ": generate equal counts, then force a nonempty surplus on one side. The fifth row generates the language because every nonempty string with equal counts splits at the first point where the counts balance. The grammar is still ambiguous: abab has the two trees $a\,[\varepsilon]\,b\,[ab]$ and $a\,[ba]\,b\,[\varepsilon]$ .

Important properties and observations

Every regular language is context-free (right-linear grammars).
CFLs are not closed under intersection or complement (see properties note).
Useless symbols, $\varepsilon$ -productions and unit productions can be eliminated (next note).
Left recursion is allowed in CFGs but problematic for top-down parsers (Compiler Design).

Common misconceptions.

"One parse tree (equivalently one leftmost derivation) per generated string" holds only for unambiguous grammars; arbitrary derivation orders need not be unique.
"Ambiguous language" when only the grammar is ambiguous; the language may still have an unambiguous CFG.
Confusing terminals and variables in productions.

GATE examination perspective

DRAW THE TREE. Match leaves to the string; check every parent against a production.
LEFTMOST VS RIGHTMOST. For the next leftmost step, rewrite only the leftmost variable.
COUNT PARSE TREES. Catalan for the pure plus grammar; otherwise enumerate carefully.
DESIGN MATCHING COUNTERS. One stack-worth of memory: one matching pair of counts, not three equal counts. $\{a^n b^n c^n\}$ and $\{a^i b^j c^k \mid i = j = k\}$ have no CFG.
IS THIS GRAMMAR AMBIGUOUS. Look for a production with the same variable twice on the right ( $S \to SS$ , $S \to S+S$ ) or two rules that can produce the same prefix ( $S \to aS \mid Sa$ ); then exhibit one string with two leftmost derivations.
TWO DERIVATIONS ARE NOT TWO TREES. A leftmost and a rightmost derivation of one tree do not show ambiguity.
GRAMMAR VERSUS LANGUAGE. "The language is ambiguous" is meaningful only as inherent ambiguity, which needs a proof about every grammar (Example 4). An ambiguous grammar often has an unambiguous equivalent (Example 5).
UNDECIDABLE. "Is $G$ ambiguous?" has no algorithm; "is $w \in L(G)$ ?" does (CYK).

Summary

Alphabets, Strings and Languages: prerequisite.
CFG Simplification and Normal Forms: dependent.
Pushdown Automata: dependent. Machine model for CFLs.
Grammar Transformations for Parsing: related. Left recursion elimination, left factoring.

Context-Free Grammars, Derivations and Ambiguity

Introduction

Prerequisites

Core concepts

Formal definition

Leftmost and rightmost derivations

Parse trees

Ambiguity

How it works

Designing CFGs

Algorithms and pseudocode

Mathematical explanation

Leftmost derivations and trees

Catalan numbers and $S \to S+S \mid a$

Worked examples

Example 1: $\{a^n b^n\}$

Example 2: ambiguous plus grammar

Example 3: balanced parentheses

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

Example 5: counting parse trees in three grammars

Example 6: the dangling else

Example 7: grammars for common languages

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Formal definition

Leftmost and rightmost derivations

Parse trees

Ambiguity

How it works

Designing CFGs

Algorithms and pseudocode

Mathematical explanation

Leftmost derivations and trees

Catalan numbers and S→S+S∣aS \to S+S \mid aS→S+S∣a

Worked examples

Example 1: {anbn}\{a^n b^n\}{anbn}

Example 2: ambiguous plus grammar

Example 3: balanced parentheses

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

Example 5: counting parse trees in three grammars

Example 6: the dangling else

Example 7: grammars for common languages

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Catalan numbers and $S \to S+S \mid a$

Example 1: $\{a^n b^n\}$

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