Resolving Ambiguity

 

---

🔹 What Does Resolving Ambiguity Mean?

A CFG is ambiguous if some string has more than one parse tree.

To resolve ambiguity, we rewrite the grammar so that every valid string has exactly one parse tree (i.e., unambiguous grammar).

---

🔹 Methods to Resolve Ambiguity

✅ (a) Enforce Operator Precedence

• Ensure * is evaluated before +.

• Example:

Ambiguous grammar:

$$E \to E + E \;|\; E * E \;|\; (E) \;|\; a$$

Unambiguous grammar (with precedence):

$$E \to E + T \;|\; T$$
$$T \to T * F \;|\; F$$
$$F \to (E) \;|\; a$$

Now in a + a * a, multiplication (*) happens before addition (+).
So only one parse tree is possible.

---

✅ (b) Enforce Operator Associativity

• Ambiguity also arises in expressions like a - b - c.

• Should it be (a - b) - c (left-associative) or a - (b - c) (right-associative)?

We rewrite grammar for left-associativity:

$$E \to E - T \;|\; T$$

So a - b - c → (a - b) - c.

---

✅ (c) Use Parentheses Explicitly

• Parentheses naturally remove ambiguity by forcing grouping.

• Example: In arithmetic expressions, (a + b) * c vs a + (b * c).

---

✅ (d) Restrict the Grammar

• Sometimes ambiguity comes from unrestricted productions.

• Example: The dangling else problem in if-then-else.

Ambiguous grammar:

$$S \to \text{if } E \text{ then } S \;|\; \text{if } E \text{ then } S \text{ else } S \;|\; a$$

Ambiguity: if E1 then if E2 then S1 else S2 → Does else attach to first or second if?

Unambiguous solution (force else to match the closest if):

$$S \to M \;|\; U$$
$$M \to \text{if } E \text{ then } M \text{ else } M \;|\; a$$
$$U \to \text{if } E \text{ then } S$$

Here, else always binds to the innermost unmatched if.

---

✅ (e) Detect Inherent Ambiguity

• Some languages are inherently ambiguous, meaning no unambiguous CFG exists.

• Example:

$$L = \{ a^i b^j c^k \mid i = j \text{ or } j = k \}$$

This language is inherently ambiguous.
👉 In such cases, ambiguity cannot be resolved.

---

🔹 Summary for Students

• Ambiguity = multiple parse trees for the same string.

• Resolve ambiguity by:

  • Enforcing precedence (e.g., * before +).

  • Enforcing associativity (e.g., left-associative subtraction).

  • Using parentheses.

  • Rewriting grammar (e.g., dangling-else).

• Some languages are inherently ambiguous → can’t be fixed.