Строительный блокнот  Automata methods and madness 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 [ 60 ] 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

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.



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 [ 60 ] 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175