AST
- C course
- Expert
- Lesson 15/47
- 5 min
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.
Practice 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.
Starter code
#include <stdio.h>
// Define ast_node struct
// Define print_ast function and call it for three nodes
int main(void) {
return 0;
}Sample 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;
}Expected output
[+]0 [num]42 [num]7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Complete the AST child access
struct ast_node *left = node->____;struct ast_node *left = node->left;Explanation: node->left gives the left child.
2 Match traversal orders
| Term | Meaning |
|---|---|
preorder |
Root first |
inorder |
Root middle |
postorder |
Root last |
level-order |
Layer by layer |
3 What does an AST node typically contain?
- Only a value
- Only a type
- Type and child nodes Correct answer
- Only text
Explanation: A node type and child pointers are the AST's foundation.