Exkurs: Syntaxbäume

Syntaxbäume (Ausdrucksbaum, engl. parse tree) sind eine einfache Methode, darzustellen, wie ein Satz mittels der Formationsregeln des vorangehenden Kapitels erzeugt worden ist. Die grundlegende Gestalt eines Baums ist in Abbildung 3.1 (Seite ) dargestellt. Die Kreise in einem Baum heißen Knoten, die Linien Kanten, Zweige oder Äste. Der oberste Knoten ist die Wurzel des Baums. Knoten, von denen keine Zweige weglaufen, werden Blätter oder Endknoten genannt.

Abbildung 3.1: Ein Baum

Zum Syntaxbaum wird ein Baum dadurch, dass er den Entstehungsweg eines Satzes ausdrückt. Gehen wir vom Satzbuchstaben $P$ aus; er ist gemäß Regel 3.3 ein Satz. Abbildung 3.2 (Seite ) zeigt einen Knoten, der diesen Satzbuchstaben wiedergibt.

Abbildung: Baum für den Satz $P$

Dieser Knoten ist zugleich der Baum für den (kurzen) Satz $P$.

Die Formationsregel 3.3 erlaubt es uns, zwei bestehende Sätze zu einem neuen zu verbinden, indem wir eines der zweistelligen Konnektive zwischen die beiden schreiben. Wählen wir als Konnektiv das Und und als zweiten Satz den Satzbuchstaben $Q$, dann entsteht der Satz $(P \wedge Q)$. Dieser Satz ist eine Konjunktion; in die Wurzel des Syntaxbaums wird daher das Und geschrieben. Da es sich um ein zweistelliges Konnektiv handelt, laufen von der Wurzel zwei Kanten weg. Die linke Kante läuft zu einem Teilbaum hin, der das linke Konjunkt darstellt; da dieses ein einfacher Satzbuchstabe ist, ist der linke Teilbaum ein einfacher Knoten. Ebenso verhält es sich mit dem rechten Konjunkt. Den kompletten Baum zeigt Abbildung 3.3 (Seite ).

Abbildung: Baum für den Satz $(P \wedge Q)$

Der Baum für den Satz $(P \wedge (Q \vee R))$ ist etwas umfangreicher. Da auch dieser Satz eine Konjunktion ist, wird die Wurzel mit dem Und beschriftet. Wie im vorangehenden Beispiel ist das linke Konjunkt ein Satzbuchstabe, wird also durch einen einfachen Knoten dargestellt. Das rechte Konjunkt ist allerdings ein zusammengesetzter Satz, nämlich eine Disjunktion. Der rechte von der Wurzel ausgehende Knoten verläuft daher zu einem mit dem Oder beschrifteten Knoten. Vom Oder-Knoten laufen seinerseits zwei Kanten weg, weil auch das Oder ein zweistelliges Konnektiv ist. Jede dieser beiden Kanten verläuft zu einem Teilbaum, der das linke bzw. das rechte Disjunkt wiedergibt. Der vollständige Baum ist in Abbildung 3.4 (Seite ) dargestellt.

Abbildung: Baum für den Satz $(P \wedge (Q \vee R))$

Von einem Knoten für ein einstelliges Konnektiv läuft nur ein Zweig weg, was für den Satz $\neg (P \wedge \neg P)$ in Abbildung 3.5 (Seite ) gezeigt wird.

Abbildung: Baum für den Satz $\neg (P \wedge \neg P)$

Bei Quantoren geht man gerne so vor, dass man die Individuenvariable, die neben dem Quantor steht, unter die eine und den quantifizierten Satz unter die andere Kante des Knotens schreibt. Satz $\bigwedge x (Fx \rightarrow Gx)$ ist in Abbildung 3.6 (Seite ) dargestellt.

Abbildung: Baum für den Satz $\bigwedge x (Fx \rightarrow Gx)$

Bäume im Allgemeinen und Syntaxbäume im Besonderen spielen in der Informatik eine sehr große Rolle. Hat man sich erst einmal an sie gewöhnt, wird man sie als eine übersichtliche Darstellung von Aussagen schätzen, der man die Struktur eines Satzes sofort ansieht und die dennoch ohne Klammern auskommt.