# derivation tree

Given a formal grammar $G=(\Sigma,N,P,\sigma)$, recall that a derivation from words $u$ to $v$ over $\Sigma$ can be visualized as a finite sequence of words over $\Sigma$, connected by the binary relation $\Rightarrow$:

 $u_{0}\Rightarrow u_{1}\Rightarrow\cdots\Rightarrow u_{n}$ (1)

where $u=u_{0}$ and $v=u_{n}$. Each $u_{i}\Rightarrow u_{i+1}$ is a derivation step, which means that there is a production in $P$ which, when applied to $u_{i}$, yields $u_{i+1}$. In other words, there is $A\to B$ in $P$ such that $u_{i}=xAy$ and $u_{i+1}=xBy$, where $x,y$ are words over $\Sigma$.

When the formal grammar $G$ is context-free, a derivation can be represented by an ordered tree, revealing the structure behind the derivation that is usually not apparent in the linear representation $(1)$ above. This ordered tree is variously known as a derivation tree or a parse tree, depending how it is being used.

In the foregoing discussion, $G$ is context-free, and any derivation of $G$ begins with $\sigma$, the starting non-terminal.

Definition. A parse tree of $G$ is an ordered tree $T$ such that

1. 1.

the nodes of $T$ are labeled by elements of $\Sigma$, or the empty word $\lambda$,

2. 2.

if a node with label $A$ has children $N_{1},\ldots,N_{k}$ such that $N_{1}<\cdots, and that each $N_{i}$ has label $A_{i}$, then $A\to A_{1}\cdots A_{k}$ is a production of $P$.

A parse tree such that the root has label $\sigma$ is called a derivation tree, or a generation tree. Every subtree of a derivation tree is a parse tree.

Remark. Since $G$ is context-free, in a parse tree, any node that is not a leaf is labeled by a non-terminal symbol.

For example, if $\Sigma=\{\sigma,a,b,X,Y\}$, $N=\{\sigma,X,Y\}$, and the productions of $P$ are

 $\sigma\to aXY,\quad X\to bYb,\quad Y\to Xa,\quad Y\to a,$

then

represents a derivation tree of $G$. The tree represents the following derivations

• $\sigma\Rightarrow aXY\Rightarrow abYbY\Rightarrow abXabY\Rightarrow abXabb$

• $\sigma\Rightarrow aXY\Rightarrow abYbY\Rightarrow abYbb\Rightarrow abXabb$

• $\sigma\Rightarrow aXY\Rightarrow aXb\Rightarrow abYbb\Rightarrow abXabb$

Definition. If $\ell_{1},\ldots,\ell_{m}$ are the leaves of a parse tree $T$, with $\ell_{1}<\cdots<\ell_{m}$, then the result of $T$ is the word $B_{1}\cdots B_{m}$, where $B_{i}\in\Sigma$ is the label of $\ell_{i}$. A word over $\Sigma$ is said to correspond to a parse tree if it is the result of the tree.

In the example above, the result of the tree is $abXabb$.

Remark. A derivable word may correspond to several derivation trees. See the entry ambiguous grammar for more detail.

## References

• 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 Relation to Automata, Addison-Wesley, (1969).
Title derivation tree DerivationTree 2013-03-22 19:00:17 2013-03-22 19:00:17 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 68Q42 msc 68Q45 generation tree parse tree result of a derivation tree