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!
