Explain ambiguity in context-free grammars. Illustrate how ambiguity can lead to shift-reduce or reduce-reduce conflicts during LR parsing.

Question

Accepted Answer

**Ambiguity in a context-free grammar**

A CFG is **ambiguous** if some string in its language has **more than one parse tree** (equivalently, more than one leftmost derivation or more than one rightmost derivation).

**Example:** $E 	o E + E \mid E * E \mid id$ on the string $id + id * id$ has two parse trees.

```mermaid
flowchart TD
    subgraph T1["Tree 1: + at root (id + (id * id))"]
    a1["E"] --> a2["E"]
    a1 --> a3["+"]
    a1 --> a4["E"]
    a2 --> a5["id"]
    a4 --> a6["E"]
    a4 --> a7["*"]
    a4 --> a8["E"]
    a6 --> a9["id"]
    a8 --> a10["id"]
    end
    subgraph T2["Tree 2: * at root ((id + id) * id)"]
    b1["E"] --> b2["E"]
    b1 --> b3["*"]
    b1 --> b4["E"]
    b2 --> b5["E"]
    b2 --> b6["+"]
    b2 --> b7["E"]
    b5 --> b8["id"]
    b7 --> b9["id"]
    b4 --> b10["id"]
    end
```

The two trees give different meanings (different evaluation order), so the compiler cannot decide which one is intended.

**How ambiguity causes conflicts in LR parsing**

An LR parser must decide in every state whether to shift or reduce. An ambiguous grammar can never be LR(k) for any $k$, so its LR table always has at least one multiply-defined entry.

**1. Shift-reduce conflict.** For the grammar above, after reading `E + E` the parser reaches a state containing both items

$$E 	o E + E \cdot \qquad	ext{and}\qquad E 	o E \cdot * E$$

On the next input symbol `*` it could **reduce** by $E 	o E+E$ (giving tree 2) or **shift** `*` (giving tree 1). The table entry for (state, `*`) holds both `s` and `r`.

**2. Reduce-reduce conflict.** Take $S 	o A \mid B$, $A 	o a$, $B 	o a$. The string `a` has two parse trees. After shifting `a` the state contains

$$A 	o a \cdot \qquad	ext{and}\qquad B 	o a \cdot$$

On lookahead `$` the parser can reduce by $A 	o a$ **or** by $B 	o a$: two reduce actions in one cell.

**Removing the conflicts**

- Rewrite the grammar to enforce precedence and associativity: $E 	o E+T \mid T$, $T 	o T*F \mid F$, $F 	o id$.
- Or keep the grammar and resolve conflicts with rules (precedence: `*` binds tighter than `+`; left associativity), as Yacc/Bison do.
- Shift is the default choice in a shift-reduce conflict; the earlier rule is chosen in a reduce-reduce conflict.

Similar questions

Coursify Android App