Ambiguous Grammar

A grammar G is ambiguous if there exists at least one string w in L(G) that has more than one distinct parse tree.

Equivalently, a grammar is ambiguous if some string has more than one:

• leftmost derivation, or
• rightmost derivation

If a string has two different parse trees, it means the grammar can interpret that string in two different ways — just like a sentence in natural language that means two things at once.

---

Natural language analogy:

"I saw the man with the telescope."

This sentence is ambiguous because it has two valid parse trees:

• I [saw the man] [with the telescope] — I used a telescope to see the man
• I [saw] [the man with the telescope] — the man had a telescope

Both interpretations are grammatically valid, but they mean different things. A compiler that faces this situation cannot know which meaning the programmer intended.

---

The Formal Definition

Grammar G is ambiguous if:

Grammar G is unambiguous if:

The most famous ambiguity in programming language grammars is the dangling else problem.

Grammar:

Ambiguous string:

Parse Tree 1 — else belongs to the INNER if:

Parse Tree 2 — else belongs to the OUTER if:

Both parse trees are valid according to the grammar. They represent completely different program behaviour:

Most languages (C, Java, Python) resolve this by the "nearest unmatched if" rule: an else always belongs to the closest preceding unmatched if. This is a semantic convention, not a grammar rule — the grammar itself remains technically ambiguous.

The most common classroom example of ambiguity is a naïvely written arithmetic grammar.

Ambiguous Grammar:

This looks simple, but it is dangerously ambiguous. Consider the string id + id * id:

---

Parse Tree 1 — + is applied first (wrong precedence):

This tree computes (id + id) * id — addition before multiplication.

---

Parse Tree 2 — * is applied first (correct precedence):

Wait — let me draw this correctly:

and

Two different trees. Two different computed values for the same expression. A compiler using this grammar would produce unpredictable results.

---

Why This Is a Problem

A compiler must produce exactly ONE interpretation for every program. If the grammar is ambiguous, the parser could build either tree and the compiled code would be wrong for one interpretation.

The standard fix for an ambiguous arithmetic grammar is to introduce separate non-terminals for each precedence level. Lower precedence operators sit higher in the grammar (closer to S), and higher precedence operators sit lower (deeper in the grammar, parsed last and grouped tightest).

---

Unambiguous Arithmetic Grammar

Now the string id + id * id has exactly one parse tree:

The multiplication is always grouped under T before the addition is grouped under E. Only one tree is possible.

---

How Precedence Levels Work

Grammar Non-Terminal	Operators at This Level	Precedence
E (top)	+	Lowest — evaluated last
T (middle)	*	Higher — evaluated before +
F (bottom)	atoms, ( )	Highest — evaluated first

General rule: If operator OP₁ binds more tightly than OP₂, put OP₁ at a lower level (deeper in the grammar) than OP₂.

---

Adding More Operators

^ binds tightest because it sits at the G level, deepest in the grammar.

Precedence tells us which operator wins when two different operators compete. Associativity tells us which direction to group when the same operator appears twice in a row:

The grammar structure directly controls associativity.

---

Left-Recursive = Left-Associative

The rule E → E + T recurses on the left (E is on the left of +). This produces left-associative grouping.

Derivation of a - b - c:

This gives (a - b) - c ✓

---

Right-Recursive = Right-Associative

The rule E → T + E recurses on the right (E is on the right of +). This produces right-associative grouping.

Example — assignment (right-associative):

Grammar:

Tree for x = y = z:

This gives x = (y = z) ✓

Most ambiguous grammars can be rewritten into an equivalent unambiguous grammar. But some languages are inherently ambiguous — every possible grammar for them is ambiguous.

Classic example:

This is the set of strings where either the number of a's equals the number of b's, OR the number of b's equals the number of c's. There is no unambiguous CFG for this language because strings where i = j = k (e.g., "abc", "aabbcc") always have two valid parse trees — one from each "branch" of the OR.

---

Checking for Ambiguity — No General Algorithm

