Syntaxbaum

Begriff und Zweck

Ein Syntaxbaum ist eine hierarchische Darstellung der Gliederung eines Textes. Er wird in der theoretischen Informatik und in der Linguistik verwendet. Als grafisches Hilfsmittel macht er sichtbar, wie ein Text in zusammengehörige Teile zerlegt wird; als Datenstruktur ermöglicht er die maschinelle Weiterverarbeitung, etwa in einem Compiler oder Übersetzer.

Die Bezeichnungen Syntaxbaum, Ableitungsbaum und Parsebaum werden in der Literatur nicht einheitlich gebraucht. Formal genau definiert ist vor allem der Ableitungsbaum, der auf dem Begriff der grammatischen Ableitung beruht.

Bei der Analyse eines natürlichsprachlichen Satzes oder eines formalen Textes findet zunächst meist die lexikalische Analyse statt: Der Text wird in Token oder Symbole zerlegt. Anschließend werden diese hierarchisch zu Konstituenten, also zusammengehörigen Satzteilen oder Textabschnitten, zusammengefasst. Das Ergebnis kann als Baum oder in einer geklammerten Schreibweise dargestellt werden. Ein konkreter Ableitungsbaum bildet dabei die Struktur eines bestimmten Textes genau ab.

Baumknoten können durch Attribute ergänzt werden, in der Linguistik beispielsweise durch morphologische Kategorien. So entsteht ein attributierter Syntaxbaum auf Grundlage einer attributierten Grammatik. Dadurch kann Kontextabhängigkeit berücksichtigt werden; im Compilerbau gehört dies bereits zur semantischen Analyse. Bei natürlichen Sprachen ist die Analyse besonders schwierig, weil die Reihenfolge der Satzbestandteile variieren kann.

Formale Definition des Ableitungsbaums

Gegeben sei eine kontextfreie Grammatik G = (N, Σ, P, S). Dabei bezeichnet N die Nichtterminalsymbole, Σ die Terminalsymbole, P die Produktionsregeln und S das Startsymbol. Ein Ableitungsbaum ist ein geordneter Baum, dessen Knoten mit Symbolen aus Σ ∪ N ∪ {ε} beschriftet sind. „Geordnet“ bedeutet, dass die Kinder eines Knotens eine feste Reihenfolge besitzen. ε bezeichnet das leere Wort.

Für den Baum gelten folgende Regeln:

• Die Wurzel ist mit dem Startsymbol S beschriftet. Wird diese Eigenschaft verlangt und erfüllt, spricht man von einem vollständigen Ableitungsbaum.
• Hat ein innerer, mit A beschrifteter Knoten die Kinder z₁, …, zₘ in dieser Reihenfolge, muss die Grammatik die Produktionsregel A → z₁…zₘ enthalten.
• Die Blätter sind mit Terminalsymbolen aus Σ oder mit ε beschriftet.
• Ist ein Blatt mit ε beschriftet, muss es der einzige Nachfolger seines Vorgängerknotens sein.

Damit können innere Knoten nur Nichtterminalsymbole tragen. Als Blätter sind nur Terminalsymbole oder das leere Wort zulässig.

Konstruktion und Mehrdeutigkeit

Für kurze Texte lässt sich ein Ableitungsbaum meist unmittelbar aus den Produktionsregeln aufbauen. Man beginnt an der Wurzel mit dem Startsymbol und ersetzt schrittweise jeweils ein Nichtterminal auf der linken Seite einer Regel durch die Symbole auf ihrer rechten Seite. Dies wird fortgesetzt, bis nur noch Terminale übrig sind. Parallel zeichnet man den Baum von oben nach unten. Umgekehrt kann man mit dem fertigen Satz beginnen und den Baum durch rückwärts angewandte Regeln von unten nach oben aufbauen.

Für den Satz „John hit the ball“ können unter anderem die Regeln S → NP VP, NP → John, NP → Det N, VP → V NP, V → hit, Det → the und N → ball verwendet werden. Eine mögliche Ableitung lautet: S ⇒ NP VP ⇒ John VP ⇒ John V NP ⇒ John hit NP ⇒ John hit Det N ⇒ John hit the N ⇒ John hit the ball.

