we proceed with

WW2 Wi-iXiXi+] Xk

IVi W> (t; iaiXVl Xjt =>

wiw2 - Wi-ia2Xi+i Xk

W1W2 WiXj+t Xi+2 Xfc

BASIS: The basis is height 1, the least that a parse tree with a yield of terminals ean be. In this case, the tree mtist look like Fig. 5.8. with a root labeled A and children that read w, left-to-right. Since this tree is a par.se tree, .4 -> w mnst be a production. Thns, A w is a one-step, leftmost derivation of w from A.

INDUCTION: If the height of the tree is n, where n > 1, it must look like Fig 5.9. That is, there is a root labeled .4, with children labeled Xj, .Y2,..., Xt from the left. The Xs may be either terminals or variables.

1. If X,; is a terminal, define wi to be the string c:onsisting of X,; alone.

2. If Xi is a variable, then it nmst be the root of some subtree with a yield of terminals, which we shall call w. Note that in this case, the subtree is of height less than n. so the inductive hypothesis applies to it. That is, there is a leftmost dt:rivation A =J- wi.

Note that ги - Wi tii

We construct a leftmost derivation of w as follows. We begin with the step A X] Xj Xk- Then, for each j - 1,2,..., in order, we show that

A 4 wiWi--- WiXi+iXi+i Xk

This proof is actually another ituluction, this time on i. For the basis, г = 0, we already know that A Xi X - Xk. For the induction, assume that

A => H.iwo wj iXiX,+ i Xk

a) If Xi is a terminal, do nothing. However, we shall subsequently think of X, as the terminal string щ. Tims, we already have

A W[U;2---mXi+iXiy2--Xk

b) If Xj is a variable, continue with a derivation of wi from X.,-, in the context of the derivation being constructed. That is, if this derivation is

Xj qi ф- qj - li-i

The result is a derivation A w\W2 WiXi+i Xk.

When i - A;, the result is a leftmost derivation of w from .4. □

Example 5.15: Let us construct the leftmost derivation for the tree of Fig. 5.6.

We shall show only the final step, where wc construct the derivation from the

entire tree from derivations that correspond to the subtrees of the root. That is,

we shall assume that by recursive application of the technique in Theorem 5.14,

we have deduced that the subtree rooted at the first child of the root has

leftmost derivation E I a, while the subtree rooted at the third child of tm I hi

the root has leftmost derivation

£ => (E) {E + £) => [I+E) {a + E)

(m im Im tm tm

{a + I) {a+ /0) ia + 100) = {a + 600)

im bn Im

To build a leftmost derivation for the entire tree, we start with the step at the root: A E * E. Then, we replace the first E according to its deriva-

tion, following each step by *E to account for the larger context in which that derivation is used. The leftmost derivation so far is thus

EE I*E a*E

tm im Im

The * in the production used at the root requires no derivation, so the above leftmost derivation also accomits for the fiist two diildren of the root. We complete the leftmost derivation by using the derivation of £ => (o 4- 600),

in a context where it is preceded by a* and followed by the empty string. This derivation actually appeared in Example 5,6; it is:

£=> E*E=> I*E a*E

Im. tm Im tm

a*(E) a*{E + E) a*{I + E) а*{а + Е) Im Im Im tm

О *( + /) a * (о. + /0) -> а*{а + 100) a*(a + 600)

tm Im Im

□

A simLlru- theorem lets ns convert a tree to a rightmost derivation. The construction of a right mtjst derivation from a tree is almost the same as the construction of a leftmost derivation. However, after starting with the step A XiX2---Xi., we expand X first, using a rightmost derivation, then

expand X-j, and so on, down to X\. Thus, we shall state without further proof:

Theorem 5,16; Let G = {V,T,P,S) be a CFG, and suppose there is a parse tree with root labeled by variable A and with yield w, where w is in T*. Then there is a rightmost derivation A w in grannnar G. □

5.2.6 From Derivations to Recursive Inferences

We uow complete the loop suggested by Fig. 5.7 by showing that whenever there is a derivation A w for some CFG, then the fact that w is in the language of A is discovered in the recursive inference procedure. Before giving tlie theorem and proof, let us observe something important about derivations.

Suppose that we have a derivation A XiXs--A., w. Then we can break w into pieces w - w\w2 wa- such that w;. Note that if .Y,- is a terminal, then пц ~ X;, and the derivation is zero steps. The proof of this observation is not hard. You can show by induction on the number of steps of the derivation, that if X1X2 -X a, then all the positions of a that come from expansion of A,; are to the left of all the positions that come from expansion of Xj, if i < j.

Tf A ; is a variable, wo can obtain the derivation of Х{ wj, by starting with the derivation A w, and stripping away:

a) All the positions of the sentential forms that are either to the left, or right of the positions that are derived from X;, and

b) All the steps that are not relevant to the derivation of Wi from X .А.П example should make this process clear.

Example 5.17: Using the expression grammar of Fig. 5.2, consider the derivation

E*E E*E + EIE-t-EI*I + E

Consider the third sentential form, E*E + E, and the middle E in this form. Starting from E * E + E, we may follow the steps of the above derivation, but strip away whatever positions are derived from the E* to the left of the central E or derived from the +E to its right. The steps of the derivation then become E,EA,I,I,b. b. That is, the next step does not change the central E, the step after that changes it to /, the next two steps leave it as /, the next changes it to b, and the final step does not change what is derived from the central E.

If we take only the steps that change what comes from the central E, the sequence of strings E, E, T, I, I,b,b becomes the derivation E = J b. That derivation correctly describes how the central E evolves during the complete derivation. □

Theorem 5.18: Let G - (V, T, P. S) be a CFG, and suppose there is a derivation A w, where w is in Г*. Then the recursive inference procedure applied G

to G determines that w is in the language of variable A.

-Our diacussioii of Fiiuling sulxlcrivaiions from larger derivations assumed we were concerned with a variable in the second sentential form of some derivation. However, tlie idea applies 10 a variable in any step of a derivation.