For example, for the following derivation:

we would have the derivation tree:

This tree represents not just the given derivation, but all the different orders in which the same productions could be applied to produce the string abbc.

A *partial derivation tree* is any subtree of a
derivation tree such that, for any node of the subtree,
either all of its children are also in the subtree,
or none of them are.

The *yield* of the tree is the final string obtained by reading the leaves
of the tree from left to right, ignoring the s
(unless *all* the leaves are ,
in which case the yield is ).
The yield of the above tree is the string abbc, as expected.

The yield of a partial derivation tree that contains the root is a sentential form.

Copyright © 1996 by David Matuszek

Last modified Feb 26, 1996