A CONTEXT-FREE GRAMMAR IS AMBIGUOUS IF SOME STRING IN ITS LANGUAGE HAS MORE THAN ONE DERIVATION TREE. EQUIVALENT FORMULATIONS, all standard: · some string has two or more distinct parse trees · some string has two or more distinct LEFTMOST derivations · some string has two or more distinct RIGHTMOST derivations NOTE WHAT AMBIGUITY IS **NOT**: having two different derivations is harmless if they produce the SAME tree, since that reflects only the order in which variables were expanded. AMBIGUITY IS ABOUT STRUCTURE, NOT ABOUT DERIVATION ORDER. WHY IT MATTERS: THE TREE DETERMINES THE MEANING. Two trees for one string means two possible meanings, and a compiler has no principled basis for choosing. A grammar that permits this cannot serve as a language definition. ── EXAMPLE 1: THE EXPRESSION GRAMMAR ─────────────────────── E → E + E | E * E | id The string id + id * id has TWO parse trees: TREE A TREE B E E / | \ / | \ E + E E * E | /|\ /|\ | id E * E E + E id | | | | id id id id = id + (id * id) = (id + id) * id WITH id = 2, 3, 4: TREE A gives 2 + 12 = 14, TREE B gives 5 × 4 = 20. THE SAME STRING, TWO ANSWERS — which is why this is not a theoretical concern. THE SAME GRAMMAR IS ALSO AMBIGUOUS FOR ASSOCIATIVITY: the string id + id + id has two trees, grouping left or right. For + it does not matter numerically; FOR − OR / IT MATTERS ENORMOUSLY, since (8 − 3) − 2 = 3 while 8 − (3 − 2) = 7. THE NUMBER OF TREES GROWS ALARMINGLY. For n operands with this grammar the count is the (n−1)ᵗʰ CATALAN NUMBER: 3 operands → 2 trees 4 operands → 5 trees 5 operands → 14 trees 6 operands → 42 trees AMBIGUITY DOES NOT MERELY PERMIT A SECOND READING; IT EXPLODES COMBINATORIALLY WITH EXPRESSION LENGTH. THE FIX — the LAYERED GRAMMAR from the CFG topic: E → E + T | T T → T * F | F F → ( E ) | id Precedence is enforced by the LEVELS, associativity by the DIRECTION of the recursion. THE LANGUAGE IS UNCHANGED; ONLY THE GRAMMAR IS DIFFERENT — and it now has exactly one tree per string. ── EXAMPLE 2: THE DANGLING ELSE ──────────────────────────── S → if E then S | if E then S else S | a The string if E then if E then a else a has TWO trees: TREE 1 — the else belongs to the INNER if: if E then ( if E then a else a ) TREE 2 — the else belongs to the OUTER if: if E then ( if E then a ) else a THESE ARE GENUINELY DIFFERENT PROGRAMS. In tree 1 the else branch runs when the inner condition fails; in tree 2 it runs when the outer condition fails. THE UNAMBIGUOUS GRAMMAR, which enforces "else binds to the nearest unmatched if": S → M | U M → if E then M else M | a (MATCHED) U → if E then S | if E then M else U (UNMATCHED) THE IDEA: between a then and its else, only a FULLY MATCHED statement may appear, so an inner if without an else cannot swallow an outer else. IN PRACTICE most languages keep the ambiguous grammar and resolve it with a disambiguating rule, because the unambiguous version is markedly harder to read. YACC RESOLVES SHIFT-REDUCE CONFLICTS BY PREFERRING SHIFT, WHICH HAPPENS TO IMPLEMENT "NEAREST IF" AUTOMATICALLY — a pragmatic accident that became the convention. ── OTHER STANDARD AMBIGUOUS GRAMMARS ─────────────────────── S → SS | a | ε The string aa has many trees, and the ε production makes the count infinite. S → aS | Sa | a The string aa has two trees. S → a | Sb | bS Multiple derivations for strings such as bab.

