I search for solutions in this order: Past Code, Unreal Source, Wiki, BUF, groups.yahoo, google, screaming at monitor. – RegularX
Legacy:BruteForce/AST
From Unreal Wiki, The Unreal Engine Documentation Site
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);
}
}
