Parse Trees and AST's

Top  Previous  Next

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.

 

 

node_tree

 

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.



Diese Seite gehört zur TextTransformer Dokumentation

Home  Inhalt  English