Slide 2.7: Parse trees
Slide 3.2: Ambiguity (cont.)
Home

Context-Free Grammars (Cont.)

Ambiguity
A grammar that generates a string with two distinct parse trees is called an ambiguous grammar. Consider the grammar again: 
   <exp> ::= <exp> <op> <exp> | ( <exp> ) | number
   <op>  ::= + | – | *
A leftmost derivation of the string “number–number*number” and its corresponding parse tree are given as follows: 

(1) <exp> ⇒ <exp> <op> <exp>
(2)  ⇒ <exp> <op> <exp> <op> <exp>
(3)  ⇒ number <op> <exp> <op> <exp>
(4)  ⇒ number – <exp> <op> <exp>
(5)  ⇒ number – number <op> <exp>
(6)  ⇒ number – number * <exp>
(7)  ⇒ number – number * number

Another leftmost derivation of the string “number–number*number” and its corresponding parse tree are given as follows: 

(1) <exp> ⇒ <exp> <op> <exp>
(2)  ⇒ number <op> <exp>
(3)  ⇒ number – <exp>
(4)  ⇒ number – <exp> <op> <exp>
(5)  ⇒ number – number <op> <exp>
(6)  ⇒ number – number * <exp> 
(7)  ⇒ number – number * number

This grammar is ambiguous because the string “number–number*number” can be generated by two different parse trees where the latter is correct according to the arithmetic rules. Since it does not specify precisely the syntactic structure of a program, an ambiguous grammar presents a serious problem for a parser, which is a component of compiler that is responsible for syntactical analysis of a sentence.