Ambiguity in Context-Free Grammars

Let $G = (V, \Sigma, R, S)$ be a context-free grammar generating language $L(G)$. A string $w \in L(G)$ may, in general, be derivable from $S$ in more than one way. To compare derivations meaningfully we fix a canonical order: a leftmost derivation always rewrites the leftmost nonterminal at each step. Two leftmost derivations of the same string $w$ are considered the same derivation if and only if they apply the same sequence of production rules — and this sequence corresponds exactly to a unique parse tree (also called a derivation tree) for $w$.

Equivalently — and this is the more intuitive formulation — $G$ is ambiguous iff some $w \in L(G)$ has two distinct parse trees. Parse trees abstract away the order in which productions are applied (leftmost vs. rightmost vs. some interleaving) and record only the hierarchical grouping of symbols; leftmost derivations give a clean bijection between derivations and trees, which is why the definition is stated in terms of them rather than raw derivation sequences (rightmost derivations give an equally valid, symmetric bijection). It is essential to separate two levels:

• Grammar ambiguity: a property of a specific grammar $G$. Fixable, in principle, by rewriting $G$.
• Inherent ambiguity of a language: a property of $L$ itself, meaning no context-free grammar for $L$ is unambiguous. This is a strictly stronger, structural statement — proved not by exhibiting one bad grammar but by an argument that works against all possible grammars.

A useful sanity check: ambiguity is entirely separate from whether the language is regular, decidable, or "simple looking." $\{a^n b^n : n \ge 0\}$ has an obviously unambiguous grammar ($S \to aSb \mid \varepsilon$); yet a language as similarly small-looking as $\{a^ib^jc^k : i=j \text{ or } j=k\}$ turns out to be inherently ambiguous, because its two "halves" ($i=j$ and $j=k$) genuinely overlap on strings where $i=j=k$, and no single unambiguous grammar can simultaneously derive those strings via only one structural route.

Detecting ambiguity by exhibiting two trees

The operational test for ambiguity of a specific grammar is constructive: find one string with two distinct parse trees. There is no general algorithm that always succeeds (ambiguity is undecidable, discussed below), but for concrete small grammars a direct search over derivations is the standard technique. ``` function FIND_AMBIGUOUS_WITNESS(G, maxLength):

# Breadth-first enumeration of leftmost derivations up to a length bound.

# Returns a string with two distinct parse trees, or "none found" if the

# search bound is exhausted without a witness. frontier = queue containing the single sentential form [S] seen_trees_for_string = empty map from string -> set of parse trees while frontier is not empty: form = frontier.dequeue() if form has no nonterminals: w = the terminal string formed by form if length(w) <= maxLength: T = the parse tree that produced `form` via this derivation if seen_trees_for_string[w] contains a tree structurally different from T: return (w, T, seen_trees_for_string[w]) # witness! else: add T to seen_trees_for_string[w] continue leftmost_nt = the first nonterminal symbol in `form` for each rule (leftmost_nt -> body) in R: new_form = form with leftmost_nt replaced by body if length(terminals so far in new_form) <= maxLength: frontier.enqueue(new_form) return "none found within bound" ``` This is a semi-procedure: if a witness of length $\le$ `maxLength` exists it will eventually be found, but a "none found" result only means no witness exists within the bound — it says nothing about longer strings. That asymmetry is exactly why ambiguity is undecidable in general (there is no bound that works for all grammars).

Disambiguation: rewriting the grammar without changing the language

Once ambiguity is diagnosed, the standard fix is to layer the grammar by precedence and use left- or right-recursion to force associativity, while keeping $L(G)$ identical. The classic arithmetic-expression example:

Ambiguous grammar $G_1$: ``` E → E + E | E * E | ( E ) | id ```

