47

I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice way to input a token/string as I'm parsing some code.

For example, when I looked at diagrams of AST's, the variable and its value were leaf nodes to an equal sign. This makes perfect sense to me, but how would I go about implementing this? I guess I can do it case by case, so that when I stumble upon an "=" I use that as a node, and add the value parsed before the "=" as the leaf. It just seems wrong, because I'd probably have to make cases for tons and tons of things, depending on the syntax.

And then I came upon another problem, how is the tree traversed? Do I go all the way down the height, and go back up a node when I hit the bottom, and do the same for it's neighbor?

I've seen tons of diagrams on ASTs, but I couldn't find a fairly simple example of one in code, which would probably help.

  • The key concept you're missing is recursion. Recursion is kind of counterintuitive, and it's different for every learner when it will finally 'click' with them, but without recursion, there is simply no way to understand parsing (and a whole lot of other computational topics as well). – Kilian Foth Aug 22 '14 at 6:05
  • I get recursion, I just thought it'd be hard to implement it in this case. I actually wanted to use recursion and I ended up with a lot of cases that wouldn't work for a general solution. Gdhoward's answer is helping me a lot right now. – Howcan Aug 22 '14 at 6:07
  • It might be exercise to build an RPN calculator as an exercise. It will not answer your question but might teach some necessary skills. – user22815 Aug 22 '14 at 19:56
  • I actually have built an RPN Calculator before. The answers helped me a lot and I think I can make a basic AST now. Thanks! – Howcan Aug 22 '14 at 20:12
47

The short answer is that you use stacks. This is a good example, but I'll apply it to an AST.

FYI, this is Edsger Dijkstra's Shunting-Yard Algorithm.

In this case, I will use an operator stack and an expression stack. Since numbers are considered expressions in most languages, I'll use the expression stack to store them.

class ExprNode:
    char c
    ExprNode operand1
    ExprNode operand2

    ExprNode(char num):
        c = num
        operand1 = operand2 = nil

    Expr(char op, ExprNode e1, ExprNode e2):
        c = op
        operand1 = e1
        operand2 = e2

# Parser
ExprNode parse(string input):
    char c
    while (c = input.getNextChar()):
        if (c == '('):
            operatorStack.push(c)

        else if (c.isDigit()):
            exprStack.push(ExprNode(c))

        else if (c.isOperator()):
            while(operatorStack.top().precedence >= c.precedence):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            operatorStack.push(c)

        else if (c == ')'):
            while (operatorStack.top() != '('):
                operator = operatorStack.pop()
                # Careful! The second operand was pushed last.
                e2 = exprStack.pop()
                e1 = exprStack.pop()
                exprStack.push(ExprNode(operator, e1, e2))

            # Pop the '(' off the operator stack.
            operatorStack.pop()

        else:
            error()
            return nil

    # There should only be one item on exprStack.
    # It's the root node, so we return it.
    return exprStack.pop()

(Please be nice about my code. I know it's not robust; it's just supposed to be pseudocode.)

Anyway, as you can see from the code, arbitrary expressions can be operands to other expressions. If you have the following input:

5 * 3 + (4 + 2 % 2 * 8)

the code I wrote would produce this AST:

     +
    / \
   /   \
  *     +
 / \   / \
5   3 4   *
         / \
        %   8
       / \
      2   2

And then when you want to produce the code for that AST, you do a Post Order Tree Traversal. When you visit a leaf node (with a number), you generate a constant because the compiler needs to know the operand values. When you visit a node with an operator, you generate the appropriate instruction from the operator. For example, the '+' operator gives you an "add" instruction.

  • This works for operators that have left to right associativity, not right to left. – Simon Dec 5 '15 at 19:04
  • @Simon, it would be extremely simple to add the capability for right-to-left operators. The simplest would be to add a look up table and if an operator right-to-left, simply reverse the order of the operands. – Gavin Howard Dec 6 '15 at 19:51
  • 4
    @Simon If you want to support both, you're better off looking up the shunting yard algorithm in its full glory. As algorithms go, that's an absolute cracker. – biziclop Feb 9 '16 at 15:42
19

There is a significant difference between how an AST is typically depicted in test (a tree with numbers/variables at the leaf nodes and symbols at interior nodes) and how it is actually implemented.

The typical implementation of an AST (in an OO language) makes heavy use of polymorphism. The nodes in the AST are typically implemented with a variety of classes, all deriving from a common ASTNode class. For each syntactical construct in the language you are processing, there will be a class for representing that construct in the AST, such as ConstantNode (for constants, such as 0x10 or 42), VariableNode (for variable names), AssignmentNode (for assignment operations), ExpressionNode (for generic expressions), etc.
Each specific node type specifies if that node has children, how many and possibly of what type. A ConstantNode will typically have no children, an AssignmentNode will have two and a ExpressionBlockNode can have any number of children.

