CD Notes
Guide to grammar ambiguity covering detection, types of ambiguity, disambiguation techniques, operator precedence, associativity encoding, and the dangling else problem.
Definition
A grammar is ambiguous if there exists at least one string in its language that has two or more distinct parse trees (equivalently, two or more leftmost derivations or two or more rightmost derivations). Ambiguity is problematic for compilers because different parse trees may assign different meanings to the same source code.
Classic Example: Expression Grammar
Types of Ambiguity
| E | E + E | E * E | id |
| Which binds tighter | + or *? |
| E | E - E | id |
| "id - id - id" | (id-id)-id or id-(id-id)? |
| stmt | if expr then stmt |
| Example | L = {aⁿbⁿcᵐdᵐ} ∪ {aⁿbᵐcᵐdⁿ} |
Disambiguating Expression Grammars
| Strategy | Use grammar structure to encode precedence and associativity. |
| Ambiguous | Unambiguous: |
| E | E + E E → E + T | T (+ lower, left-assoc) |
| | E * E T | T * F | F (* higher, left-assoc) |
| | ( E ) F | ( E ) | id (atoms) |
| - Higher precedence | deeper level |
| - Left associativity | left recursion |
| - Right associativity | right recursion |
| E | T ** E | T (** is right-associative) |
| means | 2**3**4 = 2**(3**4) |
The Dangling Else Problem
Grammar
stmt → if expr then stmt else stmt
| if expr then stmt
| other
String: if E1 then if E2 then S1 else S2
Parse Tree 1 (else with outer if): Parse Tree 2 (else with inner if):
stmt stmt
/ | \ / | \ \
if E1 then stmt else S2 if E1 then stmt
| / | \ \
if E2 then S1 if E2 then S1 else S2
Convention: else matches NEAREST unmatched if (Tree 2).
Unambiguous grammar
stmt → matched_stmt | unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt | other
unmatched_stmt → if expr then stmt
| if expr then matched_stmt else unmatched_stmt
Or in yacc: declare "else" shift preference over reduce
Disambiguation in Parser Generators
| Stack | E + E Input: * id |
| Conflict | reduce E+E to E? or shift *? |
| Resolution: * has higher precedence | SHIFT |
| Stack | E - E Input: - id |
| Conflict | reduce E-E to E? or shift -? |
| Resolution: - is left-associative | REDUCE |
Detecting Ambiguity
| E | E + E (E on both left and right → likely ambiguous) |
| A | Aα | Aβ | ... (multiple left-recursive alternatives) |
| 4. Practical test | Try to find two parse trees for a string. |
| If found | definitely ambiguous. |
| If not found | might still be ambiguous for longer strings. |
Inherently Ambiguous Languages
Some context-free languages have NO unambiguous grammar:
L = { aⁿbⁿcᵐdᵐ | n≥1, m≥1 } ∪ { aⁿbᵐcᵐdⁿ | n≥1, m≥1 }
Any grammar for L must be ambiguous because the string aⁿbⁿcⁿdⁿ
belongs to BOTH halves of the union and cannot be uniquely parsed.
Programming languages are NEVER inherently ambiguous — they are
always designed with an unambiguous interpretation (possibly using
disambiguation rules on an ambiguous grammar).
Interview Questions
- Q: Is grammar ambiguity decidable?
A: No, it is undecidable in general — there is no algorithm that can determine whether an arbitrary CFG is ambiguous. However, specific sufficient conditions for ambiguity can be checked, and parsing table conflicts provide practical ambiguity detection for LL/LR grammars.
- Q: How do parser generators like yacc handle ambiguous grammars?
A: yacc allows the user to declare operator precedence and associativity (%left, %right, %nonassoc). When shift-reduce conflicts arise, these declarations determine the action. Additionally, yacc defaults to "shift" for shift-reduce conflicts and "first rule" for reduce-reduce conflicts, providing deterministic behavior even with ambiguous grammars.
- Q: Is it always possible to rewrite an ambiguous grammar as unambiguous?
A: For most practical programming languages, yes — we can encode precedence and associativity into the grammar structure. However, some context-free LANGUAGES are inherently ambiguous (no unambiguous grammar exists). These are rare and do not include any practical programming language.
- Q: What is the performance impact of disambiguation?
A: None at parse time. Disambiguation via grammar rewriting produces a different (but equivalent) grammar before the parser is built. Disambiguation via precedence/associativity rules resolves conflicts in the parsing TABLE at parser-generation time. Either way, the resulting parser runs in the same O(n) time.
- Q: How does the dangling else problem manifest in real languages?
A: In C/C++/Java, "if(a) if(b) s1; else s2;" is ambiguous in the grammar but resolved by convention (else matches nearest if). Python avoids it with mandatory indentation. Rust/Go avoid it with mandatory braces. Some languages (like Haskell) use layout rules to prevent the ambiguity entirely.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Ambiguity in Grammars for Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, analysis, ambiguity, grammars
Related Compiler Design Topics