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$:

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<N_{k}$, 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

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.