Syntaxbaum

Ein Syntax-, Ableitungs- oder Parsebaum ist ein Begriff aus der theoretischen Informatik und der Linguistik. Er bezeichnet eine hierarchische Darstellung der Zergliederung eines Textes. Syntaxbäume werden sowohl als Hilfsmittel zur graphischen Visualisierung der Zerlegung eingesetzt als auch, in Form einer Datenstruktur, zur Darstellung dieser Zergliederung für die maschinelle Weiterverarbeitung z. B. in einem Compiler oder Übersetzer.

Die Bezeichnungen werden in der Literatur nicht einheitlich verwendet. Formal scharf ist nur Temininus Ableitungsbaum definiert, der sich auf den Begriff der Ableitung stützt. Meist werden die Synonyme nur vage als eine gemeinsame Bezeichnung für eine ganze Gruppe verschiedenartiger Bäume eingesetzt, die dann, wie unten beschrieben, bei Bedarf technisch näher bezeichnet werden. Speziell in der Linguistik ist statt von Bäumen oft auch von Diagrammen oder Graphen die Rede.

Einleitung

Bei der (mechanischen) Analyse von natürlichsprachlichen Sätzen oder formalen Texten (z. B. Computerprogrammen) findet direkt nach der lexikalischen Analyse (der Zergliederung in Token oder Symbole) oft eine hierarchische Zusammenfassung der Symbole zu zusammenhängenden Satzteilen (Konstituenten) bzw. Teilabschnitten des formalen Textes statt. Umgekehrt kann dies wiederum auch als eine Zergliederung des Textes aufgefasst werden. Im Ergebnis erhält man einen Baum, wie den rechts gezeigten.

Technisch bezeichnet man diesen Baum auch als konkreten Ableitungsbaum, da er die resultierende Struktur anhand des konkreten Textes exakt darstellt. In der Linguistik sind jedoch auch Modelle gängig, die mehrere Schichten der Repräsentation vorsehen (z.B. Oberflächen- und Tiefenstruktur).

Oftmals werden die Knoten des Baums mit Attributen angereichert (in der Linguistik sind dies dann vor allem morphologische Kategorien). Man erhält so einen attributierten Syntaxbaum mit zugehöriger attributierter Grammatik. Während in den ersten beiden Baumdarstellungen eine kontextfreie Grammatik verwendet wird, kommt in letzterer die Kontextabhängigkeit zum Tragen. Hier spricht man im Kompilerbau bereits von semantischer Analyse. Diese Unterschiede spiegeln sich in der Chomsky-Hierarchie wieder.

Ableitungsbäume

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.

Konstruktion von Ableitungsbäumen

Möglichen Syntaxbäume/diagramme lassen sich für kurze Texte oft leicht durch Befolgen der Produktionsregeln erstellen. Für längere Texte stehen eine Vielzahl mechanischer Verfahren zur Verfügung.

Ableitungsbäume bei ein- und mehrdeutigen Grammatiken

Falls es für ein Wort der Sprache einer Grammatik mehr als einen Ableitungsbaum gibt, spricht man von einer mehrdeutige Grammatik, sonst von einer eindeutigen. Beispielsweise ist die folgende Grammatik mehrdeutig

${\begin{array}{lll}S&\rightarrow &S\ S\\S&\rightarrow &a\end{array}}$

da man etwa "a a a" in zwei verschiedenen Weisen einteilen kann: "[a a] a" und "a [a a]".

Bei mehrdeutigen Grammatiken kann die Zahl möglicher Ableitungsbäume für ein und dasselbe Wort mit der Länge des Wortes stark ansteigen. In diesem Fall sind Ableitungsbäume keine geeignete Darstellung für das Gesamt möglicher Ableitungen mehr. Bei formalen Sprachen wird die konkrete (Oberflächen-)Grammatik meist eindeutig formuliert. Abstrakte Grammatiken sind dagegen oft mehrdeutig, wobei sich die Eindeutigkeit des abstrakten Ableitungsbaums dann durch den Gang der Analyse aus dem konkreten ergibt.

Verwendung in der Linguistik

Anders als in der Informatik, in der Sprachen auch den technischen Möglichkeiten folgend definiert werden können, findet die Sprachwissenschaft schwierigere Voraussetzungen vor. Da z. B. die Satzglieder z. T. mehr oder minder beliebig vertauscht werden können, sind abweichend zu obiger Definition die Syntaxbäume dort oft nicht geordnet.

Darstellungen von Syntaxbäumen

Neben der einleitenden zeichnerischen Form werden in Artikeln auch geklammerte Darstellungen für Syntaxbäume verwendet: $[_{S}\ [_{\mathit {NP}}\ John]\ [_{\mathit {VP}}\ [_{V}\ hit]\ [_{\mathit {NP}}\ [_{\mathit {Det}}\ the]\ [_{N}\ ball]]]].$

Abstrakte Syntaxbäume

Für die Darstellung von Syntaxbäumen als Datenstruktur in einem Rechner wird die Bezeichnung abstrakter Syntaxbaum (engl: abstract syntax tree (AST)) inzwischen recht einheitlich verwendet, wobei die Terminologie auch hier schwankt und z. B. ebenfalls von abstrakten Ableitungsbäumen, Operatorbäumen o. Ä. die Rede sein kann. Ein exakter Zusammenhang von abstraktem Syntaxbaum und konkretem Ableitungsbaum wird in der Literatur z. T. angedeutet. Allerdings gehen bei diesen neben einer Vergröberung des Ableitungsbaums auch Erfordernisse der Tiefenstruktur, allgemein der weiteren Verarbeitung, mit in den Aufbau ein, so dass eine direkte formale Herleitung aus der Oberflächengrammatik meist im Ergebnis nicht zufriedenstellend ist.

