Slide 2.7: Derivations
Slide 3.1: Ambiguity
Home

Context-Free Grammars (Cont.)

Parse Trees
A derivation tree or parse tree corresponding to a derivation is a labeled tree in which the interior nodes are labeled by nonterminals, the leaf nodes are labeled by terminals, and the children of each internal node represent the replacement of the associated nonterminal in one step of the derivation. Consider the grammar again: 
   <exp> ::= <exp> <op> <exp> | ( <exp> ) | number
   <op>  ::= + | – | *
The leftmost derivation of the previous slide and its corresponding parse tree are given as follows: 

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

The rightmost derivation of the previous slide and its corresponding parse tree are given as follows: 

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