Ambiguous Grammars

Ambiguity in grammars is a very important concept in Context-Free Grammars (CFGs), especially because it directly affects parsing, compiler design, and language clarity. 

---

🔹 What is Ambiguity in a Grammar?

A context-free grammar (CFG) is said to be ambiguous if at least one string in the language it generates has more than one distinct parse tree (or equivalently, more than one leftmost or rightmost derivation).

👉 Formally:
A CFG $G$ is ambiguous if

$$\exists \; w \in L(G) \quad \text{such that} \quad w \;\; \text{has two or more different parse trees.}$$

---

🔹 Why is Ambiguity a Problem?

• In programming languages, ambiguity makes parsing uncertain:
  Example: Does a + b * c mean (a + b) * c or a + (b * c)?

• Compilers require deterministic parsing → ambiguous grammars must be avoided or rewritten.

---

🔹 Example of an Ambiguous Grammar

Consider the CFG:

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

Language generated: simple arithmetic expressions with +, *, parentheses, and variable a.

---

Example String: a + a * a

Derivation 1 (treating + before *):

S → S + S
  → a + S
  → a + (S * S)
  → a + (a * a)

Parse Tree (grouping as a + (a * a)):

        S
      / | \
     S  +  S
     |     /|\
     a    S * S
          |   |
          a   a

---

Derivation 2 (treating * before +):

S → S * S
  → (S + S) * S
  → (a + a) * a

Parse Tree (grouping as (a + a) * a):

        S
      / | \
     S  *  S
   / | \    |
  S  +  S   a
  |     |
  a     a

---

✅ Both trees are valid → Grammar is ambiguous.

---

🔹 Removing Ambiguity (Disambiguation)

We can rewrite the grammar to enforce precedence:

• Multiplication (*) has higher precedence than addition (+).

• Both operators are left-associative.

Unambiguous grammar:

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

---

Derivation for a + a * a in this grammar:

$$E \Rightarrow E + T \Rightarrow T + T \Rightarrow F + T \Rightarrow a + T \Rightarrow a + T * F \Rightarrow a + F * F \Rightarrow a + a * a$$

Now the parse tree is unique, corresponding to a + (a * a).

---

🔹  Important Notes

• Every context-free language does not necessarily have an unambiguous grammar.
  

  Some languages (e.g., the language of arithmetic expressions with equal precedence and no parentheses) are inherently ambiguous.

• A language is called inherently ambiguous if every grammar that generates it is ambiguous.

---

✅ Summary for students:

• An ambiguous grammar allows multiple parse trees for the same string.

• This is problematic in programming language design.

• Example: arithmetic expressions (a+a*a) often cause ambiguity.

• Solution: rewrite grammar to enforce operator precedence and associativity.