Unfortunately, there is no algorithm that can always decide whether a given CFG is ambiguous. The ambiguity problem for CFGs is undecidable (it cannot be solved by any computer program for all possible inputs).

In practice, parser generator tools like yacc/bison report shift-reduce or reduce-reduce conflicts, which indicate ambiguity in the grammar. These conflicts must be resolved by:

1. Rewriting the grammar (adding precedence levels, as shown above)
2. Explicit precedence/associativity declarations in the parser tool
3. Choosing a deterministic parsing strategy that resolves conflicts by rule (e.g., "prefer shift over reduce" — this resolves the dangling else)

---

Summary

Concept	Meaning
Ambiguous grammar	At least one string has two or more parse trees
Unambiguous grammar	Every string has exactly one parse tree
Fix: separate precedence levels	Add E / T / F layers to force one tree
Fix: left recursion for left-associativity	A → A op B
Fix: right recursion for right-associativity	A → B op A
Inherently ambiguous	No unambiguous grammar exists for the language
Detection	Undecidable in general; parser conflicts hint at it

Question 1 — When do we call a grammar ambiguous? Check whether the given grammar G is ambiguous or not for the string "a(a)aa".

Grammar G:

---

Answer:

Part 1 — Definition of Ambiguous Grammar

A grammar G is called ambiguous if there exists at least one string w ∈ L(G) that has more than one distinct parse tree.

Equivalently, G is ambiguous if some string w has:

• more than one leftmost derivation, or
• more than one rightmost derivation

If every string in L(G) has exactly one parse tree, the grammar is called unambiguous.

---

Part 2 — Understanding the Grammar

Step 1 — What does each rule generate?

Start with A:

Derivation	String produced
A → a	a
A → (A) → (a)	(a)
A → (A) → ((A)) → ((a))	((a))
A → (A) → (((A))) → (((a)))	(((a)))

So A generates strings of the form (ⁿ a )ⁿ for n ≥ 0 — a single 'a' surrounded by n matching pairs of parentheses.

And S → AA generates the concatenation of any two strings from L(A):

---

Step 2 — Attempt to derive "a(a)aa".

The string "a(a)aa" has 6 characters: a, (, a, ), a, a.

For S → AA to derive this string, we must split it into two parts A₁ and A₂, each belonging to L(A).

The strings in L(A) have lengths 1, 3, 5, 7, … (odd numbers only). So the only possible length splits of a 6-character string into two L(A)-strings are:

Split	A₁ (prefix)	A₂ (suffix)	A₁ ∈ L(A)?	A₂ ∈ L(A)?
(1, 5)	"a"	"(a)aa"	✓ (A → a)	✗ L(A) at length 5 = "((a))", not "(a)aa"
(3, 3)	"a(a"	")aa"	✗ not of the form (ⁿaⁿ)	✗
(5, 1)	"a(a)a"	"a"	✗ not of the form (ⁿaⁿ)	✓ (A → a)

None of the splits work.

The string "a(a)aa" ∉ L(G) — it cannot be derived from this grammar at all.

Since the grammar cannot generate "a(a)aa", there are zero parse trees for this string. The grammar is not ambiguous for this string.

---

Step 3 — Is the grammar ambiguous in general?

To be thorough, we check if ANY string in L(G) could have two parse trees.

For S → AA to be ambiguous, there must exist a string w = A₁A₂ = A₃A₄ where (A₁, A₂) and (A₃, A₄) are two different splits, with all four parts in L(A).

Key observation: All strings in L(A) have different lengths (1, 3, 5, 7, …). Therefore:

• If A₁ = "a" (length 1), then A₂ is the remaining suffix, uniquely forced.
• If A₁ = "(a)" (length 3), then A₂ is the remaining suffix, uniquely forced.
• And so on — for each valid first part, its length uniquely determines the split point.

No string in L(G) can be split two different ways, because the L(A)-strings have distinct lengths. Every string in L(G) has exactly one parse tree.

---

Conclusion

The grammar G is NOT ambiguous.

The specific string "a(a)aa" is not even in L(G). And for any string that IS in L(G), the derivation is unique — there are no alternative parse trees.

