Syntax Trees as Intermediate Representation

Guide to syntax trees and abstract syntax trees as intermediate representations in compilers, covering construction, traversal, differences from parse trees, and translation to three-address code.

Introduction

A syntax tree (or Abstract Syntax Tree — AST) is a tree representation of a program's structure where each internal node represents an operator or construct, and children represent operands or sub-constructs. Unlike parse trees that include all grammar symbols, syntax trees retain only the semantically meaningful structure, discarding syntactic sugar.

Parse Tree vs Syntax Tree (AST)

Grammar: E	E + T \| T, T → T * F \| F, F → (E) \| id
Expression	a + b * c
- Non-terminals that just pass through (E	T→F→id)

AST Node Types

Code example

typedef enum {
    NODE_CONST,      // constant value
    NODE_IDENT,      // variable/identifier
    NODE_BINOP,      // binary operation (+, -, *, /)
    NODE_UNARYOP,    // unary operation (-, !)
    NODE_ASSIGN,     // assignment
    NODE_IF,         // if-else statement
    NODE_WHILE,      // while loop
    NODE_CALL,       // function call
    NODE_BLOCK,      // statement block
    NODE_RETURN,     // return statement
} NodeType;

typedef struct ASTNode {
    NodeType type;
    union {
        int int_val;              // for NODE_CONST
        char* name;               // for NODE_IDENT
        struct {                   // for NODE_BINOP
            char op;
            struct ASTNode* left;
            struct ASTNode* right;
        } binop;
        struct {                   // for NODE_IF
            struct ASTNode* cond;
            struct ASTNode* then_branch;
            struct ASTNode* else_branch;
        } if_stmt;
    };
} ASTNode;

AST Construction During Parsing

Syntax-directed construction

Grammar rule AST action

─────────────────────────────────────────────────

E → E₁ + T E.node = new BinOp('+', E₁.node, T.node)

E → T E.node = T.node

T → T₁ * F T.node = new BinOp('*', T₁.node, F.node)

T → F T.node = F.node

F → ( E ) F.node = E.node

F → id F.node = new Ident(id.name)

F → num F.node = new Const(num.value)

Building AST for "3 + x * 2":

F → 3 node = Const(3)

T → F node = Const(3)

E → T node = Const(3)

F → x node = Ident("x")

T → F node = Ident("x")

F → 2 node = Const(2)

T → T * F node = BinOp('*', Ident("x"), Const(2))

E → E + T node = BinOp('+', Const(3), BinOp('*', Ident("x"), Const(2)))

Final AST

[+]

/ \

[3] [*]

/ \

["x"] [2]

AST for Control Structures

Example

Source: if (x > 0) { y = x; } else { y = -x; } AST: [IF] / | \ [>] [BLOCK] [BLOCK] / \ | | [x] [0] [=] [=] / \ / \ [y] [x] [y] [NEG] | [x] Source: while (i < n) { sum += a[i]; i++; } AST: [WHILE] / \ [<] [BLOCK] / \ / \ [i] [n] [+=] [++] / \ | [sum] [INDEX] [i] / \ [a] [i]

Translating AST to Three-Address Code

Algorithm	Post-order traversal with code emission
emit(f"{true_label}	")
emit(f"{end_label}	")
Example	translate(BinOp('+', Const(3), BinOp('*', Ident("x"), Const(2))))
translate(*)	"t1 = x * 2", returns "t1"
translate(+)	"t2 = 3 + t1", returns "t2"

AST Optimizations

Constant folding on AST

Before: [+] After: [7]

/ \

[3] [4]

Algebraic simplification

Before: [*] After: [x]

/ \

[x] [1]

Dead subtree elimination

Before: [IF] After: [BLOCK]

/ | \ |

[true] [A] [B] [A]

Common subtree identification (leads to DAG)

Before: [+] After: [+]

/ \ / \

[*] [*] [*] [*] → same node (DAG)

/ \ / \ / \

[a][b][a][b] [a] [b]

Interview Questions

Q: Why do compilers use ASTs instead of parse trees?

A: Parse trees contain redundant nodes for grammar rules that don't contribute to semantics (unit productions like E→T→F→id). ASTs keep only meaningful operators and operands, making subsequent analysis and optimization simpler, more efficient, and language-grammar-independent.

Q: How does the AST relate to other intermediate representations?

A: The AST is typically the first IR produced (during parsing). It's then lowered to three-address code or SSA form for optimization. Some compilers optimize directly on the AST (source-level optimizations like constant folding), then translate to lower IRs. The AST preserves high-level structure that lower IRs lose.

Q: Can an AST represent programs with goto statements?

A: Yes, but awkwardly. Goto creates cross-references in the tree that break the hierarchical structure. Most modern AST designs represent gotos as labeled statements with goto nodes referencing label names. The control flow graph (CFG) is a better representation for analyzing programs with arbitrary jumps.

