Ambiguity in grammars

Why it exists

A grammar is supposed to give each string a meaning, through its parse tree. If one string has two trees it has two meanings, and a compiler would not know which to use. GATE asks: is this grammar ambiguous, find two parse trees, count the parse trees, remove the ambiguity, which languages are inherently ambiguous. The compiler side of ambiguity (dangling else, operator precedence) is on grammar ambiguity in compilers; this page is the theory.

Prerequisites

You need grammars, derivations and parse trees (context-free grammars).

Precise definitions

A CFG $G$ is ambiguous if some string $w \in L(G)$ has two different parse trees. These conditions are equivalent:

• $w$ has two different parse trees;
• $w$ has two different leftmost derivations;
• $w$ has two different rightmost derivations.

(Two different derivations are not enough, since different orders of expansion give different derivations of the same tree.) A grammar that is not ambiguous is unambiguous.

A language is inherently ambiguous if every grammar for it is ambiguous. Ambiguity belongs to grammars; inherent ambiguity belongs to languages.

If a grammar has a variable $A$ with $A \Rightarrow^+ A$ (a cycle of unit productions or of nullable symbols around $A$) that is used in the derivation of some string, that string has infinitely many parse trees, so the grammar is ambiguous.

How it works

Finding and counting parse trees

For a string $w = w_1 \cdots w_n$, let $c(A, i, j)$ be the number of parse trees with root $A$ and yield $w_i \cdots w_j$. Then $c$ is computed from shorter substrings: for each production $A \to X_1 \cdots X_k$ sum, over all ways to split the substring into $k$ consecutive parts, the product of the counts for the parts (a terminal contributes $1$ if it equals the symbol). The number of parse trees of $w$ is $c(S, 1, n)$. This is the same table as in the CYK algorithm, with counts instead of yes/no.

Example: $S \to S S \mid a$.

The string $aaa$ has two parse trees: $(aa)a$ and $a(aa)$, found as two different leftmost derivations.

The Catalan explosion

For a binary operator without precedence rules, each string $\mathrm{id} + \mathrm{id} + \cdots$ with $n$ operators has one tree for each way to bracket it, and that number is the Catalan number $C_n = \frac{1}{n + 1} \binom{2n}{n}$: $1, 1, 2, 5, 14, 42, 132, 429$. The layered grammar $E \to E + T \mid T$, $T \to \mathrm{id}$ (left associative) has exactly one tree.

(The first column is $E \to E + E \mid \mathrm{id}$, the second the layered grammar, the third $E \to E + E \mid E * E \mid \mathrm{id}$ on a string whose operators alternate $+$ and $*$: with no precedence there are again $C_n$ trees.)

Removing ambiguity

1. Precedence by layering. Give each precedence level its own variable: $E \to E + T \mid T$, $T \to T * F \mid F$, $F \to (E) \mid \mathrm{id}$. Operators lower in the layers bind tighter.
2. Associativity by the shape of the recursion. $E \to E + T$ (recursion on the left) makes $+$ left associative; $E \to T + E$ makes it right associative.
3. Dangling else: match each else with the nearest unmatched then by separating matched and unmatched statements (see the compiler page).

Unambiguous grammars (checked: at most one parse tree for every string up to length $10$):

Here $A$ generates the strings with exactly one more $a$ than $b$ and in which no proper prefix has that property, $B$ the mirror image.

Typical ambiguous grammars: $S \to aS \mid Sa \mid a$ (the string $a^n$ has $2^{n-1}$ trees), $S \to aSb \mid aS \mid \varepsilon$ for $i \ge j$, the equal-count grammar $S \to aSbS \mid bSaS \mid \varepsilon$ ($abab$ has two trees), and anything with $S \to SS$ together with other ways to make the same string.

Cyclic grammars

For $S \to SS \mid (S) \mid \varepsilon$ the derivation $S \Rightarrow SS \Rightarrow S \Rightarrow SS \Rightarrow \cdots$ can be inserted any number of times (using $S \to \varepsilon$ for one of the $S$'s): every string, even $\varepsilon$, has infinitely many parse trees. The same holds for $S \to S \mid a$ (a unit cycle) and for $S \to aSb \mid SS \mid \varepsilon$. A computation that counts trees reports "infinitely many".

Inherent ambiguity

The language $L = \{a^i b^j c^k : i = j \text{ or } j = k\}$ has the natural grammar $S \to XC \mid AY$ with $X \to aXb \mid \varepsilon$, $C \to cC \mid \varepsilon$, $A \to aA \mid \varepsilon$, $Y \to bYc \mid \varepsilon$. It is ambiguous exactly on the strings with $i = j = k$: those can be generated by the left part and by the right part. It is a textbook theorem (quoted, not proved here) that every grammar for $L$ is ambiguous, so $L$ is inherently ambiguous.

Deciding ambiguity

There is no algorithm that decides whether an arbitrary grammar is ambiguous (the problem is undecidable; textbook theorem, quoted). One can only test strings up to a bound, as the tables here do, or prove unambiguity for special classes: every LL(1) and every LR(k) grammar is unambiguous (textbook fact, quoted; LL(1) parsing).

Worked examples

Cheat box

Traps and GATE patterns

Connections

Compilers need unambiguous grammars (or precedence declarations) to give a program one meaning (ambiguity in compilers); every deterministic context-free language has an unambiguous grammar (textbook theorem, quoted; deterministic versus nondeterministic PDA); the grammar-to-PDA construction keeps the derivation structure (PDA and CFG).

PYQs

Consider the following grammar where S is the start
symbol, and a and b are
terminal symbols.
S→aSbS | bS | ε
Which of the following statements is/are true?

Which of the following grammars is/are ambiguous?

Self-check

Revision card

References