| Home Page | Recent Changes

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

The Unreal Engine Documentation Site

Wiki Community

Topic Categories

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

FAQs

Help Desk

Mapping Topics

Mapping Lessons

UnrealEd Interface

UnrealScript Topics

UnrealScript Lessons

Making Mods

Class Tree

Modeling Topics

Chongqing Page

Log In