Q: How are operator precedence and associativity encoded in an AST?

A: Through tree structure. Higher-precedence operators appear deeper (as children of lower-precedence operators). In a+b*c, the * node is a child of +, so it's evaluated first. Left-associativity means a-b-c becomes (-(-,a,b),c) — left subtree computed first.

Q: What is the space complexity of an AST compared to source code?

A: An AST typically uses 5-10x more memory than the source text because each token becomes a node with pointers, type information, and source location. For a 1MB source file, the AST might be 5-10MB. This is why large codebases use incremental parsing and AST compression techniques.

Introduction

Parse Tree vs Syntax Tree (AST)

Grammar: E	E + T \| T, T → T * F \| F, F → (E) \| id
Expression	a + b * c
- Non-terminals that just pass through (E	T→F→id)

AST Node Types

Code example

typedef enum {
    NODE_CONST,      // constant value
    NODE_IDENT,      // variable/identifier
    NODE_BINOP,      // binary operation (+, -, *, /)
    NODE_UNARYOP,    // unary operation (-, !)
    NODE_ASSIGN,     // assignment
    NODE_IF,         // if-else statement
    NODE_WHILE,      // while loop
    NODE_CALL,       // function call
    NODE_BLOCK,      // statement block
    NODE_RETURN,     // return statement
} NodeType;

typedef struct ASTNode {
    NodeType type;
    union {
        int int_val;              // for NODE_CONST
        char* name;               // for NODE_IDENT
        struct {                   // for NODE_BINOP
            char op;
            struct ASTNode* left;
            struct ASTNode* right;
        } binop;
        struct {                   // for NODE_IF
            struct ASTNode* cond;
            struct ASTNode* then_branch;
            struct ASTNode* else_branch;
        } if_stmt;
    };
} ASTNode;

AST Construction During Parsing

Syntax-directed construction

Grammar rule AST action

─────────────────────────────────────────────────

E → E₁ + T E.node = new BinOp('+', E₁.node, T.node)

E → T E.node = T.node

T → T₁ * F T.node = new BinOp('*', T₁.node, F.node)

T → F T.node = F.node

F → ( E ) F.node = E.node

F → id F.node = new Ident(id.name)

F → num F.node = new Const(num.value)

Building AST for "3 + x * 2":

F → 3 node = Const(3)

T → F node = Const(3)

E → T node = Const(3)

F → x node = Ident("x")

T → F node = Ident("x")

F → 2 node = Const(2)

T → T * F node = BinOp('*', Ident("x"), Const(2))

E → E + T node = BinOp('+', Const(3), BinOp('*', Ident("x"), Const(2)))

Final AST

[+]

/ \

[3] [*]

/ \

["x"] [2]

AST for Control Structures

Example

Translating AST to Three-Address Code

Algorithm	Post-order traversal with code emission
emit(f"{true_label}	")
emit(f"{end_label}	")
Example	translate(BinOp('+', Const(3), BinOp('*', Ident("x"), Const(2))))
translate(*)	"t1 = x * 2", returns "t1"
translate(+)	"t2 = 3 + t1", returns "t2"

AST Optimizations

Constant folding on AST

Before: [+] After: [7]

/ \

[3] [4]

Algebraic simplification

Before: [*] After: [x]

/ \

[x] [1]

Dead subtree elimination

Before: [IF] After: [BLOCK]

/ | \ |

[true] [A] [B] [A]

Common subtree identification (leads to DAG)

Before: [+] After: [+]

/ \ / \

[*] [*] [*] [*] → same node (DAG)

/ \ / \ / \

[a][b][a][b] [a] [b]

Interview Questions

Q: Why do compilers use ASTs instead of parse trees?

Q: How does the AST relate to other intermediate representations?

Q: Can an AST represent programs with goto statements?

Q: How are operator precedence and associativity encoded in an AST?

Q: What is the space complexity of an AST compared to source code?

Syntax Trees as Intermediate Representation

Introduction

Parse Tree vs Syntax Tree (AST)

AST Node Types

AST Construction During Parsing

Syntax-directed construction

Final AST

AST for Control Structures

Translating AST to Three-Address Code

AST Optimizations

Constant folding on AST

Algebraic simplification

Dead subtree elimination

Common subtree identification (leads to DAG)

Interview Questions

Continue learning this concept

Syntax Trees as Intermediate Representation

Introduction

Parse Tree vs Syntax Tree (AST)

AST Node Types

AST Construction During Parsing

Syntax-directed construction

Final AST

AST for Control Structures

Translating AST to Three-Address Code

AST Optimizations

Constant folding on AST

Algebraic simplification

Dead subtree elimination

Common subtree identification (leads to DAG)

Interview Questions

Continue learning this concept