Syntaxbaum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel oder Abschnitt bedarf einer Überarbeitung: Belege fehlen
Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.

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 . Ein Ableitungsbaum dazu ist ein Baum, dessen Knoten mit Symbolen aus (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 beschriftet. Diese Eigenschaft wird gelegentlich nicht verlangt. Ein Baum, der sie erfüllt, wird als vollständiger Ableitungsbaum bezeichnet.
  • Wenn die Kinder eines mit beschrifteten inneren Knotens mit den Symbolen (in dieser Reihenfolge) beschriftet sind, muss die Grammatik die Regel enthalten.
  • Die Blätter des Baumes sind mit Symbolen aus beschriftet.
  • Ist ein Blatt mit 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 verwendet.

Konstruktion[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Zu einer gegebenen Ableitung ohne -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[Bearbeiten | Quelltext bearbeiten]

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

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

Parse-tree.svg

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

und die Rechtsableitung