"Is this grammar ambiguous?" is a GATE staple, and the only honest way to answer yes is to exhibit two parse trees for one string. Eyeballing the productions or counting alternatives proves nothing. The proof is a construction, so let us build one and then remove the ambiguity cleanly.
What ambiguity actually means
A context-free grammar is ambiguous if at least one string in its language has two or more distinct parse trees. The equivalent derivation test is two distinct leftmost derivations, or two distinct rightmost derivations, for the same string.
This definition tells you exactly how to prove ambiguity:
Choose one string generated by the grammar.
Construct two genuinely different parse trees for it.
Show that both trees produce the same terminal string.
The witness is enough. You do not need to test every string in the language. The reverse is not true: failing to find a witness does not prove that the grammar is unambiguous.
This distinction fits naturally after the basic machinery of context-free grammars and pushdown automata. A PDA may recognise the language, while ambiguity asks whether the grammar assigns more than one syntactic structure to a string.
The classic ambiguous expression grammar
Consider this grammar:
E -> E + E | E * E | ( E ) | idIt gives + and * the same structural status. Nothing says that multiplication binds more tightly than addition. Nothing says that repeated additions or multiplications group from the left or from the right.
Use the witness string:
id + id * idUnder normal arithmetic convention, we expect id + (id * id). The grammar also permits (id + id) * id, which is a different structure with the same terminal sequence.
Worked ambiguity proof with two trees
For the first tree, put + at the root:
E => E + E
=> id + E
=> id + E * E
=> id + id * E
=> id + id * idThe right child is the multiplication subtree. This tree groups the expression as id + (id * id).
For the second tree, put * at the root:
E => E * E
=> E + E * E
=> id + E * E
=> id + id * E
=> id + id * idHere the left child is the addition subtree. This tree groups the expression as (id + id) * id.
Both derivations end in the same five terminals, but their roots and internal structures differ. Therefore the grammar is ambiguous. Notice the standard of proof: one witness string, two trees, one firm conclusion.
Encoding precedence and associativity
The standard repair gives each precedence level its own nonterminal:
E -> E + T | T
T -> T * F | F
F -> ( E ) | idAn E may combine terms with +, but a T handles multiplication before it becomes part of that addition. Therefore id + id * id can only take the structure id + (id * id). Multiplication has higher precedence because it appears at the tighter T level.
Recursion direction encodes associativity. The production E -> E + T is left recursive, so id + id + id groups as (id + id) + id. If the production were E -> T + E, the same operator would be right associative, giving id + (id + id).
Do not mix the two jobs. Separate nonterminal levels establish precedence. Recursion direction within a level establishes associativity. These ideas also matter when you compare top-down and bottom-up parsing, because a parser must be given a grammar whose intended structure is explicit.
The dangling-else ambiguity
Expression grammar is not the only standard witness. Consider:
S -> if E then S
| if E then S else S
| aThe string if E1 then if E2 then a else a permits two attachments. The else may belong to the inner if E2, or it may belong to the outer if E1. Those attachments produce distinct parse trees.
The usual language rule attaches an else to the nearest unmatched if. A grammar can enforce that rule by separating fully matched statements from open statements. The important exam idea is not the names of those nonterminals. It is that the rewritten grammar removes the structural choice instead of asking the parser to guess.
Classification traps and the undecidability note
Ambiguity is a property of a grammar, not automatically of its language. The expression language above has an ambiguous grammar and the layered unambiguous grammar. Both describe the intended expressions, but only one fixes their structure.
Some context-free languages are inherently ambiguous, which means every grammar for the language is ambiguous. That is a much stronger claim than showing that one grammar is ambiguous.
There is also no algorithm that decides ambiguity for every arbitrary CFG. The general problem is undecidable. In a GATE question, expect a manageable witness, a parse-tree count for a particular string, or a choice among rewrites. Do not treat a short unsuccessful search for two trees as a proof of unambiguity.
How GATE tests grammar ambiguity
Typical stems ask you to identify an ambiguous grammar, count parse trees for a supplied string, choose a grammar with the required precedence, or determine the associativity produced by recursion. Before drawing anything, write the operator that should appear at the root. That usually exposes the two competing structures.
The KnowledgeGate bank has about 700 Compiler Design questions, including two-tree ambiguity proofs and grammar-classification patterns. Use them to practise construction, not recognition by appearance. For the current paper wording or any official pattern detail, confirm it on the official GATE portal of the organising IIT. The broader GATE preparation category can help place this topic in the full syllabus.
Short version and next step
Ambiguous means two parse trees for one string. Precedence comes from separate nonterminal levels, while associativity comes from recursion direction. Ambiguity for an arbitrary CFG is undecidable, but exam questions give you a concrete witness or a controlled rewrite.
Now take three expression strings and force yourself to draw both proposed roots before checking the answer. Then use GATE Guidance by Sanchit Sir to practise classify-the-grammar sets in sequence.