Unambiguous grammar $G_2$ generating the same language, with `` binding tighter than `+`, and both left-associative: ``` E → E + T | T T → T F | F F → ( E ) | id ``` The transformation follows a general recipe: ``` function DISAMBIGUATE_EXPRESSION_GRAMMAR(operators_by_precedence):

# operators_by_precedence: list of operator groups, lowest precedence first

# e.g. [ {"+","-"} , {"*","/"} ] (each group assumed left-associative here) levels = new array of nonterminals L_0, L_1, ..., L_k, F

# L_0 = lowest precedence (loosest binding), L_k = highest, F = atoms for i = 0 to k-1: ops = operators_by_precedence[i] add rule: L_i → L_i op L_{i+1} for each op in ops (left-recursive ⇒ left-assoc) add rule: L_i → L_{i+1} add rule: L_k → L_k op F for each op in operators_by_precedence[k] add rule: L_k → F add rules: F → ( L_0 ) | id return grammar with start symbol L_0 ``` Each precedence level becomes its own nonterminal; a production can only combine operators within its level or hand off to the next tighter level, so the tree shape is forced: `` subtrees are always nested strictly inside `+` subtrees, and left-recursion (`L_i → L_i op L_{i+1}`) forces the leftmost operator of equal precedence to bind first, giving left-associativity. This does not always work — it is not a decision procedure for ambiguity in general — but for the broad class of expression grammars with clean precedence hierarchies it is a reliable, mechanical construction, and it is exactly what hand-written recursive-descent parsers and grammar files fed to `yacc`/`bison` implement. The <strong>dangling-else</strong> ambiguity is handled by the same principle of restricting when* a rule may apply:

Ambiguous: ``` S → if E then S | if E then S else S | other ``` Here `if E1 then if E2 then S1 else S2` has two parses: the `else` attaching to the inner or the outer `if`.

Disambiguated (forcing "match the nearest unmatched `if`," the convention virtually every language adopts): ``` S → matched | unmatched matched → if E then matched else matched | other unmatched → if E then S | if E then matched else unmatched ``` The trick: a `matched` statement is one where every `if` already has its `else`; an `unmatched` statement always has a still-open, outermost `if`. Because `unmatched`'s `else`-branch is required to have a matched `then`-part, the grammar mechanically forces every `else` to bind to the closest preceding unmatched `if` — there is exactly one derivation per string.

Deciding whether a specific string has multiple parse trees in a given grammar $G$ (with $|G|$ = total size of productions) can be done via a modified CYK-style parse: convert $G$ to Chomsky Normal Form (size increase at most a constant factor for a fixed grammar) and run the CYK recognizer while counting, for each cell $(i,j,A)$ of the parse table, the number of distinct ways nonterminal $A$ derives the substring $w_{i..j}$, using arbitrary-precision arithmetic (counts can grow exponentially in string length). If any accepting cell's count exceeds $1$, the string is ambiguous under $G$.

• Time: $O(n^3 \cdot |G|)$ for a string of length $n$, same asymptotic class as ordinary CYK parsing, since we only add a counting step per table cell.
• Space: $O(n^2 \cdot |V|)$ table cells, each holding a count whose bit-length can itself be $O(n)$ in the worst case (the number of parse trees can be exponential, e.g. for the fully ambiguous grammar $E \to E E \mid a$, the count of trees for a string of length $n$ is the Catalan number $C_{n-1} \sim 4^n/n^{3/2}$).

This gives a decision procedure for "is this one string ambiguously derived by this one grammar" — but it is not a decision procedure for "is this grammar ambiguous at all", since that would require checking infinitely many strings.

Theorem (undecidability of ambiguity). There is no algorithm that, given an arbitrary context-free grammar $G$, always correctly decides whether $G$ is ambiguous. Proof sketch. The standard argument reduces from the Post Correspondence Problem (PCP), which is undecidable. Given a PCP instance with dominoes $(x_1,y_1), \ldots, (x_k,y_k)$ over alphabet $\Sigma$, build two grammars:

where $a_1,\dots,a_k$ are fresh marker symbols encoding which sequence of indices was used. $G_x$ generates exactly the strings $x_{i_1}x_{i_2}\cdots x_{i_m}\, a_{i_m}\cdots a_{i_1}$ for every index sequence $i_1,\dots,i_m$, and symmetrically for $G_y$. Combine them with a fresh start symbol into

