BruteForce/AST

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);
  }
}