The Derivation Tree

The yield

The yield of a tree is the string obtained by reading its leaves from left to right, with epsilon leaves contributing nothing.

That definition is what connects the tree to the language: the strings of L(G) are exactly the yields of the derivation trees of G. A tree whose yield is w is a proof that w is in the language, and finding such a tree is what parsing means.

Worked: one tree, read three ways

Take the grammar for a to the n followed by b to the n.

S->aSb | ε

Accepts: ε, ab, aabb, aaabbb

Rejects: a, b, ba, aab, abab

The derivation of aabb, from chapter 23:

S
aSb
aaSbb
aabb

The tree, written with indentation, one vertex per line, children indented under their parent:

S
  a
  S
    a
    S
      ε
    b
  b

Read it against the four conditions. The root is S. The interior vertices are the three S. The leaves are a, a, epsilon, b, b, all terminals or epsilon. And each S's children spell a right hand side: the outer two spell a, S, b, which is the first production, and the innermost spells epsilon, which is the second.

The yield is read off the leaves left to right: a, a, epsilon, b, b, and the epsilon contributes nothing, so the yield is aabb. Which is the string the derivation produced, as it must be.

Worked: building the tree from a derivation

The procedure, and it is mechanical.

1. Write the start symbol as the root.
2. Take the derivation's first step. It rewrote some occurrence of some variable; find the vertex for that

occurrence and give it one child per symbol of the right hand side, in order.

1. Repeat for each step, always attaching to the vertex for the occurrence that step rewrote.
2. When the derivation ends, every leaf is a terminal or epsilon.

Take a grammar with two variables so the occurrences are worth tracking.

S->AB
A->aA | a
B->bB | b

Accepts: ab, aab, abb, aabb, aaabbb

Rejects: ε, a, b, ba, bab

A derivation of aabb:

S
AB
aAB
aaB
aabB
aabb

The tree it builds:

S
  A
    a
    A
      a
  B
    b
    B
      b

Step by step: the first step gives S the children A and B. The second rewrites A as aA, so A gets children a and A. The third rewrites the inner A as a, so it gets one child a. The fourth rewrites B as bB. The fifth rewrites the inner B as b.

The yield is a, a, b, b, which is aabb.

Notice what the tree shows and the string does not: that the two a belong to A and the two b belong to B. That structure is the whole reason a compiler wants a tree.

Worked: reading a tree back into a derivation

The reverse, which MU's papers also set.

Take this tree, for the grammar V2 above:

S
  A
    a
  B
    b
    B
      b

The yield is a, b, b, which is abb.

A derivation, obtained by choosing an order in which to expand the interior vertices. Expanding leftmost first:

S
AB
aB
abB
abb

And there are other derivations of the same tree, differing only in the order. Chapter 43 counts them.

The tree and the expression grammar

The tree is what makes operator precedence visible, so here is the arithmetic grammar of chapter 41 with a tree.

E->E+T | T
T->T*F | F
F->(E) | i

Accepts: i, i+i, ii, i+ii, (i+i)*i

Rejects: ε, +, i+, +i, i**i, (i

The tree for i+i*i:

yield i+i*i
E
  E
    T
      F
        i
  +
  T
    T
      F
        i
    *
    F
      i

Read the shape rather than the labels. The top of the tree is a plus, with i on its left and the whole of i*i on its right. So the tree says: add i to the product of i and i. It does not say: multiply the sum of i and i by i.

That is precedence, and it is a fact about the shape of the tree, not about the string. The three levels E, T, F are what force it: a plus can only appear at an E vertex, a times only at a T vertex, and a T is below an E, so a plus is always higher in the tree than a times. Chapter 44 shows what happens to a grammar that tries to do without the levels.

Distinctions

What it does NOT mean

A tree is not a derivation. It is what many derivations have in common, and the order is gone.

Two derivations of one string do not make a grammar ambiguous. Two trees do. V2 above has several derivations of abb and exactly one tree, and it is unambiguous.

The yield is not the label of the root. It is the leaves, read left to right.

An epsilon leaf is not nothing. It is a leaf, it is the only child of its parent, and it records that a null production was used. Omitting it makes the tree violate the fourth condition, because its parent would then have no children at all.

A terminal never has children. Interior vertices are variables, always, because only a variable can be rewritten.

Quick revision

• A derivation tree has the start symbol at its root, variables at every interior vertex, terminals or epsilon at

every leaf, and each vertex's children spelling a production's right hand side in order.

• The yield is the leaves read left to right, epsilon leaves contributing nothing. The strings of L(G) are exactly

the yields of the derivation trees.

• The tree records which production went where and forgets the order, which is why ambiguity is defined on trees.
• Building the tree from a derivation: attach children to the vertex for the occurrence each step rewrote.
• Reading a derivation from the tree: choose an order for expanding the interior vertices.
• Precedence is a fact about the SHAPE of the tree, forced by the level structure of the grammar.
• A subtree rooted at a variable A is an A-tree, and it is what the induction in the CFG pumping lemma works with.

Test yourself

1. Give the four conditions defining a derivation tree. The root is labelled with the start symbol; every interior vertex is labelled with a variable; every leaf is labelled with a terminal or epsilon; and if a vertex labelled A has children X1 to Xk left to right then A to X1 ... Xk is a production.

2. What is the yield, and what does it have to do with the language? The string of leaf labels read left to right, epsilon leaves contributing nothing. L(G) is exactly the set of yields of derivation trees of G, so a tree with yield w proves w is in the language.

3. For S->aSb | ε, draw the tree for ab. S at the root with three children: a, then S, then b. The inner S has one child, epsilon. The yield is a, epsilon, b, which is ab.

4. Why is ambiguity defined on trees rather than on derivations? Because one tree corresponds to many derivations, which differ only in the order the variables were taken. Counting derivations would make almost every grammar ambiguous; counting trees counts genuinely different structures.

5. Can an interior vertex be labelled with a terminal? Can a leaf be labelled with a variable? No to both. Only a variable can be rewritten, so only a variable can have children; and a finished tree has no variable left to rewrite, so no leaf carries one.

6. In the arithmetic grammar, what makes a plus sit higher in the tree than a times? The level structure. A plus can only appear at an E vertex and a times only at a T vertex, and every T vertex is below some E vertex, so any plus is nearer the root than any times in the same expression. That is what encodes precedence.