This combined $G$ is ambiguous exactly when some string is generated by both $A$ and $B$ (via two different rules $S\to A$ and $S \to B$ giving two distinct trees), which happens exactly when some index sequence $i_1,\dots,i_m$ makes $x_{i_1}\cdots x_{i_m} = y_{i_1}\cdots y_{i_m}$ — precisely a solution to the PCP instance. So "$G$ ambiguous" $\iff$ "PCP instance solvable." Since PCP is undecidable, ambiguity of a CFG is undecidable. $\blacksquare$ This is one of the cleanest reductions in the theory: it shows ambiguity-checking inherits undecidability directly from a combinatorial problem about string matching, not from anything exotic about grammars themselves.

Correctness of the disambiguated precedence grammar ($G_2$ above) rests on an invariant provable by structural induction on parse trees: every tree rooted at $T$ (with start `L_0`) has, at every internal node labeled $L_i$, only operators of precedence level $i$ or higher-precedence subtrees nested below, and left-recursive productions force the leftmost same-level operator to be the root of the subtree. Together these two facts imply a unique tree per string: given any valid parse tree for a string in $L(G_2)$, the precedence level of the root operator is forced by which nonterminal can produce it, and among operators of equal precedence the left-recursion forces a unique split point (the rightmost occurrence at that level, working outward), so no two distinct trees can produce the same terminal string. This is the standard justification used when specifying operator-precedence parsing tables (foreshadowing Deterministic Context-Free Languages and Parsing).

Tradeoffs. Disambiguating a grammar preserves the language but can:

• increase the number of nonterminals and productions (more grammar "layers"),
• make the grammar less "natural" to read (the precedence-layered arithmetic grammar is longer than `E → E+E|E*E|...`),
• sometimes be impossible if the language is inherently ambiguous — no amount of rewriting will produce an unambiguous grammar, only a different language "close to" the intended one.

Grammar (dangling-else, ambiguous form): ``` S → if E then S | if E then S else S | other ```

String: `if E1 then if E2 then other else other`

Both derivations legally end in the identical terminal string, so this grammar is ambiguous: two distinct leftmost derivations, hence two distinct parse trees (inner `if`'s `else` vs. outer `if`'s `else`). Now apply the disambiguated grammar: ``` S → matched | unmatched matched → if E then matched else matched | other unmatched → if E then S | if E then matched else unmatched ``` Tracing `if E1 then if E2 then other else other`:

Wait — step 5 needs the `else`, so the correct unique route is:

This can't apply directly at step 2 since that production's left-hand `if` is the outer one — tracking carefully: the only derivation that produces the target string is the one using `unmatched → if E then matched else unmatched` at the outer level is disallowed (outer has no trailing content after the inner block), so the parser is forced to expand the inner `if` with `matched → if E then matched else matched`, giving:

Exactly one leftmost derivation exists (the `else` is forced onto $E_2$'s `if`), confirming the disambiguated grammar generates this string with a unique tree — matching the standard "nearest unmatched `if`" convention.

Every compiler front end for languages like C, Java, and Python must resolve exactly the kinds of ambiguity discussed here — operator precedence tables in `yacc`/`bison`/ANTLR grammar files are a direct, practical encoding of the precedence-layering disambiguation technique. The dangling-`else` rule ("bind to the nearest unmatched `if`") is a language-design convention baked into virtually every C-family language specification, precisely to avoid ambiguity at the grammar level. Query languages (SQL parsers), configuration-file formats, and markup languages (early ambiguous HTML/XML-adjacent grammars) all face the same tension between human-readable grammar and machine-checkable determinism. In natural-language processing, genuine (and often intentional) ambiguity — "I saw the man with the telescope" — is the reason statistical and probabilistic parsers, rather than plain CFGs, are used: they assign probabilities to competing parse trees instead of requiring the grammar to pick just one. Understanding ambiguity is also the conceptual bridge to Deterministic Context-Free Languages and Parsing and to Pushdown Automata-based parsing algorithms (LL, LR), which are only well-defined and efficient on unambiguous — indeed deterministic — grammars.

Ask the tutor: Can you show why $\{a^ib^jc^k : i=j \text{ or } j=k\}$ is provably inherently ambiguous, step by step?