C
AST
Learn to build an Abstract Syntax Tree (AST).
What is an AST?
An AST (abstract syntax tree) is a tree that captures the structure of the source code. Each inner node is an operation; each leaf is a value. It is the parser's main output.
For example 2 + 3 * 4 reduces to three nodes: root +, left child 2, right child *. The children of * are 3 and 4. The AST encodes precedence structurally; no parentheses are needed. Later compiler stages walk this tree. Each node is a struct with type, value and child pointers.
Tree traversal
To process an AST three traversal orders are common: preorder (root first), inorder (root middle) and postorder (root last). Each order suits a different purpose.
Preorder fits code generation that analyses expressions top-down. Postorder is used by interpreters that need children computed first. Inorder prints expressions like a human reads them. Traversal is written recursively: the function processes the root, then calls itself on the children (preorder). Each node type triggers a different action, so traversal code usually contains a switch.
Exercise Print AST nodes
Define struct ast_node { const char *op; int value; }. Define void print_ast(struct ast_node n) with body printf("[%s]%d\n", n.op, n.value);. In main declare three nodes: {"+", 0}, {"num", 42}, {"num", 7} and print each with print_ast.
Show example solution
#include <stdio.h>
struct ast_node { const char *op; int value; };
void print_ast(struct ast_node n) {
printf("[%s]%d\n", n.op, n.value);
}
int main(void) {
struct ast_node root = {"+", 0};
struct ast_node left = {"num", 42};
struct ast_node right = {"num", 7};
print_ast(root);
print_ast(left);
print_ast(right);
return 0;
}
Test yourself
-
Complete the AST child access
struct ast_node *left = node->____;
Show answer
struct ast_node *left = node->left;
-
Match traversal orders
- preorder
- Root first
- inorder
- Root middle
- postorder
- Root last
- level-order
- Layer by layer
-
What does an AST node typically contain?
- Only a value
- Only a type
- Type and child nodes
- Only text
Show answer
Type and child nodes — A node type and child pointers are the AST's foundation.
Next lesson: Code generation
