CompilersIntermediate RepresentationHard

Translate an AST into Your IR

Master the fundamental concepts of intermediate representation through this focused micro-challenge.

~90 minutes Intermediate Representation Ready to learn

Topic Overview

Lowering AST to IR

Code generation traditionally walks the AST and emits IR instructions. Clang's CodeGenFunction::EmitStmt and LLVM's IRBuilder follow this pattern: recursive descent on the tree, emitting instructions as you return from subtrees. Expression results land in temporaries.

Post-Order Walk

For a + b, generate code for a and b first, obtaining operands, then emit t = a + b. For statements, emit side-effecting instructions in order. Control flow creates labels and conditional branches.

c
Loading…

Each expression node yields an operand (temp, var, or const)
Short-circuit && needs labels, not naive eager eval
Declarations may emit alloca or variable binding
Attach IR to function nodes, not just expressions

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 translate an AST into your IR by walking the tree and emitting instructions. This exercise requires implementing the lowering pass that converts expressions and statements into a linear instruction list.

Implementation Task

Your Task

Write the syntax-directed translator that turns statements into three-address code (the TAC format from Design a Simple 3-Address Code IR, plus return a). Every compiler front end ends with a pass like this.

Input

Statements on stdin (any layout):

c
Loading…

Binary operators are left-associative; else binds to the nearest if.

Translation scheme (follow it exactly)

Translating an expression yields an atom (a name or number) and may emit instructions:

a number or name: no code; the atom is itself.
e1 OP e2: translate e1, then e2, then allocate a new temporary tN and emit tN = a1 OP a2.
- e: translate e, then allocate tN and emit tN = 0 - a.

Temporaries are t1, t2, … and labels L1, L2, …, each numbered in allocation order across the whole program.

Statement	Code
`x = e;`	code(e); `x = a`
`return e;`	code(e); `return a`
`if (c) S`	allocate `Lend`; code(c); `ifFalse a goto Lend`; S; `Lend:`
`if (c) S1 else S2`	allocate `Lelse`, then `Lend`; code(c); `ifFalse a goto Lelse`; S1; `goto Lend`; `Lelse:`; S2; `Lend:`
`while (c) S`	allocate `Lstart`, then `Lend`; `Lstart:`; code(c); `ifFalse a goto Lend`; S; `goto Lstart`; `Lend:`
`{ S1 S2 … }`	the statements in order

Labels are allocated when the statement starts, before any of its parts are translated.

Output

The TAC, one instruction per line, in the canonical spelling of the TAC task (x = a + b, L1:, goto L1, ifFalse a goto L1, return a), then temps=T labels=L.

Example

Input:

c
Loading…

Output:

c
Loading…

Requirements

Build (or walk) an AST and translate it with one recursive function for expressions and one for statements: no global rewriting afterwards.
new_temp() and new_label() counters shared by the whole program.

Hidden tests cover nested loops and conditionals, dangling else, unary minus on sub-expressions, and deep parenthesisation.