CompilersCode GenerationMedium

Three-Address Code IR

Master the fundamental concepts of code generation through this focused micro-challenge.

~45 minutes Code Generation Ready to learn

Topic Overview

Generating TAC from the AST

This task bridges tree-shaped ASTs to flat instruction lists. GCC's GIMPLE lowering and LLVM's IRBuilder::CreateAdd both flatten expressions into temporaries. Stack machines like JVM bytecode are three-address code with implicit operand stacks.

Recursive Code Generation

generate_expression returns the operand holding the result. For binary nodes, recurse on children, emit t = left op right, return t. Statements emit sequences: labels for control flow, param/call for functions.

c
Loading…

new_temp() allocates fresh temporaries
emit() appends to the instruction list
If/else needs labels, conditional jumps, and merge
Do not return placeholder constants; wire each node kind

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 implement a three-address code generator that walks the AST and emits instructions. This exercise requires generate_expression, generate_statement, and temporary allocation without stub placeholders that fake results.

Implementation Task

Your Task

Extend three-address code generation to the parts of expressions that need more than arithmetic: function calls (param / call), unary operators, and short-circuit && / ||, whose right operand must not be evaluated when the left one already decides the result.

Input

Statements on stdin (any layout):

c
Loading…

Translation scheme (follow it exactly)

Translating an expression yields an atom (a name, number or temporary) and may emit code. Temporaries t1, t2, … and labels L1, L2, … are numbered in allocation order.

Expression	Code emitted	Atom
number / name	-	itself
`e1 OP e2`	code(e1); code(e2); then allocate `t`; `t = a1 OP a2`	`t`
`- e` / `! e`	code(e); allocate `t`; `t = - a` / `t = ! a`	`t`
`f(e1, …, en)`	code(e1) … code(en); `param a1` … `param an`; allocate `t`; `t = call f, n`	`t`
`e1 && e2`	code(e1); allocate `Lfalse`, `Lend`; `ifFalse a1 goto Lfalse`; code(e2); `ifFalse a2 goto Lfalse`; allocate `t`; `t = 1`; `goto Lend`; `Lfalse:`; `t = 0`; `Lend:`	`t`
`e1 \|\| e2`	code(e1); allocate `Ltrue`, `Lend`; `if a1 goto Ltrue`; code(e2); `if a2 goto Ltrue`; allocate `t`; `t = 0`; `goto Lend`; `Ltrue:`; `t = 1`; `Lend:`	`t`

&& binds tighter than ||, and both are left-associative: a && b && c is (a && b) && c.

Statements: x = e; → code(e); x = a. return e; → code(e); return a. e; → code(e) only (a call's result temporary is still allocated).

Output

The TAC, one instruction per line, then temps=T labels=L calls=C.

Example

Input:

c
Loading…

Output:

c
Loading…

g(x) is only evaluated when x < 10: that is what the jump around it guarantees.

Requirements

One translation function per precedence level, each returning the atom of its result.
Arguments are fully translated before any param is emitted, so nested calls never interleave their param sequences.

Hidden tests cover || mixed with &&, nested calls as arguments, zero-argument calls, ! and double negation, and call statements whose value is discarded.