Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Ambiguous grammars

Notes on ambiguous grammars: what ambiguity means in context-free grammars, how to detect and remove it, examples (including inherently ambiguous languages), and exam-focused tips.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Ambiguity in grammars matters because a compiler or parser must choose a single meaning for each program construct. An ambiguous grammar can give two different parse trees (two meanings) for the same source string, causing wrong code generation or inconsistent semantics. Engineers use unambiguous grammars (or disambiguation rules) when designing programming-language front ends, interpreters and parsers.

Key ideas

Start with definitions (each bold word is defined before it is used):

  • Grammar: a formal specification that generates strings. For context-free discussion we use context-free grammar (CFG).
  • CFG: a 4-tuple G = (V, Σ, P, S) where V is a finite set of nonterminals, Σ is a finite set of terminals (disjoint from V), P is a finite set of productions (rules of form A → α with A ∈ V and α ∈ (V ∪ Σ)*), and S ∈ V is the start symbol.
  • Derivation: a sequence of rule applications starting from S that produces a string of terminals. A leftmost derivation always replaces the leftmost nonterminal at each step; a rightmost derivation always replaces the rightmost nonterminal.
  • Parse tree (or derivation tree): a rooted ordered tree that visually shows how productions expand the start symbol to give a terminal string. Internal nodes are nonterminals; leaves are terminals (or ε if used).
  • Language of G, L(G): the set of terminal strings derivable from S.

Definition of ambiguity:

  • Ambiguous grammar: A CFG G is ambiguous if there exists some string w ∈ L(G) that has two or more distinct parse trees (equivalently two distinct leftmost derivations or two distinct rightmost derivations). Formally: there exists w ∈ Σ* such that #ParseTrees_G(w) ≥ 2.
  • Unambiguous grammar: a CFG that is not ambiguous (every w ∈ L(G) has exactly one parse tree in G).
  • Ambiguous language: a context-free language L is called ambiguous if there exists at least one ambiguous CFG G with L(G) = L; L is called unambiguous if there exists some unambiguous CFG for L.
  • Inherently ambiguous language: a context-free language for which no unambiguous grammar exists (i.e., every CFG generating it is ambiguous).

Important properties and facts (exact statements):

  • Equivalence of parse trees and derivations: For a CFG G and string w, the existence of two distinct parse trees for w is equivalent to the existence of two distinct leftmost derivations (and equivalent to two distinct rightmost derivations). (Assumption: the CFG is standard with labelled productions.)

  • Undecidability of ambiguity: The decision problem “Given a CFG G, is G ambiguous?” is undecidable (there is no algorithm that decides ambiguity for every CFG). Note: the proof is nontrivial and uses reductions from known undecidable problems.

  • There exist inherently ambiguous CFLs: there are context-free languages for which no unambiguous grammar exists. (Example languages are known; constructing a rigorous proof is advanced.)

How ambiguity arises in practice and common remedies:

  • Ambiguity often comes from productions allowing multiple binary groupings (associativity) or lacking precedence (for operators). Example pattern: E → E + E | E * E | (E) | id is ambiguous.
  • Fixes include: redesigning grammar to encode precedence and associativity (separate nonterminals for each precedence level), using explicit associativity rules (left- or right-associative), or using parser disambiguation rules (precedence and associativity declarations in parser generators).

What to draw when asked to show ambiguity:

  • Draw two different parse trees for the same terminal string w. Label roots with the start symbol S; internal nodes with nonterminals; leaves left-to-right with the terminals forming w. Show clearly the differing tree shapes or rule expansions. Alternatively, present two leftmost derivation sequences step-by-step and label each substitution.

Formulas

G = (V, Σ, P, S) — G is a context-free grammar where V is nonterminals, Σ terminals, P productions, S start symbol. (Units: n/a; applies to CFGs.)

A → α — a production in P meaning nonterminal A can be replaced by string α ∈ (V ∪ Σ)*. (Units: n/a.)

L(G) = { w ∈ Σ* | S ⇒* w } — language generated by G; S ⇒* w means w is derivable from S by zero or more productions. (Units: n/a.)

G is ambiguous ⇔ ∃ w ∈ Σ* s.t. #ParseTrees_G(w) ≥ 2 — formal condition for ambiguity. (Units: n/a.)

L is inherently ambiguous ⇔ ∀ G with L(G) = L, G is ambiguous — definition of inherent ambiguity. (Units: n/a.)

