110 CONTEXT-FREE LANGUAGES
S S
/I\
S b S/\\/I\
A\ c i
S b S a!(^60) (b)
Figure 3.4: The sentence abaca has two parse trees.
can be represented by the tree of Figure 3.4(b).
In general, for a context-free grammar G = (V, C, R, S), a parse tree can
be constructed as follows:
(1) Let S be th e root of the tree.
(2) Repeat the following until every leaf of the tree is either E or a terminal
symbol:
For any leaf A E V of the tree, select a rule A --+ ~1x2 l s l xn, where
xiEVUCfori=l,..., 72, and replace the node A in V by the following
tree:
/i\
1 x2 l ’ ’ 5
If the concatenation of the leaves of a parse tree is the string x E C”, then we
say this is a parse tree of x.
It is clear that a parse tree of x corresponds to a derivation of x. In fact,
a parse tree often represents more than one derivation of x. For instance,
for the grammar G1 defined above, there are 16 different derivations for x =
abaca. Among them, the eight derivations that begin with S^3 SbS are
all represented by the same parse tree of Figure 3.4(a). The other eight
derivations that begin with S + ScS are all represented by the parse tree of
Figure 3,4(b).
To make the relation between parse trees and derivations clearer, we define
that a derivation of a string x E L(G) is a leftmost derivation if it always
applies a rule to substitute for the leftmost nonterminal symbol in a sentential
form. Then, it is easy to verify that each parse tree of a string x corresponds
to a unique leftmost derivation of x. For instance, among the eight derivations
for x = abaca that begin with S 3 S&S’, the following is the only leftmost
derivation:
S =3 SbS 3 abS abScS abacS abaca.