Example tree
It's wise to write a function to draw the current AST, this way you can easily spot errors.
The PrintTree() below gives the following tree for this piece of code:
var int x; var int y; x = 1+2*3-5; y = (x+2)/5; print(""+x+" "+y);
+– var | +– int | +– x +– var | +– int | +– y +– = | +– x | +– - | | +– + | | | +– 1 | | | +– * | | | | +– 2 | | | | +– 3 | | +– 5 +– = | +– y | +– / | | +– + | | | +– x | | | +– 2 | | +– 5 +– print | +– + | | +– + | | | +– + | | | | +– | | | | +– x | | | +– | | +– y
The code
/** The compiled code ready to be executed */ class AST extends Object config(BruteForce); enum NodeType { NT_Keyword, NT_Identifier, NT_String, NT_Integer, NT_Float, NT_Boolean, NT_Function, };
These are the kind of tree nodes we have in the tree. The most important is the NT_Keyword, this defines a piece of code to execute, it's usualy a root node.
struct Node { var NodeType type; var string value; var int parent; var array<int> children; }; var config array<Node> Tree;
A tree is simply an array with all nodes, each node has pointers to it's children and a pointer to it's parent. These pointers are actualy just the index in the array.
var private int currentNode;
The current root node
function Create() { Tree.length = 0; currentNode = -1; } /** The real add node */ private function int AddNode(NodeType inType, string inValue, int inParent) { local int i; i = Tree.length; Tree.length = i+1; Tree[i].type = inType; Tree[i].value = inValue; Tree[i].parent = inParent; if (inParent > -1) { Tree[inParent].children.length = Tree[inParent].children.length+1; Tree[inParent].children[Tree[inParent].children.length-1] = i; } return i; }
This will add a node to the tree, and as child to it's parent (when set).
/** Open a new Root to the tree */ function AddRoot(NodeType inType, string inValue) { currentNode = AddNode(inType, inValue, currentNode); }
This will add a new node and set the current root node to the newly added node.
/** Close a Root node */ function CloseRoot() { currentNode = Tree[currentNode].parent; }
Close the current root by setting the root node to the previous root node.
/** Add a child to the current node, doesn't set a new root */ function AddChild(NodeType inType, string inValue) { AddNode(inType, inValue, currentNode); } /** Move previous node down a notch */ function SwitchNode() { local int lastSib; // set new parent lastSib = Tree[Tree[currentNode].parent].children[Tree[Tree[currentNode].parent].children.length-2]; Tree[currentNode].children.length = Tree[currentNode].children.length+1; Tree[currentNode].children[Tree[currentNode].children.length-1] = lastSib; // remove child pointer from previous parent Tree[Tree[lastSib].parent].children.remove(Tree[Tree[lastSib].parent].children.length-2 ,1); }
This will move the previous node added to a child of the last added root node
/** Print the tree */ function PrintTree() { local int i; for (i = 0; i < Tree.length; i++) { if (Tree[i].parent == -1) PrintSubTree(i, 0); } }
This will make an ASCII drawing of the current state of the AST, as you can see above.
/** Internal function for printing the tree */ private function PrintSubTree(int root, int depth) { local int i; local string tmp; for (i = 0; i < depth; i++) tmp = tmp$"| "; Log(tmp$"+--"@Tree[root].value); for (i = 0; i < Tree[root].children.length; i++) { PrintSubTree(Tree[root].children[i], depth+1); } }