Eine Grammatik heißt mehrdeutig, wenn es für mindestens ein Wort ihrer Sprache mehr als einen Ableitungsbaum gibt; andernfalls ist sie eindeutig. Die Grammatik S → SS und S → a ist mehrdeutig, weil „a a a“ sowohl als „[a a] a“ als auch als „a [a a]“ gegliedert werden kann. Bei der Grammatik S → aS und S → a gibt es dagegen nur eine solche Einteilung.

Bei einer mehrdeutigen Grammatik kann die Zahl der möglichen Ableitungsbäume mit der Wortlänge stark wachsen. Einzelne Ableitungsbäume eignen sich dann nicht mehr zur Darstellung aller Möglichkeiten. Deshalb werden konkrete Oberflächengrammatiken formaler Sprachen meist eindeutig formuliert. Abstrakte Grammatiken sind dagegen oft mehrdeutig; die eindeutige abstrakte Struktur kann sich aus der vorherigen Analyse des konkreten Textes ergeben.

Abstrakte Syntaxbäume

Ein abstrakter Syntaxbaum, englisch abstract syntax tree (AST), ist eine für die Verarbeitung im Rechner bestimmte Datenstruktur. Er übernimmt die wesentliche inhaltliche Struktur eines konkreten Ableitungsbaums, lässt aber Einzelheiten der syntaktischen Oberfläche weg. In der Literatur finden sich dafür auch Bezeichnungen wie abstrakter Ableitungsbaum oder Operatorbaum.

Ein AST ist nicht bloß eine formal festgelegte Vergröberung des konkreten Ableitungsbaums. Sein Aufbau richtet sich zusätzlich nach den Anforderungen der späteren Verarbeitung. Eine direkte Herleitung allein aus der Oberflächengrammatik führt daher meist nicht zu einem zufriedenstellenden Ergebnis.

Der kontextfreien Oberflächengrammatik steht eine abstrakte Grammatik gegenüber. Im engeren Sinn handelt es sich dabei meist um einen algebraischen Datentyp. Die Syntaxbäume werden als vielsortige Terme dargestellt. Deshalb gehen grammatische und algebraisch-logische Begriffe ineinander über: Nichtterminale können als Typen und Bäume als Terme betrachtet werden.

Beispiel und Darstellungsformen

Beim Ausdruck a × (b + 3) muss die konkrete Grammatik Regeln der Schreiboberfläche berücksichtigen. Dazu gehören die Punkt-vor-Strich-Regel, die Zusammenfassung gleichrangiger Teilausdrücke von links nach rechts und die Möglichkeit, durch Klammern eine andere Gruppierung festzulegen. Sie unterscheidet dafür etwa Ausdruck E, Term T und Faktor F und enthält die Terminalsymbole „(“, „)“, „+“ und „*“.

Für die spätere Verarbeitung sind diese Oberflächendetails nicht mehr erforderlich. Ein algebraischer Typ kann stattdessen durch die Konstruktoren add(E, E), mul(E, E), var(V) und num(N) beschrieben werden. Der abstrakte Syntaxbaum des Ausdrucks lässt sich dann als Term notieren: mul(var('a'), add(var('b'), num(3))).

Die Wurzel ist hier die Multiplikation. Ihr linker Teilbaum enthält die Variable a, ihr rechter Teilbaum die Addition der Variable b und der Zahl 3. Der AST liegt damit näher am Inhalt des Ausdrucks als der konkrete Ableitungsbaum. Er ist übersichtlicher, benötigt als Datenstruktur weniger Speicher und vereinfacht sowie beschleunigt Programme, die den Baum weiterverarbeiten. Deshalb wird die Zerlegung eines Quelltextes meist nicht als vollständiger konkreter Ableitungsbaum gespeichert.

Abstrakte Syntaxbäume können grafisch als Operatorbäume oder textuell als Terme dargestellt werden. In manchen Darstellungen wird statt eines algebraischen Datentyps eine vergröberte, möglicherweise mehrdeutige Grammatik angegeben. Durch zusätzliche Klammern lässt sich die gewünschte Struktur eindeutig ausdrücken; der Beispielbaum kann dann wieder quelltextnah als a * (b + 3) erscheinen.

Ein typisches weiteres Beispiel ist das Lambda-Kalkül. Seine abstrakte Grammatik wird häufig knapp als E := λV.E | EE | V angegeben. Dabei steht der dargestellte Ausdruck weiterhin für eine Termstruktur, auch wenn die Schreibweise wie eine gewöhnliche Grammatik aussieht.