Syntaxbaum

Ein Syntax-, Ableitungs- oder Parsebaum ist ein Begriff aus der theoretischen Informatik und bezeichnet eine baumförmige Darstellung einer Ableitung. Der Syntaxbaum ist ein Hilfsmittel zur Visualisierung von Wörtern einer (kontextfreien) Grammatik.

Man betrachte eine kontextfreie Grammatik $G=\left(N,\Sigma ,P,S\right)$. Ein Ableitungsbaum dazu ist ein Baum, dessen Knoten mit Symbolen aus $\Sigma \cup N\cup \{\varepsilon \}$ (also Terminal- und Nichtterminalsymbolen und dem leeren Wort) beschriftet sind. Der Baum ist geordnet, d. h. die Kinder jedes Knotens haben eine feste Reihenfolge, und für die Beschriftung gilt:

• Die Wurzel ist mit dem Startsymbol $S$ beschriftet. Diese Eigenschaft wird gelegentlich nicht verlangt. Ein Baum, der sie erfüllt, wird als vollständiger Ableitungsbaum bezeichnet.
• Wenn die Kinder eines mit $A$ beschrifteten inneren Knotens mit den Symbolen $z_{1},\ldots ,z_{m}$ (in dieser Reihenfolge) beschriftet sind, muss die Grammatik die Regel $A\to z_{1}\ldots z_{m}$ enthalten.
• Die Blätter des Baumes sind mit Symbolen aus $\Sigma \cup \{\varepsilon \}$ beschriftet.
• Ist ein Blatt mit $\varepsilon$ gekennzeichnet, so ist es der einzige Nachfolger seines Vorgängerknotens.

Als innere Knoten kommen also nur Nichtterminalsymbole in Frage, sowie für die Blätter nur die Terminalsymbole oder das leere Wort. Für das Vierertupel werden auch die Buchstaben $G=\left(V,T,P,S\right)$ verwendet.

Konstruktion

Die möglichen Syntaxbäume/diagramme erstellen sich von der Wurzel ausgehend durch befolgen der Produktionsregeln. Bei der Ableitung einer kontextfreien Grammatik erfolgt je Ableitungsschritt das Ersetzen genau eines Nichtterminals. Der Ableitungsvorgang ist dann abgeschlossen, wenn keine inneren Knoten mehr vorhanden sind, d.h. der Syntaxbaum in den Blättern nur Terminale oder das leere Wort trägt. Alle Wörter einer kontextfreien Grammatik müssen über die Produktionsregeln durch einen abgeschlossenen Syntaxbaum darstellbar(ableitbar) sein.

Eindeutigkeit des Ableitungsbaums

Zu einer gegebenen Ableitung ohne $\varepsilon$-Regeln ist der Ableitungsbaum eindeutig. Zu einem Ableitungsbaum können jedoch verschiedene Ableitungen existieren, je nachdem, in welcher Reihenfolge die Regeln angewendet werden (siehe dazu Rechtsableitung). Diese verschiedenen Ableitungen erzeugen jedoch alle dasselbe Wort, welches sich am Ableitungsbaum an den Blättern ablesen beziehungsweise durch eine Tiefensuche ermitteln lässt.

Verschiedene Ableitungen zu einem Ableitungsbaum bedeuten dabei noch nicht, dass die Grammatik mehrdeutig ist: Dazu muss es verschiedene Ableitungsbäume geben, die dasselbe Wort erzeugen.

In der Literatur kommt es vor, dass Syntax- und Ableitungsbaum nicht synonym verwendet werden. Insbesondere im Compilerbau ist der abstrakte Syntaxbaum von Bedeutung, der durch Entfernen von inneren Knoten mit nur einem Kind aus dem Ableitungsbaum hervorgeht. Der eigentliche Ableitungsbaum wird dabei zur Unterscheidung oft als konkreter Syntaxbaum oder Parsebaum bezeichnet.

Beispiel

Wir betrachten eine Grammatik mit dem Startsymbol $S$ und den folgenden Regeln:

${\begin{matrix}S&\to &AB\\A&\to &aA\\A&\to &\varepsilon \\B&\to &b\end{matrix}}$

Ein möglicher Ableitungsbaum zu dieser Grammatik sieht so aus:

Durch Ablesen der Terminalsymbole an den Blättern von links nach rechts erhält man das abgeleitete Wort aab. Ableitungen zu diesem Baum sind unter anderem die Linksableitung

$S\Rightarrow AB\Rightarrow aAB\Rightarrow aaAB\Rightarrow aaB\Rightarrow aab$

und die Rechtsableitung

$S\Rightarrow AB\Rightarrow Ab\Rightarrow aAb\Rightarrow aaAb\Rightarrow aab.$

Literatur

• Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 6.1 Beispiele kontextfreier Sprachen und Syntaxbäume, S. 147–148. 
• Uwe Schöning: Theoretische Informatik – kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1, 1.1.4 Syntaxbäume, S. 15–17. 
• Juraj Hromkovič: Theoretische Informatik. Formale Sprachen, Berechenbarkeit, Komplexitätstheorie, Algorithmik, Kommunikation und Kryptographie. 3. Auflage. B.G. Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5, 10.4 Kontextfreie Grammatiken und Kellerautomaten, S. 378.