Glossar > Parse Trees and AST's
In einer Baumstruktur kann der Eingabetext in einer der Grammatik entsprechenden Struktur abgebildet werden. Ein derartiger Baum wird Parse tree oder AST (abstract syntax tree) genannt.
Der Vorteil der Erzeugung solcher Baumstrukturen gegenüber der unmittelbaren Übersetzung (one-pass compiler) ist:
| • | Die Daten können mehrmals durchgegangen werden, ohne die Eingabe erneut zu parsen. |
| • | Transformationen können zunächst am Baum selbst durchgeführt werden. |
| • | Auswertungen können in beliebiger Folge durchgeführt werden. |
Allgemein besteht ein Baum aus einer Anzahl miteinander verknüpfter Knoten (node).
In der folgenden Abbildung ist eine Baumstruktur zu sehen, wie sie im Variablen-Inspektor angezeigt werden kann.
An Hand dieser Abbildung sollen die Verhältnisse der Knoten zueinander veranschaulicht werden.
Jeder Knoten, der Kind-Knoten besitzt, ist durch ein kleines Quadrat gekennzeichnet, die Blätter des Baums besitzen kein solches Quadrat. Die Beschriftung der Knoten besteht aus ihrem Label, gefolgt von einem Doppelpunkt und ihrem Wert. In der Abbildung haben alle Knoten bis auf einen das gleiche Label: element.
Wurzel- oder Root-Knoten des Baums ist der Knoten an der Spitze des Baums mit dem label: document.
Greift man den Knoten mit dem Wert Program_Info heraus, so steht er in folgenden Beziehungen:
Eltern- oder Parent-Knoten ist: element : XML_DIZ_INFO
Erster Kind- bzw. first Child-Knoten ist : element : Program_Name
Letzter Kind- bzw. last Child-Knoten ist: element : File_Info
Nächster Geschwister- bzw. next Sibling-Knoten gibt es nicht.
Vorheriger Geschwister- bzw. previous Sibling-Knoten ist: element : Company_Info
Erster Geschwister- bzw. first Sibling-Knoten ist: element : Company_Info.
Letzter Geschwister- bzw. last Sibling-Knoten ist: element : Program_Info
Unterster erster Kind- bzw. bottom first Child-Knoten ist: CharData : TextTransformer
Unterster letzter Kind- bzw. bottom last Child-Knoten ist : CharData : 3.86
Vom Wurzelknoten aus betrachtet ist
Unterster erster Kind- bzw. bottom first Child-Knoten ist: CharData : Detlef Meyer-Eltz
Unterster letzter Kind- bzw. bottom last Child-Knoten ist : CharData : 3.86
Durchlaufen eines Baums
Ein Baum kann in ab- oder aufsteigender Richtung durchlaufen werden. Beginnend mit dem Wurzelknoten werden die Knoten in absteigender Richtung genau in der Reihenfolge besucht, die ihrer Zeilennummer in obiger Abbildung entspricht:
document :
element : XML_DIZ_INFO
element : Company_Info
element : Company_Name
CharData : Detlef Meyer-Eltz
element : City_Town
CharData : Hamburg
element : Country
CharData : Germany
element : Contact_Info
element : Author_Email
CharData : dme@texttransformer.com
element : Program_Info
element : Program_Name
CharData : TextTransformer
element : Program_Version
CharData : 0.9.7.9
element : File_Info
element : File_Size_MB
CharData : 3.86
In aufsteigender Richtung ist die Folge genau umgekehrt.