(There are no physical SI units here.)

Worked examples

Example 1 — classic arithmetic grammar (show ambiguity):

Grammar G1: E → E + E | E * E | ( E ) | id

Task: Show that G1 is ambiguous by using the string id + id * id.

Model answer (step-by-step):

  1. First leftmost derivation producing parse with + at the top level (yields id + (id * id)): E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * id.
  2. Second leftmost derivation producing parse with * at the top level (yields (id + id) * id): E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * id. (Alternatively show different order of replacements producing a different tree.)
  3. Draw parse tree A: root E with children E, '+', E; left child E is leaf id; right child E has children E, '*', E whose leaves are id, id. Label leaves left-to-right to read id + (id * id).
  4. Draw parse tree B: root E with children E, '*', E where left E has children E, '+', E whose leaves are id, id; right E is id. This corresponds to (id + id) * id.
  5. Because two distinct parse trees produce the same terminal string, G1 is ambiguous.

Explain remedy: write unambiguous grammar with precedence: E → E + T | T T → T * F | F F → ( E ) | id This grammar is designed so * binds stronger than + and is (intended to be) unambiguous. Draw the single parse tree that yields id + (id * id) to show uniqueness.

Example 2 — ambiguous due to association (binary concatenation grammar):

Grammar G2: S → S S | a

Task: Show ambiguity for string aaa.

Model answer:

  1. One parse: S ⇒ S S ⇒ S S S ⇒ a S S ⇒ a a S ⇒ a a a (grouping ((a a) a)). Draw tree with left-branching binary nodes.
  2. Another parse: S ⇒ S S ⇒ a S ⇒ a S S ⇒ a a S ⇒ a a a (grouping (a (a a))). Draw tree with right-branching binary nodes.
  3. The two parse trees are structurally different, so G2 is ambiguous. Since the ambiguity comes from uncaptured associativity, we can make an unambiguous grammar for strings of a: S → a S | a (a regular grammar) if needed.

Example 3 — statement of an inherently ambiguous language (model-answer style, no full proof):

Language L = { a^n b^n c^m d^m | m,n ≥ 0 } ∪ { a^n b^m c^m d^n | m,n ≥ 0 } is inherently ambiguous.

Model answer sketch (what to write in exam): state the language clearly, explain that some strings (like a^k b^k c^k d^k) can be generated by both parts with different pairings of equal counts, and argue (nontrivially) that no CFG can force a unique parse for all such strings. A full rigorous proof is advanced and omitted; reference to standard textbooks is acceptable in an exam if the course expects only the statement and intuition.

Common mistakes

  • Showing two derivations that are actually the same parse tree written differently. Always check tree shape and parent–child relationships.
  • Confusing an ambiguous grammar with an ambiguous language: a language can admit both ambiguous and unambiguous grammars.
  • Attempting to prove undecidability by hand without a correct reduction; the undecidability proofs are nontrivial.

For your exam

Kinds of questions and what full-marks answers include:

  • Definitions: give formal definitions of CFG, parse tree, ambiguous grammar, inherently ambiguous language; include formal conditions (exists w with ≥2 parse trees).
  • Short notes: explain causes of ambiguity (operator precedence, associativity, productions like S → S S) and practical fixes (grammar refactoring, precedence levels, parser directives). Give a short example.
  • Derivations/diagrams: show two leftmost derivations or draw two distinct parse trees for the same string; label nodes and leaves to get full credit.
  • Proof/decision questions: state known decidability results (ambiguity undecidable) and sketch only if asked; don't attempt a full reduction unless the course covered it.
  • Transformations: show how to create an unambiguous grammar for arithmetic expressions by separating precedence and associativity; demonstrate with one example string.

A full-marks answer must be precise, include formal statements where asked, and when asked for a demonstration of ambiguity must show two distinct parse trees (drawn or described step by step) for the same terminal string.

Quick check

  1. Define an ambiguous grammar in one sentence.
  2. Give a short example (a grammar and a string) that shows ambiguity.
  3. Is the problem “given a CFG G, is G ambiguous?” decidable or undecidable?

Answers: 1) A CFG is ambiguous if some terminal string has two or more distinct parse trees in that grammar. 2) G: E → E + E | E * E | id; string id + id * id shows two trees (id + (id * id) and (id + id) * id). 3) Undecidable.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?