---

Question 2 - Consider the Grammar

i. Now, show that the grammar is ambiguous by constructing two parse trees for the following string:

if (0) if (1) other else other

ii. Rewrite the grammar so that it becomes unambiguous.

---

Answer:

i. The grammar is ambiguous — two parse trees for the same string

The string is if (0) if (1) other else other. The non-terminal if-stmt has two productions that both begin with if (exp) stmt; the else part is optional. So the single token else can legally attach either to the inner if (1) or to the outer if (0). That gives two different parse trees for the same terminal string, so the grammar is ambiguous.

---

Parse Tree 1 — the else belongs to the INNER if (nearest-if convention in many languages):

Meaning: if (0) then ( if (1) then other else other )

Derivation sketch (same grouping):

Here the else is a child of the inner if-stmt node.

---

Parse Tree 2 — the else belongs to the OUTER if:

Meaning: if (0) then ( if (1) then other ) else other

Derivation sketch:

Here the inner if-stmt uses only if (exp) stmt (no else on the inner if), and the else is a child of the outer if-stmt.

The two trees are structurally different (different parent for else), so the grammar is ambiguous.

---

ii. An unambiguous grammar (matched / unmatched statements)

Step 1 — What went wrong in the original grammar?

The two productions for if-stmt both start the same way: if (exp) stmt. The else branch is optional. So when the parser sees else after nested ifs, it cannot tell from the grammar alone whether else belongs to the inner if or the outer if. We need rules that never allow both shapes for the same string.

---

Step 2 — Main idea: split statements into two kinds

We replace the single non-terminal stmt (for “any statement”) with two names:

1. matched_stmt — a statement where every if has its own else somewhere inside it. Nothing “dangles”; the structure is balanced like matched parentheses.
2. unmatched_stmt — a statement that contains at least one if that does not get an else in the usual nested way we will enforce.

A full program statement is still one of these:

---

Step 3 — Define matched_stmt (fully balanced if-else)

If we only use matched pieces inside if … else …, then after if (exp) we never leave a “half-finished” if that could grab the next else.

• Base case: other is matched (no if at all).
• Recursive case: both the then and else parts must again be matched_stmt. So you cannot derive if (exp) stmt without else here — that “bare if” is intentionally not in matched_stmt.

---

Step 4 — Define unmatched_stmt (controlled dangling)

We still need to generate programs where an if has no else. Those are built only through unmatched_stmt:

• First production — if (exp) stmt: The then part is any stmt (matched or unmatched). This is how we get a simple if with no else, or a chain of ifs where the inner structure is still flexible — but see Step 5.
• Second production — if (exp) matched_stmt else unmatched_stmt: The then part is forced to be matched. So the else cannot attach to a then that ends with a raw inner if waiting for an else. Only the unmatched_stmt on the right of else can “continue” the dangling pattern.

Together, Steps 3–4 encode the same rule many languages use informally: else pairs with the nearest if that does not already have an else — but here it is forced by the grammar, not by a separate semantic rule.

---

Step 5 — Keep exp unchanged

---

Step 6 — Complete unambiguous grammar

---

Step 7 — Check the old ambiguous string

Take if (0) if (1) other else other.

• Outer reading we want to allow (else goes with the inner if):
  Use stmt → unmatched_stmt → if (exp) stmt, where stmt derives the inner if-else. The inner part can be matched_stmt, giving if (1) other else other after the outer if (0). This path is valid.

• Outer reading we want to forbid (else goes with the outer if):
  That tree needed the outer then part to be only if (1) other — a bare inner if with no else. Such a subtree is not a matched_stmt, because every matched if must have its own else. The old ambiguous grammar allowed the inner if to use only if (exp) stmt; here, forcing a matched “then” whenever we use if (exp) matched_stmt else unmatched_stmt blocks the outer else from attaching after if (1) other. So that second parse tree cannot be built.

So this grammar is unambiguous for this language: every string still has the same meaning as before, but each string has at most one parse tree.