derivation tree

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

$$u_0\Rightarrow u_1\Rightarrow \mathrm{\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 $\mathrm{\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. the nodes of $T$ are labeled by elements of $\mathrm{\Sigma }$, or the empty word $\lambda$,

2. if a node with label $A$ has children $N_1,\mathrm{\dots },N_k$ such that , and that each $N_i$ has label $A_i$, then $A\to A_1\mathrm{\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 $\mathrm{\Sigma }=\{\sigma ,a,b,X,Y\}$, $N=\{\sigma ,X,Y\}$, and the productions of $P$ are

$$\sigma \to aXY,X\to bYb,Y\to Xa,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 ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_m$ are the leaves of a parse tree $T$, with , then the result of $T$ is the word $B_1\mathrm{\cdots }{B}_m$, where $B_i\in \mathrm{\Sigma }$ is the label of ${\mathrm{\ell }}_i$. A word over $\mathrm{\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.