The AST gets built by the parser, who knows what construct it has just parsed, so it can construct the right kind of AST Node.

When traversing the AST, the polymorphism of the nodes comes really into play. The base ASTNode defines the operations that can be performed on the nodes, and each specific node type implements those operations in the specific way for that particular language construct.

9

Building the AST from the source text is "simply" parsing. How exactly it is done depends upon the parsed formal language and the implementation. You could use parser generators like menhir (for Ocaml), GNU bison with flex, or ANTLR etc etc. It is often done "manually" by coding some recursive descent parser (see this answer explaining why). The contextual aspect of parsing is often done elsewhere (symbol tables, attributes, ....).

However, in practice AST are much more complex than what you believe. For instance, in a compiler like GCC the AST keeps source location information and some typing information. Read about Generic Trees in GCC and look inside its gcc/tree.def. BTW, look also inside GCC MELT (which I have designed & implemented), it is relevant to your question.

  • I'm making an Lua interpreter to parse source text and transform in an array in JS. Can I consider it an AST? I'm supposed to do something like this: --My comment #1 print("Hello, ".."world.") transforms to ` [ { "type":"--", "content":"My comment #1" }, { "type":"call", "name":"print", "arguments":[ [ { "type":"str", "action":"..", "content":"Hello, " }, { "type":"str", "content":"world." } ] ] } ]` I think it's much more simpler in JS than any other language ! – Hydroper Feb 9 '16 at 14:47
  • @TheProHands This would be considered tokens, not an AST. – YoYoYonnY Sep 24 '16 at 15:20
2

I know this question is 4+ years old but I feel I should add a more detailed answer.

Abstract Syntax Trees are created no differently from other trees; the more true statement in this case is that Syntax Tree nodes have a variadic amount of nodes AS NEEDED.

An example is binary expressions like 1 + 2 A simple expression like that would create a single root node holding a right and left node that holds the data about the numbers. In C language, it'd look something like

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod,
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

Your question was also how to traverse? Traversing in this case is called Visiting Nodes. Visiting each Node requires that you use each node type to determine how to evaluate each Syntax node's data.

Here's another example of that in C where I simply print the contents of each node:

void AST_PrintNode(const ASTNode *node)
{
    if( !node )
        return;

    char *opername = NULL;
    switch( node->Type ) {
        case AST_IntVal:
            printf("AST Integer Literal - %lli\n", node->Data->llVal);
            break;
        case AST_Add:
            if( !opername )
                opername = "+";
        case AST_Sub:
            if( !opername )
                opername = "-";
        case AST_Mul:
            if( !opername )
                opername = "*";
        case AST_Div:
            if( !opername )
                opername = "/";
        case AST_Mod:
            if( !opername )
                opername = "%";
            printf("AST Binary Expr - Oper: \'%s\' Left:\'%p\' | Right:\'%p\'\n", opername, node->Data->BinaryExpr.left, node->Data->BinaryExpr.right);
            AST_PrintNode(node->Data->BinaryExpr.left); // NOTE: Recursively Visit each node.
            AST_PrintNode(node->Data->BinaryExpr.right);
            break;
    }
}

Notice how the function recursively visits each node according to what type of node we're dealing with.

Let's add a more complex example, an if statement construct! Recall that if statements can also have an optional else clause. Let's add the if-else statement to our original node structure. Remember that if statements themselves can also have if statements, so a kind of recursion within our node system can occur. Else statements are optional so the elsestmt field can be NULL which the recursive visitor function can ignore.

struct ASTNode;
union SyntaxNode {
    int64_t         llVal;
    uint64_t        ullVal;
    struct {
        struct ASTNode *left, *right;
    } BinaryExpr;
    struct {
        struct ASTNode *expr, *stmt, *elsestmt;
    } IfStmt;
};

enum SyntaxNodeType {
    AST_IntVal, AST_Add, AST_Sub, AST_Mul, AST_Div, AST_Mod, AST_IfStmt, AST_ElseStmt, AST_Stmt
};

struct ASTNode {
    union SyntaxNode *Data;
    enum SyntaxNodeType Type;
};

back in our node visitor print function called AST_PrintNode, we can accommodate the if statement AST construct by adding this C code:

case AST_IfStmt:
    puts("AST If Statement\n");
    AST_PrintNode(node->Data->IfStmt.expr);
    AST_PrintNode(node->Data->IfStmt.stmt);
    AST_PrintNode(node->Data->IfStmt.elsestmt);
    break;

As simple as that! In conclusion, the Syntax Tree is not much more than a tree of a tagged union of the tree and its data itself!

protected by gnat Mar 23 '18 at 6:08

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.