| Home Page | Recent Changes | Preferences

# 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

Image Uploads

Random Page

Recent Changes

Offline Wiki

Unreal Engine

Console Commands

Terminology

Mapping Topics

Mapping Lessons

UnrealEd Interface

Questions&Answers

Scripting Topics

Scripting Lessons

Making Mods

Class Tree

Questions&Answers

Modeling Topics

Questions&Answers

Log In