CD Notes
HubApplications of Compiler DesignCompiler vs Interpreter — Compiler DesignLanguage ProcessorsPhases of a CompilerWhat is Compiler Design?The AssemblerCompiler OverviewComplete Compilation ProcessThe LinkerThe LoaderThe PreprocessorFinite Automata in Lexical AnalysisIntroduction to Lexical AnalysisLex Tool - Lexical Analyzer GeneratorLexemes in Compiler DesignLexical Analyzer DesignLexical Errors and Error RecoveryPatterns in Lexical AnalysisRegular Expressions in Compiler DesignTokens in Compiler DesignAmbiguity in Grammars for Compiler DesignBottom-Up Parsing in Compiler DesignCLR Parser: Canonical LR(1) Parsing with Complete Lookahead InformationContext-Free Grammars for Syntax AnalysisDerivations in Syntax AnalysisIntroduction to Parsing in Compiler DesignLALR Parser: Practical LR(1) With State Merging for EfficiencyLL(1) Parser: Single Lookahead Predictive Parsing from First PrinciplesLR Parsers: Canonical LR Parsing for Complex Language SyntaxParse Trees in Compiler DesignPredictive Parsers: Lookahead-Guided Top-Down ParsingRecursive Descent Parsers: Procedural Approach to Top-Down ParsingShift-Reduce Parsing: Fundamental Mechanism of Bottom-Up Syntax AnalysisSLR Parser: Simple LR Parsing with Efficient AutomataTop-Down Parsing Techniques in Compiler DesignScope Management: Symbol Table Design for Language ImplementationSemantic Analysis IntroductionSemantic Errors: Detection and Reporting in Compiler ConstructionSemantic Rules: Defining Language Semantics in Compiler ConstructionSymbol Table: Core Data Structure for Semantic Analysis and Code GenerationType Checking: Static Analysis for Type Safety in Compiler DesignType Conversion and Coercion in Compiler Semantic AnalysisAttribute Grammars: Foundation of Semantic Analysis and Code GenerationDependency Graphs: Visualizing Attribute Computation Order in Semantic AnalysisInherited Attributes: Top-Down Attribute Computation for Context TransferSyntax-Directed Definitions: Attribute Grammars for Semantic AnalysisSyntax-Directed Translation Schemes: Execution Semantics and Code GenerationSynthesized Attributes: Bottom-Up Attribute Computation in Compiler DesignDirected Acyclic Graphs (DAGs) in Compiler DesignIndirect Triples in Compiler DesignIntroduction to Intermediate Code GenerationQuadruples Representation in Compiler DesignSyntax Trees as Intermediate RepresentationThree-Address Code in Compiler DesignTriples Representation in Compiler DesignActivation Records: Function Call ManagementHeap Allocation: Dynamic Memory ManagementMemory Management: Strategies and OptimizationParameter Passing: Communication Between FunctionsRuntime Environment: Program Execution ContextStack Allocation: Automatic Memory ManagementStorage Organization: Memory Sections and LayoutIntroduction to Code Generation in Compiler DesignCode Generator Design in Compiler ConstructionInstruction Selection in Code GenerationMachine Code Generation in CompilersRegister Allocation in Compiler DesignRegister Assignment Strategies in Code GenerationTarget Machine Architecture for Code GenerationIntroduction to Code Optimization in Compiler DesignCommon Subexpression Elimination (CSE) in Compiler OptimizationConstant Folding Optimization in Compiler DesignConstant Propagation in Compiler OptimizationDead Code Elimination in Compiler OptimizationGlobal Optimization Techniques in Compiler DesignLocal Optimization Techniques in Compiler DesignLoop Optimization Techniques in Compiler DesignPeephole Optimization in Compiler DesignBison: LALR Parser GeneratorFlex: Lexical Analyzer GeneratorLex: Original Lexical AnalyzerParser Generator WorkflowPractical Parser ProjectsYACC: Original Parser GeneratorBytecode and Virtual MachinesGCC ArchitectureJava Compiler and BytecodeJust-In-Time CompilationLLVM: The Low-Level Virtual MachinePython Interpreter ArchitectureWebAssembly BasicsCalculator Compiler ProjectExpression Parser ProjectLexical Analyzer ProjectMini Programming Language ProjectSyntax Checker ProjectToy Compiler Project: Minimal Complete CompilerCompiler Design CheatsheetCompiler Design Interview QuestionsGATE Compiler Design QuestionsLexical Analysis Interview QuestionsParsing Interview QuestionsGlossary of Compiler Design TermsImportant Formulas and RulesQuick Revision Notes for ExamsRecommended Books and Resources — Compiler DesignContext-Free Languages in Compiler DesignDeterministic Finite Automata (DFA) in Compiler DesignFinite Automata Review for Compiler DesignNondeterministic Finite Automata (NFA) in Compiler DesignPushdown Automata (PDA) in Compiler DesignRegular Languages in Compiler DesignTuring Machines and Their Role in Compiler Theory
Complete guide to three-address code covering instruction types, generation from expressions and control structures, boolean expression translation, and implementation techniques.
Definition
Three-address code (TAC) is an intermediate representation where each instruction has at most one operator on the right side (besides assignment). The general form is: x = y op z, meaning apply operator op to y and z and store the result in x. The name comes from the three "addresses" (operands) involved.
Instruction Types
Example
Category Form Example
────────────────────────────────────────────────────────
Assignment x = y op z t1 = a + b
Unary x = op y t1 = -a
Copy x = y a = t1
Unconditional goto L goto L3
Conditional if x relop y goto L if t1 < t2 goto L1
if x goto L if t1 goto L2
Parameter param x param a
Call call p, n call factorial, 1
Return return x return t1
Indexed Load x = y[i] t1 = a[t2]
Indexed Store x[i] = y a[t1] = t2
Address x = &y t1 = &a
Dereference x = *y t1 = *p
Ptr Assignment *x = y *p = t1
Generating TAC from Expressions
Example
Source: a + b * c - d / e
Parse tree: Three-address code:
[-] t1 = b * c
/ \ t2 = a + t1
[+] [/] t3 = d / e
/ \ / \ t4 = t2 - t3
[a] [*] [d] [e]
/ \
[b] [c]
Translation algorithm (recursive):
gen_expr(node):
match node:
Binary(op, left, right):
l = gen_expr(left)
r = gen_expr(right)
t = newtemp()
emit(t = l op r)
return t
Leaf(name):
return name
Constant(val):
return val
Generating TAC for Control Structures
If-Else Statement
Example
Source: if (a > b) { x = 1; } else { x = 2; } y = x;
TAC:
if a > b goto L_true
goto L_false
L_true:
x = 1
goto L_end
L_false:
x = 2
L_end:
y = x
Optimized (fewer jumps):
if a <= b goto L_false // negate condition
x = 1
goto L_end
L_false:
x = 2
L_end:
y = x
While Loop
Example
Source: while (a < b) { a = a + 1; }
TAC:
L_begin:
if a >= b goto L_end // negate condition for exit
a = a + 1
goto L_begin
L_end:
For loop - Source: for (i=0; i<n; i++) { s = s + a[i]; }
TAC:
i = 0
L_begin:
if i >= n goto L_end
t1 = i * elem_size
t2 = a[t1]
s = s + t2
i = i + 1
goto L_begin
L_end:
Switch Statement
| Source | switch(x) { case 1: a=10; break; case 2: a=20; break; default: a=0; } |
| L1 | a = 10 |
| L2 | a = 20 |
| L_default | a = 0 |
Boolean Expression Translation
Short-Circuit Evaluation
| Source | if (a < b && c > d || e == f) goto L_true |
| if a < b goto L1 // a<b true | check c>d |
| goto L2 // a<b false | try e==f (OR) |
| if c > d goto L_true // c>d true | whole AND is true |
| goto L2 // c>d false | AND is false, try OR |
| if e == f goto L_true // e==f true | OR succeeds |
| Control flow for | E1 AND E2 OR E3 |
| E1_true | E2 |
| E1_false | E3 (short-circuit AND, try next OR clause) |
| E2_true | L_true |
| E2_false | E3 |
| E3_true | L_true |
| E3_false | L_false |
Numerical Representation of Booleans
Example
Source: x = (a < b) // assign boolean result to variable
TAC (using 0/1 values):
if a < b goto L1
x = 0
goto L2
L1: x = 1
L2:
Alternative (conditional assignment):
t1 = a < b // if machine supports comparison as value
x = t1
Array Access Translation
| One-dimensional | x = a[i] |
| x = *t2 // or | x = a[t1] in TAC notation |
| Two-dimensional (row-major) | x = a[i][j] |
| With lower bounds | a[low1..high1][low2..high2] |
Function Call Translation
Code example
Source: result = max(a + b, c * d);
TAC:
t1 = a + b
t2 = c * d
param t1 // push first argument
param t2 // push second argument
t3 = call max, 2 // call with 2 arguments
result = t3
Source: int factorial(int n) { if (n<=1) return 1; return n*factorial(n-1); }
TAC:
factorial:
if n <= 1 goto L1
t1 = n - 1
param t1
t2 = call factorial, 1
t3 = n * t2
return t3
L1:
return 1Type Conversions in TAC
| Source | float f = 3 + (int)x; // x is double |
| t1 = (float) i // int | float |
| t1 = (int) d // double | int (truncate) |
| t2 = (char) i // int | char (truncate) |
Temporary Variable Management
Example
Strategy 1: Unlimited temporaries (simple)
Generate new temp for every subexpression.
Let register allocator handle the rest.
Strategy 2: Reuse temporaries (save space)
Track live ranges of temps within basic block.
Reuse temps whose values are no longer needed.
t1 = a + b ← t1 live
t2 = c + d ← t1, t2 live
t3 = t1 * t2 ← t3 live (t1, t2 dead)
t1 = t3 + e ← t1 live (reuse t1! t3 dead)
Only 3 temp names needed for this entire block.
Interview Questions
- Q: Why is three-address code called three-address?
A: Each instruction involves at most three addresses (operand locations): typically two source operands and one destination. For example, t1 = a + b has three addresses: a, b, and t1. Unary operations and copies use fewer, but three is the maximum.
- Q: How does short-circuit evaluation of boolean expressions translate to TAC?
A: Short-circuit AND: if left operand is false, skip right operand (jump to false label). Short-circuit OR: if left operand is true, skip right operand (jump to true label). This generates conditional jumps instead of evaluating both sides, potentially avoiding side effects and improving performance.
- Q: How are function calls represented in TAC?
A: Using param instructions to push arguments, followed by call p,n (call function p with n arguments). The return value is assigned to a temporary. This representation is ABI-independent — the code generator maps params to registers or stack positions according to the calling convention.
- Q: What is the advantage of TAC over stack-based IR?
A: TAC makes operands explicit (named temporaries), enabling optimization via dataflow analysis. Stack-based IR (like JVM bytecode) has implicit operands on the stack, making analysis harder. TAC also maps more naturally to register machines. However, stack IR is more compact and simpler to generate.
- Q: How many temporaries are needed for a basic block?
A: At most as many as the maximum number of simultaneously live temporaries — equivalent to the minimum number of registers needed. For expression trees, this equals the Ershov number (tree register labeling). Optimal temporary reuse within a block is efficiently computable using liveness analysis.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Three-Address Code in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, intermediate, code, generation, three
Related Compiler Design Topics
Continue learning this concept
Intermediate Code GenerationDirected Acyclic Graphs (DAGs) in Compiler DesignComplete guide to DAGs as intermediate representation covering DAG construction, common subexpression detection, code generation from DAGs, and optimization using DAG representation.Intermediate Code GenerationIndirect Triples in Compiler DesignGuide to indirect triples as an intermediate representation that combines the space efficiency of triples with the reordering flexibility of quadruples using an indirection array.Intermediate Code GenerationIntroduction to Intermediate Code GenerationComprehensive introduction to intermediate code generation in compilers covering its purpose, types of intermediate representations, benefits of IR, and the role of intermediate code in the compilation pipeline.Intermediate Code GenerationQuadruples Representation in Compiler DesignDetailed guide to quadruples as three-address code representation covering structure, advantages, comparison with triples, and practical implementation in intermediate code generation.Intermediate Code GenerationSyntax Trees as Intermediate RepresentationGuide 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.Intermediate Code GenerationTriples Representation in Compiler DesignGuide to triples as a compact intermediate code representation covering structure, position-based referencing, comparison with quadruples, and optimization challenges.