"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. Ambiguity is proved by construction, and it is removed the same way, by rewriting the grammar until only one structure survives.
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.
Recognition and structure are different questions. The machinery of context-free grammars and pushdown automata settles the first one: a PDA built from the grammar accepts every string in the language. Ambiguity asks the stricter second question, whether the grammar gives each of those strings exactly one syntactic structure.
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.
The layered grammar is also the only one a parser can act on. Give a bottom-up parser the flat version, let it read id + id, and show it a * lookahead: reducing E + E to E and shifting the * are both legal, and no production breaks the tie. That shift-reduce conflict is this same ambiguity seen from the parsing side, which is why top-down and bottom-up parsing both assume a grammar whose intended structure is already 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.
KnowledgeGate's Compiler Design question bank runs to about 700 questions, including two-tree ambiguity proofs and grammar-classification sets. Work them by construction rather than by recognising a familiar-looking production. The eleven solved items in Ambiguous and Inherently Ambiguous Grammar MCQs sit closest to this section, and the GATE preparation category places compiler design inside the rest of the 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.
