Syntaxbaum - LinkFang.de





Syntaxbaum


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 [math]G = \left( N, \Sigma, P, S \right)[/math]. Ein Ableitungsbaum dazu ist ein Baum, dessen Knoten mit Symbolen aus [math]\Sigma\cup N\cup\{\varepsilon\}[/math] (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 [math]S[/math] beschriftet. Diese Eigenschaft wird gelegentlich nicht verlangt. Ein Baum, der sie erfüllt, wird als vollständiger Ableitungsbaum bezeichnet.
  • Wenn die Kinder eines mit [math]A[/math] beschrifteten inneren Knotens mit den Symbolen [math]z_1,\ldots,z_m[/math] (in dieser Reihenfolge) beschriftet sind, muss die Grammatik die Regel [math]A \to z_1\ldots z_m[/math] enthalten.
  • Die Blätter des Baumes sind mit Symbolen aus [math]\Sigma\cup\{\varepsilon\}[/math] beschriftet.
  • Ist ein Blatt mit [math]\varepsilon[/math] 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 [math]G = \left( V, T, P, S \right)[/math] verwendet.[1]

Konstruktion

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

Zu einer gegebenen Ableitung ohne [math]\varepsilon[/math]-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

Wir betrachten eine Grammatik mit dem Startsymbol [math]S[/math] und den folgenden Regeln:

[math]\begin{matrix}S&\to&AB\\ A&\to&aA\\ A&\to&\varepsilon\\ B&\to&b\end{matrix}[/math]

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

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

[math]S \Rightarrow AB \Rightarrow aAB \Rightarrow aaAB \Rightarrow aaB \Rightarrow aab [/math]

und die Rechtsableitung

[math]S \Rightarrow AB \Rightarrow Ab \Rightarrow aAb \Rightarrow aaAb \Rightarrow aab.[/math]

Einzelnachweise

  1. Informatik für Ing. I -Folien,Prof. Dr.-Ing. Richard Lenz,Lehrstuhl für Informatik 6 (Datenmanagement) Friedrich-Alexander-Universität Erlangen-Nürnberg

Kategorien: Compilerbau | Theorie formaler Sprachen

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Syntaxbaum (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.