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 : 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
The ascending order is exactly the reversed order.