Parse Trees

Parse Trees

AU Dec.-03,04,05,10,12,14,15, May-04,05,09,13,16, Marks 16

• Derivation trees is a graphical representation for the derivation of the given production rules for a given CFG.

• It is the simple way to show how the derivation can be done to obtain some string from given set of production rules.

• The derivation tree is also called parse tree.

• Following are properties of any derivation tree -

1. The root node is always a node indicating start symbol.

2. The derivation is read from left to right.

3. The leaf nodes are always terminal nodes.

4. The interior nodes are always the non-terminal nodes.

• For example,

S → bSb | a | b is a production rule. The S is a start symbol.

• The above tree is a derivation tree drawn for deriving a string bbabb. By simply reading the leaf nodes we can obtain the desired string. The same tree can also be denoted by, Fig. 3.4.2

Relationship between Derivation and Derivation Trees

AU Dec.-03, 04, 05, 10, 12, 14, 15, May-04, 05, 09, 13, 16, Marks 16

Theorem: Let G = (V, T, P, S) be a context free grammar. Then S ⇒ a if and only if there is a derivation tree in grammar G which gives the string a.

OR

Theorem Let G = (V, T, P, S) be a context free grammar then prove that if the recursive inference procedure tells us that terminal string w is in the language of variable A, then there is a parse tree with root A and yield w. AU: Dec.-15, Marks 10

Proof: For a non-terminal S there exists S ⇒ w if and only if there is a derivation tree starting from root S and yielding w. To prove this we will use method of induction.

Basis of induction: Assume that there is only one interior node S. The derivation tree yielding S₁, S₂, S₃, … ,S_n. From S is that means S ⇒ S₁, S₂, ... S_n ⇒ a is input string.

Induction hypothesis: We assume that for K-1 nodes the derivation tree can be drawn. We then can prove that for K vertices also we can have a derivation tree. That means the input string a can be derived as S → S₁, S₂, S₃, ….Sk. There are two cases: either S_i may be a leaf variable or S_i may be an interior node yielding a. The S derives a by fewer number of K steps then a ϵ S₁ S₂ S₃ …S_k.

If a_i = S_i then S_i is leaf node (terminal) and if S_i ⇒ a_i then S_i is an interior node. The tree for S₁ S₂ …S_k will be shown in Fig. 3.3.4

We can also represent it as shown in Fig. 3.4.5.

This proves that S ⇒ S₁, S₂, S₃ …. S_n ⇒ a can be obtained.