Syntaxbaum

Ein Syntax- oder Ableitungsbaum ist eine baumförmige Darstellung einer Ableitung.

Man betrachte eine formale Grammatik $G=\left(N,\Sigma ,P,S\right)$ und eine Ableitung $S=w_{0}\Rightarrow w_{1}\Rightarrow ...\Rightarrow w_{n}=w$. $G$ sei eine Typ-2-Grammatik (vgl. Chomsky-Hierarchie).

Den zugehörigen Syntaxbaum erhält man, indem man

1. die Wurzel mit $S$ beschrifte,
2. Kinder $z_{i}$ mit $i\in \{1,...,m\}$ von Knoten $A$ erzeugt, wenn bei $w_{i-1}\Rightarrow w_{i}$ die Regel $A\rightarrow z_{1}...z_{m}$ mit $z_{i}\in N\cup \Sigma$ angewendet wird.

Blätter werden mit $w$ beschriftet.

Unter Umständen können mehrere Ableitungen zum gleichen Baum führen.