Parse Trees and AST's

Top  Previous  Next

Glossary > Parse Trees and AST's


In tree structures the input text can be represented with a structure that conforms to the grammar.  Such a tree is called a parse trees or AST (abstract syntax tree).

The advantages of a previous creation of such parse trees in contrast to an immediate translation (one-pass compiler) is:


You can make multiple passes over the data without having to re-parse the input.
You can first perform transformations on the tree itself.
You can evaluate things in any order you want.


Generally spoken, a tree consists of a number of nodes, connected to each other.


In the following picture a tree structure is depicted, as the variable inspector shows it.





This picture shall demonstrate the relationships of the nodes.


Each node, which has a child, is marked by a little square; the leafs of the tree don't have such a square. A colon and the value of the node follow the label. All node in the picture have the same label: element; only the root node at the top of the tree has the label: document.


If you pick out the node with the value Program_Info following relationships exist:


Parent-node is: element : XML_DIZ_INFO

first Child node is : element : Program_Name

last Child node is: element : File_Info

next Sibling node not exists.

previous Sibling node is: element : Company_Info

first Sibling node is: element : Company_Info.

last Sibling node is: element : Program_Info

bottom first Child node is: CharData : TextTransformer

bottom last Child node is : CharData : 3.86


For the root node

bottom first Child node is: CharData : Detlef Meyer-Eltz

bottom last Child node is : CharData : 3.86



Walk through a tree


A walk through the tree can be done in descending or ascending order. The descending order goes exactly parallel to the line numbers, in which the nodes appear in the picture above. Beginning with the root node:


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 :

element : Program_Info

element : Program_Name

CharData : TextTransformer

element : Program_Version

CharData :

element : File_Info

element : File_Size_MB

CharData : 3.86


The ascending order is exactly the reversed order.


This page belongs to the TextTransformer Documentation

Home  Content  German