Der kontextfreien Oberflächengrammatik steht dann einer abstrakte Grammatik gegenüber, die im engeren Sinne aber meist ein algebraischer Datentyp ist. Die Syntaxbäume werden dann als vielsortige Terme technisch repräsentiert. Die Analyse befindet sich dabei im Übergang zwischen grammatischen und algebraisch-logischen Begriffen, so dass hier fließend sowohl von Nonterminalen und Typen oder von Bäumen und Termen die Rede sein kann.

Beispiel

Konkreter (links) und abstrakter (rechts) Syntaxbaum für den Ausdruck $a\times (b+3)$

Die nebenstehende Abbildung zeigt konkrete und abstrakte Syntaxbäume für die nachfolgenden Grammatiken.

konkrete Grammatik	abstrakte Grammatik	algebraischer Typ
E :: E "+" T -- Ausdruck :: T T :: T "*" F -- Term :: F F :: V -- Faktor :: N :: "(" E ")" V -- Variable N -- Zahl	E :: E "+" E :: E "*" E :: V :: N	typ E = add(E, E); mul(E, E); var(V); num(N)

Die konkrete Grammatik in diesem Beispiel muss insbesondere die Prioritäten und Bindigkeiten der (Teil-)Ausdrücke regeln. Dass also Punkt- vor Strichrechnung geht und die Teilausdrücke gleicher Priorität von links nach rechts zusammenzufassen sind. Ebenso wird mit Klammerausdrücken die Möglichkeit angeboten, eine andere Zusammenfassung zu bewirken. Dies sind zusammen mit den "Schlüsselworten" (hier "(", ")", "+", "*") lediglich Eigenschaften der syntaktischen Oberfläche, die in der späteren Analyse und Weiterverarbeitung keine Rolle mehr spielen. Insbesondere kann auf die Unterscheidung in verschiedene Arten von Ausdrücken (hier E, T und F) sowie die Schlüsselworte völlig verzichtet werden, wie man am abstrakten Syntaxbaum sieht, der auch deutlich näher am "Inhalt" des Ausdrucks ist. Ferner werden konkrete Ableitungsbäume wegen diese Oberflächendetails nicht nur schnell unübersichtlich, sondern belegen auch als Datenstruktur im Rechner durch ihre Details mehr Speicherplatz als nötig. Dies schlägt sich ebenfalls in der Laufzeit und Kompliziertheit der Programme nieder, die später den Ableitungsbaum weiter verarbeiten sollen. Auch aus technischen Gründen wird die Zergliederung eines Quelltextes daher meist nicht durch einen konkreten Ableitungsbaum dargestellt.

Darstellung abstrakter Syntaxbäume

Neben der im Beispiel gezeigten graphischen Darstellung als (Operator-)Baum werden abstrakte Syntaxbäume technisch auch als Terme notiert, z. B.: mul(var('a'), add(var('b'), num(3))).

Abstrakte Grammatik

Während abstrakte Syntaxbäume Datenstrukturen sind und algebraische Typen bei ihnen in die Rolle der Grammatik treten, wird in der Literatur, speziell im Zusammenhang mit Kalkülen oft nur eine vergröberte, mehrdeutige Grammatik angegeben, die, wie in obigem Beispiel gezeigt, zwar dieselbe Struktur wie die Terme haben, aber noch Schlüsselworte enthalten. Diese Form ermöglicht eine dann vor allem eine angenehme Niederschrift abstrakter Syntaxbäume, die der eigentlichen Quelle oft sehr nahe ist. Meist wird einleitend darauf hingewiesen, dass zur Vereindeutung Klammern gesetzt werden dürfen. Eine abstrakter Syntaxbaum für das obige Beispiel würde dann tatsächlich als a * (b + 3) niedergeschrieben. Im Kontext dieser Literatur liegt der Blick dabei aber stets auf dem Term. Wie erwähnt, werden die Grenzen zwischen Grammatik und Algebra durch ein Spiel mit der Form verwischt.

Ein typisches Beispiel sind die Ausdrücke im Lambda-Kalkül, deren abstrakte Grammatik oft nur knapp als $E:=\lambda X.E\,|\,EE\,|\,X$ niedergeschieben wird. Dieselbe Technik wird aber auch für umfangreiche Grammatiken eingesetzt.

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.
Hans Zima: Compilerbau I. Analyse. Bibliographisches Institut, Mannheim/Wien/Zürich 1982, ISBN 3-411-01644-2, 4.3 Abstrakte Bäume und ihre Attributierung, S. 216–229.
Hans Jürgen Heringer: Deutsche Syntax. Walter de Gruyter, Berlin/New York 1972, ISBN 3-11-004015-8, 1.6 Beschreibung von Sätzen mit dem Konstitutionssystem, S. 30–31.
Ulrich Engel: Syntax der deutschen Gegenwartssprache. Erich Schmidt Verlag, Berlin 1981, ISBN 3-503-01696-1, 1.10 Diagramme in der Grammatik, S. 42–43.