Ableitungsbaum

Ein Syntax-, Ableitungs- oder Parsebaum ist ein Begriff aus der theoretischen Informatik und bezeichnet eine baumförmige Darstellung einer Ableitung.

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 z1,...,zm (in dieser Reihenfolge) beschriftet sind, muss die Grammatik die Regel A \to z_1...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.

Die inneren Knoten sind also genau die mit Nichtterminalsymbolen beschrifteten Knoten; die Blätter sind mit Terminalsymbolen oder dem leeren Wort beschriftet.

Zu einer gegebenen Ableitung 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:

                     S
                    / \
                   A   B
                  / \   \
                 a   A   b
                    / \
                   a   A
                        \
                         \varepsilon

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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Parsebaum — Ein Syntax , Ableitungs oder Parsebaum ist ein Begriff aus der theoretischen Informatik und bezeichnet eine baumförmige Darstellung einer Ableitung. Man betrachte eine kontextfreie Grammatik . Ein Ableitungsbaum dazu ist ein Baum, dessen Knoten… …   Deutsch Wikipedia

  • Syntaxbaum — Ein Syntax , Ableitungs oder Parsebaum ist ein Begriff aus der theoretischen Informatik und bezeichnet eine baumförmige Darstellung einer Ableitung. Man betrachte eine kontextfreie Grammatik . Ein Ableitungsbaum dazu ist ein Baum, dessen Knoten… …   Deutsch Wikipedia

  • PumpingLemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Pumping Lemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Pumpinglemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Pumplemma — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Schleifensatz — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Uvw-Theorem — Das Pumping Lemma bzw. Pumplemma beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. In vielen Fällen lässt sich anhand des Lemmas nachweisen, dass eine formale Sprache nicht regulär bzw. nicht… …   Deutsch Wikipedia

  • Kontextfreie Grammatik — In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird …   Deutsch Wikipedia

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”