By the time a program has passed through lexical analysis, syntax analysis, and semantic analysis, the compiler has thoroughly verified that it is both structurally and meaningfully correct. What it does not yet have is anything close to executable code. The annotated syntax tree produced so far is a rich, verified representation of the program, but it is tightly bound to the specific grammar of the source language, which makes it an awkward starting point for generating code for a specific target machine. Intermediate code generation exists to bridge exactly this gap, transforming the verified program into a simpler, more uniform representation that sits conceptually between the source language and the final machine code.
This intermediate representation acts as a kind of universal middle ground. It is simple and regular enough that later phases, such as code optimization, can analyze and improve it without worrying about the quirks of the original source language, while still being general enough that it does not commit the compiler to any particular target machine's instruction set. This separation is one of the most important architectural decisions in compiler construction, and it directly enables the front end and back end separation discussed back in the very first tutorial of this series.
In this tutorial, you will learn why intermediate representations are used at all, the most common forms of intermediate code, including three-address code, quadruples, and triples, how expressions and control statements are translated into this form, and how intermediate code generation connects back to the syntax directed translation techniques covered earlier in this series.
It might seem simpler, at first glance, for a compiler to translate directly from the source language into target machine code in a single step, skipping any intermediate stage entirely. In practice, this approach creates serious engineering problems as soon as a compiler needs to support more than one source language, more than one target machine, or any meaningful degree of code optimization.
Compilers use several different styles of intermediate representation, each with its own trade-offs in terms of readability, compactness, and ease of manipulation. Three of the most commonly discussed forms are three-address code, quadruples, and triples, along with the syntax tree itself, which can also serve as a form of intermediate representation in its own right.
| Representation | Description |
|---|---|
| Syntax Tree | A tree-based representation, closely related to the parse tree, where each internal node represents an operation and each leaf represents an operand. |
| Three-Address Code | A linear sequence of simple instructions, each involving at most three operands, typically representing at most one operation per instruction. |
| Quadruples | A tabular representation of three-address code, where each instruction is stored as a record with an operator and up to three operand or result fields. |
| Triples | A more compact tabular representation that avoids naming temporary results explicitly, instead referring to earlier instructions by their position in the table. |
Three-address code is one of the most widely discussed intermediate representations in Compiler Design, and it was already introduced briefly in the earlier tutorial on the phases of a compiler. Its defining characteristic is that each instruction performs at most one operation and involves at most three operands, typically two source operands and one destination, which is where the name comes from.
Source Code: total = price * quantity + tax; Three-Address Code: t1 = price * quantity t2 = t1 + tax total = t2
Notice how the single, more complex source statement has been broken down into a sequence of simple steps, each involving only one operation. This uniformity is exactly what makes three-address code so convenient for later phases of the compiler, since every instruction has a predictable, simple shape that is easy to analyze and transform.
Although three-address code is simple in structure, it needs to be expressive enough to represent every construct found in a real programming language. This is achieved through a small set of common instruction types.
| Instruction Type | Example |
|---|---|
| Assignment with a binary operation | t1 = a + b |
| Assignment with a unary operation | t1 = - a |
| Simple copy from one variable to another | a = t1 |
| Unconditional jump to another instruction | goto L1 |
| Conditional jump based on a comparison | if a < b goto L1 |
| Procedure or function call handling | param a; call sum, 2; t1 = result |
These few instruction types, used in combination, are sufficient to represent arithmetic expressions, assignments, conditional statements, loops, and function calls, which together cover the vast majority of constructs found in typical procedural programming languages.
Translating an expression into three-address code follows naturally from the synthesized attribute techniques introduced in the syntax directed translation tutorial. As the compiler processes an expression, it generates a temporary variable to hold the result of each operation, using the temporaries or identifiers already computed for the sub-expressions as operands.
Source Expression: result = (a + b) * (c - d); Generated Three-Address Code: t1 = a + b t2 = c - d t3 = t1 * t2 result = t3
This translation mirrors the structure of the annotated parse tree for the expression almost exactly, with each internal node of the tree corresponding to one instruction in the generated code, and the order of instructions following a bottom-up traversal of that tree, consistent with the synthesized attribute evaluation order discussed previously.
Control statements, such as conditional statements and loops, are translated into three-address code using labels and jump instructions, since three-address code itself has no built-in notion of nested blocks the way source code does.
Source Code:
if (a < b)
x = 1;
else
x = 2;
Three-Address Code:
if a < b goto L1
x = 2
goto L2
L1: x = 1
L2:
Source Code:
while (a < b)
a = a + 1;
Three-Address Code:
L1: if a < b goto L2
goto L3
L2: a = a + 1
goto L1
L3:
In both examples, labels mark specific positions in the generated code, and conditional or unconditional jumps direct execution to the correct label depending on the outcome of a comparison, faithfully reproducing the control flow described by the original source code using only the very limited set of instruction types available in three-address code.
Quadruples represent three-address code in a structured, tabular form rather than as a sequence of textual instructions. Each row of a quadruple table, often simply called a quadruple, contains four fields: an operator, up to two operands, and a result.
Three-Address Code: t1 = a + b t2 = t1 * c Equivalent Quadruples: Index Operator Operand1 Operand2 Result (0) + a b t1 (1) * t1 c t2
This tabular structure makes quadruples particularly convenient to work with programmatically, since each instruction has a fixed, predictable format that can be easily stored, indexed, and modified during later phases such as code optimization.
Triples offer a more compact alternative to quadruples by eliminating the explicit temporary result field. Instead of naming a temporary variable for each intermediate result, a triple refers back to the result of an earlier instruction by its position, or index, within the table.
Equivalent Triples for the same expression: Index Operator Operand1 Operand2 (0) + a b (1) * (0) c
Here, the second instruction refers to the result of the first instruction using its index, (0), rather than introducing an explicitly named temporary variable such as t1. This makes triples somewhat more compact than quadruples, but it also makes them more fragile in certain situations, since rearranging or optimizing the instructions, such as moving one to a different position, can require carefully updating every reference to it elsewhere in the table.
| Representation | Advantage | Drawback |
|---|---|---|
| Syntax Tree | Closely preserves the hierarchical structure of the original program, useful for some kinds of analysis. | Less convenient than a linear representation for many optimization and code generation techniques. |
| Three-Address Code | Simple, linear, and readable, closely resembling low-level assembly-style instructions. | Explicit temporary variable names can slightly increase the size of the representation. |
| Quadruples | Structured and easy to manipulate programmatically, with a fixed, predictable format. | Requires explicit storage for temporary result names in every instruction. |
| Triples | More compact than quadruples, since it avoids explicitly naming temporary results. | Rearranging instructions during optimization can be more error-prone, since positional references must be carefully maintained. |
Intermediate code generation does not operate in isolation. It relies directly on the annotated syntax tree produced by semantic analysis, using the type information already verified in that phase to decide, for example, whether a particular addition instruction should be treated as an integer addition or a floating-point addition, and where any necessary type conversion instructions need to be inserted. This phase is also typically implemented using the same syntax directed translation techniques introduced earlier in this series, with synthesized attributes representing the generated code for each sub-expression, which are then combined together to form the code for larger expressions and statements.
| Mistake | Correct Understanding |
|---|---|
| Assuming intermediate code must always be tied to a specific target machine's instruction set. | Intermediate representations are intentionally designed to be machine-independent, which is exactly what allows the same intermediate code to be used with different target machine back ends. |
| Believing quadruples and triples represent fundamentally different information from three-address code. | Quadruples and triples are simply alternative, tabular ways of storing the same underlying three-address code instructions, rather than a different kind of intermediate representation altogether. |
| Thinking control statements require special new instruction types beyond simple jumps and labels. | Control statements such as if-else blocks and loops are translated using only conditional and unconditional jumps combined with labels, without needing any specialized control-flow instructions. |
| Overlooking the connection between intermediate code generation and the type information computed during semantic analysis. | Type information verified during semantic analysis directly influences intermediate code generation, determining which specific operations and conversions should appear in the generated code. |
Intermediate code generation transforms a verified, annotated syntax tree into a simplified, machine-independent representation that serves as the shared boundary between a compiler's front end and back end. Common forms of this representation include three-address code, along with its tabular variants, quadruples and triples, each offering a slightly different trade-off between readability, compactness, and ease of manipulation. Expressions are translated by generating temporary variables that mirror the structure of the underlying syntax tree, while control statements are translated using labels and jump instructions to faithfully reproduce the program's intended control flow.
In this tutorial, you learned why intermediate representations are essential to modern compiler design, the most common forms of intermediate code, how expressions and control statements are translated into three-address code with worked examples, how quadruples and triples represent the same information in tabular form, and how this phase connects back to the type information verified during semantic analysis. With this foundation in place, you are ready to explore code optimization, where this intermediate representation is analyzed and improved before final target code is produced.