CompilersSyntax AnalysisMedium

AST Node Structures

Master the fundamental concepts of syntax analysis through this focused micro-challenge.

~45 minutes Syntax Analysis Ready to learn

Topic Overview

ASTs Represent Syntax Trees

The parser's output is an abstract syntax tree: a tree of nodes for expressions, statements, and declarations. Clang builds Expr and Stmt subclasses; LLVM's frontend lowers from similar structures. Every semantic check and code generator walks this tree.

Node Design

Each AST node has a type tag, source location, and child pointers. Expression nodes cover literals, identifiers, binary/unary ops, and calls. Statement nodes cover assignments, if/while, return, and blocks. Keep the hierarchy shallow enough to traverse easily.

c
Loading…

Literals store numeric or string values
Binary nodes store operator and two children
If nodes store condition, then-branch, else-branch
Locations enable error messages in later phases

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will define AST node types and structures for expressions and statements. This exercise asks you to model the parse tree data layout that your parser builds and that semantic analysis traverses.

Implementation Task

Your Task

Design the AST node type a C compiler's parser will produce, with constructors, a printer, and a recursive destructor. There is no parser yet: instead, stdin is a small build script that tells you which nodes to construct, bottom-up, using a stack.

Input: the build script

One command per line. Each command creates one node. Commands that need children pop them from the stack; every command then pushes the new node.

Command	Node	Pops (top of stack is the last one listed)
`num N`	`LITERAL N`	-
`id NAME`	`IDENTIFIER NAME`	-
`unary OP`	`UNARY OP`	operand
`bin OP`	`BINARY OP`	left, right
`call NAME K`	`CALL NAME`	K arguments, first argument deepest
`expr`	`EXPR_STMT`	expression
`ret`	`RETURN`	value
`if`	`IF`	condition, then-branch
`ifelse`	`IF`	condition, then-branch, else-branch
`while`	`WHILE`	condition, body
`block K`	`BLOCK`	K statements, first statement deepest
`var NAME`	`VAR_DECL NAME`	initializer
`param NAME`	`PARAM NAME`	-
`func NAME K`	`FUNC_DECL NAME`	K params (first deepest), then body: K + 1 nodes in all

OP and NAME are single words without spaces. When the script ends, every node left on the stack becomes a child of one PROGRAM root, bottom of the stack first.

If a command needs more nodes than the stack holds, print error: line L: stack underflow to stdout (L is the 1-based line number of the command, counting every line), stop reading, and exit with status 0. Print nothing else: no tree and no nodes= line. A non-zero exit status fails the test even when the line is right.

Output

Print the tree depth-first, one node per line, indenting each level by two spaces. Children are printed in the order listed in the table (for CALL, BLOCK, FUNC_DECL: in their original order; a FUNC_DECL's params come before its body). Then:

c
Loading…

N counts every node including PROGRAM; D is the number of nodes on the longest root-to-leaf path (PROGRAM alone has depth 1).

Example

int x = 2 + 3; built bottom-up:

Input:

c
Loading…

Output:

c
Loading…

Requirements

One ASTNode struct with a node-type enum, a tagged union (or fields) for the literal value / name / operator, and a growable array of children.
Constructors per node kind, ast_print() and a recursive ast_destroy() that frees every node.

The visible tests cover every command and the underflow error. The hidden tests are variations on them: a function with two params, an if without else, a while nested in a block, a call with no arguments, and a func that underflows because it pops its body as well as its params.