derivation tree of a derivation

Constructing a Derivation from a Derivation Tree

Let G be a context-free grammar. Given a (finite) derivation tree T of G, we can construct a derivation D of G. There are two ways of doing this: top-down, or bottom-up.

The idea with the top-down approach is to build the derivation one derivation step at a time, starting from the root of the tree. During each step, a node with children is picked so that the next derivation step is formed, thus creating a new derivation with the new derivation step attached. Do this until all nodes of the tree are used.

To facilitate the discussion, for each node n of T, denote [n] the label of n.

The top-down approach works as follows:

  1. 1.

    Set X0=Y0=:{r}, and D0 the derivation σ=[r], where r is the root of T.

  2. 2.

    Suppose Xi,Yi and Di are defined for i0, and Yi={n1,,nk} with n1<<nk. It is easy to see that Di is the derivation σ*[n1][nk].

    If none of the elements of Y have children, then set D:=Di. Otherwise, pick a node njYi with children n1,,nm such that n1<<nm. Then set

    • Xi+1:=Xi{nj},

    • Yi+1:=(Yi-{nj}){n1,,nm}, and

    • Di+1:=Di[n1][nj-1][n1][nm][nj+1][nk].

Since T is finite, D can be constructed in a finite number of steps above.

Definition. A derivation tree T is said to correspond to a derivation D if D can be constructed from T from the top-down.

From the construction above, one sees that every derivation tree corresponds to at least one derivation. But it may correspond to more than one derivation. If, in the second step of the construction above, one always picks the smallest node with children in each step, then the corresponding derivation is the leftmost derivation. Similarly, consistently picking the largest node in each step results in the rightmost derivation. This shows that a derivation tree T corresponds to a unique leftmost derivation (written LD(T)) as well as a unique rightmost derivation (written RD(T)).

The bottom-up approach starts out with the result u of the derivation tree T. The result corresponds to leaves of T. PartitionMathworldPlanetmathPlanetmath the set of leaves into blocks, so that two leaves belonging to the same block if they have the same parent. Pick a block B of leaves, and form a new word u1 from u by replacing the labels of leaves in B by the label of their parent. Then u1u is a derivation step. Next, form a new tree T1 from T by removing the leaves of T in B. So u1 is now the result of T1. Repeat the process just described, until all of the nodes are removed (Ti= for some i), which is possible since T is finite. What we end up with is a derivation. We will leave the formal detail to the reader.

Proposition 1.

A derivation can be constructed from the top-down iff it can be constructed from the bottom-up.

Constructing a Derivation Tree from a Derivation

Conversely, given a derivation D=σW1Wn, one can construct a derivation tree T such that D corresponds to T. The way this works is as follows: start with the tree with a single node whose label is σ. At each derivation step, additional nodes are added from the tree constructed so far, until the last derivation step is processed. The tree so constructed has a natural linear orderingPlanetmathPlanetmath, and hence is a derivation tree, which D corresponds to. This construction can be formalized as follows:

  1. 1.

    Defining nodes: (The nodes of the tree T will be tuples of positive integers)

    1. (a)

      Set node (1) whose label is σ.

    2. (b)

      Suppose nodes are defined for symbols occurring in Wi. Look at the derivation step WiWi+1. Suppose it is based on production PQ, and (p1,,pm) is the node whose label is P.

      • *

        If Q=N1Nk, where each NjΣ, then define nodes


        whose labels are N1,,Nk respectively.

      • *

        If Q=λ, then define one node (p1,,pm,1) whose label is λ.

    3. (c)

      Continue (b) until nodes whose labels are symbols forming word Wn are defined.

  2. 2.

    Defining arrows: Given two nodes p=(p1,,pr) and q=(q1,,qs), an arrow is constructed from p to q iff s=r+1 and p1=q1,,pr=qr.

  3. 3.

    Extending the partial orderMathworldPlanetmath on T to a linear order based on the nodes: see the entry on ordered treeMathworldPlanetmath for detail.

The algorithmMathworldPlanetmath shows that the derivation tree is uniquely constructed.

Definition. Given a derivation D, the derivation tree of D, denoted by TD, is the ordered tree constructed above from D.

It is easy to see that TD corresponds to D.

Remark. Suppose u is a word derived by a derivation D. One can find the leftmost derivation D of u using the methods provided above: first find TD of D, then find LD(TD), and set D=LD(TD).


  • 1 H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
  • 2 A. Salomaa, Formal Languages, Academic Press, New York (1973).
  • 3 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their RelationMathworldPlanetmath to Automata, Addison-Wesley, (1969).
Title derivation tree of a derivation
Canonical name DerivationTreeOfADerivation
Date of creation 2013-03-22 19:00:25
Last modified on 2013-03-22 19:00:25
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Classification msc 68Q45