Resolving Ambiguity: Grammar Rewriting
You'll learn: How to systematically transform an ambiguous context-free grammar into an unambiguous one that generates the same language.
The Problem with Ambiguity
You've seen that some grammars allow multiple parse trees for the same string. This ambiguity causes real problems: compilers don't know which interpretation to use, and different parsers might choose differently. The solution? Rewrite the grammar's structure to eliminate multiple derivation paths while preserving the language it generates.
Core Transformation Techniques
Introduce precedence levels: For arithmetic expressions, create separate non-terminals for each precedence tier. Instead of one rule handling all operators equally, nest lower-precedence operations (like addition) above higher-precedence ones (like multiplication).
Enforce associativity: For left-associative operators, make the recursive production place the non-terminal on the left side of the operator. For right-associative operators, place it on the right. This structural choice eliminates the ambiguity about evaluation order.
Stratify productions: Break one ambiguous non-terminal into multiple specialized non-terminals, each handling a specific case. The grammar becomes more verbose but unambiguous.
Example Pattern
An ambiguous expression grammar might have:
E → E + E | E * E | number
Rewrite it with precedence layers:
E → E + T | T
T → T * F | F
F → number
Now there's exactly one parse tree per string. Addition sits at the top level, multiplication binds tighter at the middle level, and atomic values form the base.
The Tradeoff
Grammar rewriting adds complexity and more rules, but it guarantees deterministic parsing. The rewritten grammar accepts exactly the same strings—only the structure is constrained.
Key Takeaway: Ambiguity is resolved by restructuring grammar rules to encode operator precedence and associativity directly, creating unique parse trees without changing the language itself.