Review of Tree Terminology

We assume you have been introduced to the idea of a tree and are familiar with the commonly used definitions for trees. However, the following will serve as a review.

Trees are collections of nodes, with a parent-child relationship. A node has at most one parent, drawn above the node, and zero or more chUdren, drawn below. Lines connect parents to their children. Figures 5.4, 5.5, and 5.6 are examples of trees.

There is one node, the root, that has no parent; this node appears at the top of the tree. Nodes with no children are called leaves. Nodes that are not leaves are interior nodes.

A child of a child of a node is a descendant of that node. A parent of a parent of a is an ancestor. TViially, nodes are ancestors and descendants of themselves,

The children of a node are ord(!red from the left, and drawn so. If node is to the left of node M, then all the descendants of N are considered to be to the left of all the descendants of Л7 .

3. If an interior node is labeled .4, and its children arc labeled

X\,X2.... ,Xk

respectively, from the left, then .4 XiX-i - .Y is a production in P. Note that the only time one of the ХЧ can be e is if that is the label of the only child, and .4 -> e is a production of G.

Example 5.9: Figure 5.4 shows a parse tree that uses tht; expression grammar of Fig. 5,2, The root is labeled with the variable E. We нее that the production used at the root is + £, since th<! three children of the root hav(! labels

E, +, and E, respectively, from the left. .\t the leftmost child of the root, the production jE -V / is used, smce there is one child of that node, labeled /. □

Example 5.10: Figure 5.5 shows a parse tree for the palindrome grannnar of Fig. 5.1. The production used at the root is P -> OPO. and at the middle child of the root it is P IPl. .Note that at the bottom is a use of the production P f. That use, where tht node lab<>led by the head has one child, labeled e, is thc> only time that a node labeled e can appear in л parse tree. □

Figurf; 5.4; A par.se tree .showing the derivation oi I + E from E

1 P 1

Figure 5.3: A parse tree .showing the derivation P 0110

5.2.2 The Yield of a Parse Tree

If we look at the leaves of any parse tree and concatenate them from the left, we get a string, called the yidd of the tree;, which is always a string that is deriveei from the re)e)t variable. The fact that the yi(;ld is deriveei from the root will be proved shortly. Of special importance are thf)se parse trees such that:

1, The yield is a tmninal string. That is, all leaves are; labeled either with a termin;il or with t.

2. The root is labeled by the start symbeil.

These are the parse trees whosti yields are strings in the language of the underlying grammar. We; shall also prejve shortly that another way to describe the language of a grammar is as the; set of yiekls of those parse trees having the start symbol at the root anel a terminal string as yield.

Example 5.11: Figure 5.6 is an example of a tree with a terminal string as yield and th(; start symbol at the root; it is l)ased on the granunar for expressions that we introduced in Fig. 5.2. This trees yield is the string a* (ci + bOO) that was deriveei in Example 5.5. In fact, as w-e shall se*;, this particular ]>a)se tree is a representatiem of tiiat derivation. □

Figure 5.6: Parse tree showing a* (a 4- bOO) is in the language of our expression grammar

5.2.3 Inference, Derivations, and Parse Trees

Each of the ideas that we have introduced so far for describing how a grammar works gives us essentially the same facts about strings. That is, given a grammar G = {V, T, P, S), we shall show that the following are equivalent:

1. The recursive inference procedure determines that terminal string ю is in the language of variable A.

A uf.

5. There is a parse tree with root Л and yield w.

In fact, except for the use of recursive inference, which we only defined for terminal strings, all the other conditions - the existence of derivations, leftmost or rightmost derivations, and parse trees - are also equivalent if u) is a string that has some variables.