Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 287

for the strings that have equal number of a’s and c’s and in between there are multiple of

b’s so S → a A c and A → b | b A are the additional productions.

Hence, grammar has the productions

S → a S c | a A c

A → b | b A

That is also a context free grammar (CFG).

11.6 Derivation Tree (Parse Tree)..........................................................................................

When we constructed the language (strings) from the grammar, we will go through a sequence

of derivations. The tree representation of the derivations are called derivation tree/parse tree.

Parse tree shows how the terminal symbol/s are generated and grouped into strings. The

recursive inferences of the productions are also visualize in the parse tree.

The ambiguity characteristic of the grammars and languages is an important application

of parse trees. In the compiler theory parse tree provide the way how the source program is

translated into the machine level program.

11.6.1 Parse Tree Construction....................................................................................

Let the grammar G = (VN, VT, S, P) then, the derivation tree of G has following characteristics,
n The nodes of this tree have labeled from VN ∪ VT ∪ {ε},
n The root of the tree has labeled S (start symbol),
n All internal nodes in the tree have labeled from VN,
n If a node has label X and X 1 , X 2 , X 3 ,.........XK are the labels of its children (from left-to-
right) then X → X 1 X 2 X 3 .........XK must be the production,
n If a node has label ε then it must be a leaf node and also it must be the only son of its
parent.
On bases of these characteristics we can construct the parse tree.
Example 11.10. Let VN = {S}, VT = {+, H, (,), a} and the productions are S → S + S/S H S/(S)/a.
Then construct the derivation tree for the terminal string (a + (a H a)).
Sol. First we go through the derivation sequence for the given terminal string, i.e.,
S ⇒ (S) [we start from this production because the first terminal string is ‘(’]
S ⇒ (S + S) [∴ S → S + S]
S ⇒ (a + S) [∴ S → a]
S ⇒ (a + (S)) [∴ S → (S)]
S ⇒ (a + (S H S)) [∴ S → S H S]
S ⇒ (a + (a H S)) [∴ S → a]
S ⇒ (a + (a H a)) [∴ S → a]
So, from starting symbol S we reaches to the terminal string (a + (a H a)), and its deriva-
tion tree is shown in Fig. 11.10.