Ambiguity; encoding operator precedence and associativity in a grammar

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• How many steps does a derivation of a string take, in terms of its parse tree? from Lesson 2.1.1
• State the two rules a lexer uses to choose among overlapping patterns. from Lesson 1.2.2
• Give the postorder of a tree with root + whose children are a and *, where * has children b and c. from Lesson 0.2.4

1 · The Story

📖

Two meanings, one rulebook

A speech contains “old men and women”. Kabir’s rulebook allows two charts: [old [men and women]], where the women are old too, and [[old men] and women], where they are not. The rulebook is not wrong; it is two-faced: one sentence, two structures, two meanings. Anaya at the Meaning Desk cannot work with that.

Mrs. Desai’s fix is a house rule: “an adjective attaches only to the nearest noun”. Kabir rewrites the rulebook so that only that chart is possible.

The same thing happens with numbers in budget speeches. “10 minus 3 minus 2” is 5 if read as (10 − 3) − 2, but 9 if read as 10 − (3 − 2). And “2 plus 3 times 4” is 14 or 20 depending on what is grouped first. Mrs. Desai’s house rules: times before plus, and equal operations from left to right.

2 · Predict First

🤔

With the rules E → E + E | E * E | id, how many different parse trees does id + id * id have? Write your guess down. The answer is in the vault.

3 · Core Concept

Ambiguity

A grammar is ambiguous if some sentence has two or more parse trees. Equivalently: two different leftmost derivations, or two different rightmost derivations, of the same sentence.

Ambiguity is a property of the grammar. The same language may have both ambiguous and unambiguous grammars. (A few languages have only ambiguous grammars: inherently ambiguous languages. That is a Theory of Computation fact, not examined here.) No algorithm can decide ambiguity for every grammar, so exam questions show it with a concrete string.

Why it matters

Different trees mean different meanings: 2 + 3 * 4 evaluates to 14 or 20. A parser must produce one tree, so either the grammar is rewritten, or (Chapter 2.4) the parser is told which choice to make.

Precedence: one nonterminal per level

Give each precedence level its own nonterminal. Lower precedence near the start symbol, higher precedence deeper:

E → E + T | T        (level 1: + −)
T → T * F | F        (level 2: * /)
F → ( E ) | id       (atoms and brackets)

Now * can only be built inside a T, below any +, so it is grouped first.

Associativity: which side repeats

Associativity decides how equal operators group. In E → E + T, the repeated E is on the left, so a + b + c groups as (a + b) + c: left associative. Writing the repetition on the right, E → T + E, gives a + (b + c): right associative, which is right for exponentiation (2^3^2 = 2^9) and assignment (a = b = c).

The dangling else

S → if E then S | if E then S else S | other is ambiguous: in if a then if b then x else y, the else can belong to either if (2 parse trees). Every C-like language uses the rule: else matches the nearest unmatched then. A grammar can enforce it by splitting statements into matched and unmatched ones:

S → M | U
M → if E then M else M | other
U → if E then S | if E then M else U

With this grammar the same input has exactly 1 parse tree.

Story → compiler term

4 · Visual

The two parse trees of the ambiguous grammar give two different values (computed by parsing and evaluating each tree).

Tree 1: id + (id * id).

Tree 2: (id + id) * id.

5 · Worked Examples

Example 1 Easy

Show that E → E − E | id is ambiguous, and give the two values of 10 − 3 − 2.

Solution

The string id − id − id has 2 parse trees: (id − id) − id and id − (id − id). With 10, 3, 2: (10 − 3) − 2 = 5 and 10 − (3 − 2) = 9, Mrs. Desai’s budget-speech problem.

Example 2 Medium

Rewrite E → E + E | E * E | ( E ) | id so that * binds tighter than + and both are left associative.

Solution

E → E + T | T
T → T * F | F
F → ( E ) | id

One nonterminal per level; the same-level nonterminal on the left gives left associativity. This is the grammar of Lesson 2.1.1.

Example 3 GATE

How many parse trees does id + id * id + id have in E → E + E | E * E | id? And id * id * id * id * id?

Solution

Every way of fully bracketing a chain of operators is a different tree. With 3 operators there are 5 trees; with 4 operators, 14. These are the Catalan numbers 1, 2, 5, 14, …; the operator symbols do not matter, only how many there are. Counted by enumerating all parse trees.

6 · Shortcuts

⚡

Parse trees of an operator chain in E → E op E | id with n operators = Catalan number Cₙ = 1, 1, 2, 5, 14, 42 for n = 0 … 5. Valid when: a fully ambiguous grammar of binary operators with one kind of atom and no other rules.

⚡

Read precedence and associativity off a grammar: deeper nonterminal = higher precedence; same nonterminal on the left = left associative, on the right = right associative. Valid when: layered expression grammars.

7 · GATE Traps

⚠️

• Ambiguity needs two parse trees for the same string, not two derivation orders of the same tree.
• Two different derivations are not proof of ambiguity unless both are leftmost (or both rightmost).
• E → T + E is right associative even though it looks like the usual grammar.
• Removing ambiguity changes the grammar, not the language.
• The dangling else resolves to the nearest unmatched then.

8 · Memory Hook

🧠

“Lower in the tree, sooner it’s done; same side repeating says where it’s won.” Deep = high precedence; left repetition = left associative.

9 · Connect the Dots

The unambiguous expression grammar has productions like E → E + T that begin with their own left side. The parsing method of Chapter 2.3 cannot cope with that. The next lesson rewrites grammars to remove such rules and to factor out common beginnings.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markAmbiguity

A grammar is ambiguous if:

• (A) some sentence has two or more parse trees
• (B) it has ε-productions
• (C) it has two productions for one nonterminal
• (D) some sentence has both a leftmost and a rightmost derivation

Q2NAT2 marksCounting trees

How many parse trees does id * id + id * id have in E → E + E | E * E | id?

Numerical answer: ________

Q3MCQ1 markAssociativity

In the grammar E → T + E | T, T → id, the operator + is:

• (A) left associative
• (B) right associative
• (C) non-associative
• (D) of higher precedence than id

Q4MSQ2 marksPrecedence

In E → E − T | T, T → T / F | F, F → ( E ) | id, which are true?

• (A) / has higher precedence than −
• (B) − is left associative
• (C) / is right associative
• (D) the grammar is ambiguous

Q5NAT1 markAmbiguity

How many parse trees does - id + id have in E → E + E | - E | id?

Numerical answer: ________

11 · Rule Card

• Ambiguous grammar: some sentence has ≥ 2 parse trees (≥ 2 leftmost derivations).
• Fix precedence: one nonterminal per level; lowest precedence nearest the start symbol.
• Fix associativity: E → E op T (left), E → T op E (right).
• Dangling else: else matches the nearest unmatched then (matched/unmatched grammar).
• Trees of an operator chain in E → E op E | id: Catalan numbers 1, 2, 5, 14, 42.

12 · Concept Ledger

ambiguous grammarprecedence levelassociativity (left, right)dangling elsematched/unmatched statementsinherently ambiguous language (not examined)

13 · Answer Vault