── THE CRITICAL DISTINCTION ──────────────────────────────── AMBIGUITY IS A PROPERTY OF THE **GRAMMAR**, NOT OF THE LANGUAGE. A language may have an ambiguous grammar AND an unambiguous one — as the expression language does. Rewriting the grammar fixes the problem. BUT SOME LANGUAGES ARE **INHERENTLY AMBIGUOUS**: EVERY grammar generating them is ambiguous, and no rewriting can help. THE STANDARD EXAMPLE: L = { aⁿbⁿcᵐdᵐ : n,m ≥ 1 } ∪ { aⁿbᵐcᵐdⁿ : n,m ≥ 1 } The first set matches a's with b's and c's with d's; the second matches a's with d's and b's with c's. A STRING OF THE FORM aⁿbⁿcⁿdⁿ BELONGS TO BOTH SETS, and any grammar must derive it in both ways — through the structure that generates the first set and through the structure that generates the second. THE TWO DERIVATIONS REFLECT TWO GENUINELY DIFFERENT WAYS THE STRING SATISFIES THE DEFINITION, and no grammar can suppress one. INHERENTLY AMBIGUOUS LANGUAGES ARE NEVER DETERMINISTIC CONTEXT-FREE, so they cannot be parsed by any deterministic pushdown automaton — which connects this topic to the PDA material later in the section. ── DETECTING AMBIGUITY ───────────────────────────────────── THE FUNDAMENTAL AND UNCOMFORTABLE FACT: DECIDING WHETHER AN ARBITRARY CONTEXT-FREE GRAMMAR IS AMBIGUOUS IS **UNDECIDABLE**. There is no algorithm that takes any CFG and correctly answers "ambiguous or not" in all cases. This is proved by reduction from Post's Correspondence Problem, which appears in the Turing machine section. SO IS DECIDING WHETHER A LANGUAGE IS INHERENTLY AMBIGUOUS. WHAT CAN BE DONE IN PRACTICE: · FIND A WITNESS. To prove a specific grammar ambiguous, exhibit ONE string with two trees. THIS IS ALWAYS THE EXAM TASK, and it is easy — the difficulty lies only in the general decision problem. · USE A PARSER GENERATOR. If yacc reports SHIFT-REDUCE or REDUCE-REDUCE CONFLICTS, the grammar is not LALR(1), which is often (though not always) because it is ambiguous. CONFLICTS ARE A SYMPTOM, NOT A PROOF. · RESTRICT TO A KNOWN-UNAMBIGUOUS CLASS. Every LL(k) and every LR(k) grammar is unambiguous BY CONSTRUCTION, because the parsing algorithm is deterministic and can therefore produce only one tree. THIS IS THE PRACTICAL ROUTE: design the grammar to be LR(1) and ambiguity cannot arise. ── REMOVING AMBIGUITY — THE TECHNIQUES ───────────────────── 1. IMPOSE PRECEDENCE BY LAYERING. One variable per precedence level, tighter-binding operators lower down. This is the expression grammar fix. 2. IMPOSE ASSOCIATIVITY BY THE DIRECTION OF RECURSION: LEFT-recursive A → A op B gives LEFT associativity RIGHT-recursive A → B op A gives RIGHT associativity Exponentiation is normally right-associative, which is why its rule is written the other way round from + and *. 3. MATCH CONSTRUCTS EXPLICITLY, as in the matched/unmatched statement grammar for the dangling else. 4. ADD EXPLICIT DELIMITERS to the language itself. Requiring endif, or braces around every branch, eliminates the dangling else by making the grammar unable to express the ambiguous form — WHICH IS WHY LANGUAGES LIKE ADA AND MODERN STYLE GUIDES REQUIRE THEM. 5. DECLARE PRECEDENCE IN THE PARSER GENERATOR: yacc's %left and %right directives resolve conflicts without changing the grammar. ── THE SUMMARY WORTH CARRYING AWAY ───────────────────────── AMBIGUITY IS A DESIGN DEFECT IN A GRAMMAR, USUALLY REPAIRABLE BY RESTRUCTURING; INHERENT AMBIGUITY IS A PROPERTY OF THE LANGUAGE ITSELF AND IS NOT REPAIRABLE AT ALL. Programming languages are designed to avoid the second case entirely, which is a deliberate act of language design rather than a happy accident.