-~. - - - - - - - - - - - - - ~ -
Chapter 6: Context-Free Languages );1 181
P consists of 5 ----+ (sign) (integer), (sign) ----+ + 1-,
(integer) ----+ (digit) (integer) I (digit)
(digit) ----+ 011121· .. 19
L(G) = the set of all integers. For example, the derivation of -17 can be
obtained as follows:
5 =? (sign) (integer) =? - (integer)
=? - (digit) (integer) =? - 1 (integer; =? - 1 (digit)
=? - 17
6.1.1 DERIVATION TREES
The derivations in a CFG can be represented using trees. Such trees
representing derivations are called derivation trees. We give below a rigorous
definition of a derivation tree.
Definition 6.1 A derivation tree (also called a parse tree) for a CFG
G = (V\'. L. P, 5) is a tree satisfying the following conditions:
(i) Every vertex has a label which is a variable or terminal or A.
(ii) The root has label S.
(iii) The label of an internal vertex is a variable.
(iv) If the vertices 111' 11~ • . . . , 11k written 'vvith labels Xl- X~, ..., X k are
the sons of vertex 11 with label A, then A ----+ X1X~ .. , X k is a
production in P.
(v) A vertex 11 is a leaf if its label is a E L or A; 11 is the only son of
its father if its label is A.
For example. let G = ({S, A}. {a. b}. P, S). where P consists of 5 ----+
aAS I a 155. A ----+ SbA 1ba. Figure 6.1 is an example of a derivation tree.
s
a 10
2
a 4
7 b
8 a
Fig. 6.1 An example of a derivation tree.
Chapter 6: Context-Free Languages );1 181
P consists of 5 ----+ (sign) (integer), (sign) ----+ + 1-,
(integer) ----+ (digit) (integer) I (digit)
(digit) ----+ 011121· .. 19
L(G) = the set of all integers. For example, the derivation of -17 can be
obtained as follows:
5 =? (sign) (integer) =? - (integer)
=? - (digit) (integer) =? - 1 (integer; =? - 1 (digit)
=? - 17
6.1.1 DERIVATION TREES
The derivations in a CFG can be represented using trees. Such trees
representing derivations are called derivation trees. We give below a rigorous
definition of a derivation tree.
Definition 6.1 A derivation tree (also called a parse tree) for a CFG
G = (V\'. L. P, 5) is a tree satisfying the following conditions:
(i) Every vertex has a label which is a variable or terminal or A.
(ii) The root has label S.
(iii) The label of an internal vertex is a variable.
(iv) If the vertices 111' 11~ • . . . , 11k written 'vvith labels Xl- X~, ..., X k are
the sons of vertex 11 with label A, then A ----+ X1X~ .. , X k is a
production in P.
(v) A vertex 11 is a leaf if its label is a E L or A; 11 is the only son of
its father if its label is A.
For example. let G = ({S, A}. {a. b}. P, S). where P consists of 5 ----+
aAS I a 155. A ----+ SbA 1ba. Figure 6.1 is an example of a derivation tree.
s
a 10
2
a 4
7 b
8 a
Fig. 6.1 An example of a derivation tree.