Intermediate code generation is the compiler phase that converts the analyzed source program into a machine-independent intermediate representation before optimization and target-code generation.
Position in Compiler
Source Program
|
Lexical, Syntax and Semantic Analysis
|
v
Intermediate Code Generator
|
Intermediate Representation
|
Code Optimization
|
Target Code Generation
Need for Intermediate Code
Separates the compiler front end from the machine-dependent back end.
Improves portability.
Makes optimization easier.
Allows one front end to support multiple target machines.
Allows one back end to support multiple source languages.
Properties of a Good Intermediate Representation
Easy to generate from source constructs.
Easy to translate into target instructions.
Independent of a particular machine.
Suitable for optimization.
Clear and unambiguous.
Example
For the source statement x = a + b * c;:
t1 = b * c
t2 = a + t1
x = t2
Conclusion: Intermediate code forms a bridge between semantic analysis and machine-code generation and makes compiler design modular, portable and optimization friendly.
2. Forms of Intermediate Representation 14 Marks
Main Forms
Postfix notation
Syntax tree
Directed acyclic graph
Three-address code
Static single-assignment form
Syntax Tree
A syntax tree represents operators as internal nodes and operands as leaves.
Expression: a + b * c
+
/ \
a *
/ \
b c
Postfix Form
Infix: a + b * c
Postfix: a b c * +
Three-Address Form
t1 = b * c
t2 = a + t1
Comparison
Representation
Main Feature
Use
Syntax tree
Hierarchical structure
Semantic analysis
DAG
Shares common subexpressions
Optimization
Postfix
Operator after operands
Stack evaluation
Three-address code
At most three addresses per statement
Optimization and code generation
3. Three-Address Code 14 Marks
Three-address code, or TAC, is an intermediate representation in which each instruction contains at most one operator and usually no more than three addresses.
General Form
x = y op z
Common TAC Statements
Binary operation: x = y op z
Unary operation: x = op y
Copy: x = y
Unconditional jump: goto L
Conditional jump: if x relop y goto L
Procedure call: param x, call p, n
Array access: x = y[i] or x[i] = y
Address operation: x = &y, x = *y, *x = y
Example
Expression: a = b * -c + b * -c
t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5
Advantages
Simple instruction format.
Easy to rearrange and optimize.
Explicit evaluation order.
Convenient for target-code generation.
Limitations
Produces many temporary variables.
Longer than tree representation.
Needs separate data structure for storage.
4. Quadruples 14 Marks
A quadruple represents each three-address instruction using four fields: operator, argument 1, argument 2 and result.
Format
(op, arg1, arg2, result)
Example
Expression: x = a + b * c
t1 = b * c
t2 = a + t1
x = t2
No.
op
arg1
arg2
result
0
*
b
c
t1
1
+
a
t1
t2
2
=
t2
—
x
Advantages
Result names are explicit.
Instructions can be moved during optimization.
Easy to generate target code.
Suitable for global optimization.
Disadvantage
Many temporary names may be generated, increasing symbol-table and storage requirements.
5. Triples 14 Marks
A triple represents an instruction using operator, argument 1 and argument 2. The result is referred to by the position number of the instruction.
Format
(op, arg1, arg2)
Example
No.
op
arg1
arg2
0
*
b
c
1
+
a
(0)
2
=
(1)
x
Advantages
No explicit temporary variables are needed.
Representation is compact.
Reduces temporary-name storage.
Disadvantages
Moving instructions changes position references.
Code optimization becomes difficult.
References must be updated after reordering.
6. Indirect Triples 14 Marks
Indirect triples use a separate pointer list to refer to triples, so instructions can be reordered by changing pointers instead of changing triple positions.
Structure
Pointer List Triple Table
0 ---------------> (*, b, c)
1 ---------------> (+, a, (0))
2 ---------------> (=, (1), x)
Advantages
Easy code movement.
Suitable for optimization.
No explicit temporary variables.
Triple table remains unchanged during reordering.
Quadruples vs Triples vs Indirect Triples
Feature
Quadruples
Triples
Indirect Triples
Result
Explicit temporary
Instruction position
Pointer to triple
Space
More
Less
Moderate
Code movement
Easy
Difficult
Easy
Optimization
Convenient
Less convenient
Convenient
7. Translation of Assignment Statements 14 Marks
Assignment translation converts expressions and assignments into a sequence of intermediate instructions using temporary variables.
x = &y address of y
x = *p value pointed by p
*p = x store x at address p
Unary Minus
Expression: x = -a
TAC:
t1 = minus a
x = t1
9. Translation of Boolean Expressions 14 Marks
Boolean expressions are translated either by computing explicit Boolean values or by generating conditional and unconditional jumps.
Methods
Numerical method: represent true as 1 and false as 0.
Control-flow method: generate jumps to true and false labels.
Relational Expression
if a < b goto Ltrue
goto Lfalse
Short-Circuit Evaluation
In short-circuit evaluation, only the minimum required operands are evaluated.
AND Expression
B1 AND B2
If B1 is false, B2 need not be evaluated.
B1.true points to beginning of B2.
OR Expression
B1 OR B2
If B1 is true, B2 need not be evaluated.
B1.false points to beginning of B2.
NOT Expression
For NOT B:
true-list = B.false-list
false-list = B.true-list
Advantages of Control-Flow Translation
Avoids unnecessary computation.
Supports short-circuit semantics.
Maps naturally to machine branch instructions.
10. Translation of Control Structures 14 Marks
If Statement
if B then S
Code:
evaluate B
if false goto Lnext
code for S
Lnext:
If-Else Statement
if B then S1 else S2
evaluate B
if false goto Lelse
code for S1
goto Lnext
Lelse:
code for S2
Lnext:
While Loop
Lbegin:
evaluate B
if false goto Lnext
code for S
goto Lbegin
Lnext:
Do-While Loop
Lbegin:
code for S
evaluate B
if true goto Lbegin
For Loop
initialization
Ltest:
evaluate condition
if false goto Lnext
body
increment
goto Ltest
Lnext:
Important Point
Labels may not be known when a jump instruction is first generated. Backpatching is used to fill these missing target addresses later.
11. Backpatching 14 Marks
Backpatching is a technique for generating jump instructions with initially unknown targets and filling those targets later when the correct label becomes known.
Need
During one-pass intermediate-code generation, the target of a forward jump may not yet be available.
Lists Used
truelist: list of jumps to be directed to the true branch.
falselist: list of jumps to be directed to the false branch.
nextlist: list of jumps to the next statement.
Important Functions
makelist(i)
Creates a new list containing instruction i.
merge(p1, p2)
Combines two lists.
backpatch(p, i)
Inserts target i into all incomplete jumps in list p.
Example
Boolean expression: a < b OR c < d
100: if a < b goto _
101: goto _
102: if c < d goto _
103: goto _
Backpatch first false jump 101 with 102.
Final true list = {100, 102}
Final false list = {103}
Backpatching for If-Else
Generate Boolean code with true and false lists.
Backpatch true list with beginning of then-part.
Backpatch false list with beginning of else-part.
Generate a jump after then-part.
Backpatch next list with statement following if-else.
Advantages
Supports one-pass code generation.
Avoids premature label assignment.
Useful for Boolean and control-flow translation.
Simplifies syntax-directed code generation.
12. Runtime Memory Management 14 Marks
Runtime memory management is the organization and allocation of memory required by a program during execution.
Typical Runtime Memory Layout
High Address
+-----------------------+
| Stack |
| ↓ |
+-----------------------+
| |
| Free Space |
| |
+-----------------------+
| ↑ |
| Heap |
+-----------------------+
| Static / Global Data |
+-----------------------+
| Program Code / Text |
+-----------------------+
Low Address
Memory Areas
Code area: executable instructions.
Static area: global and static variables.
Stack: procedure calls, local variables and temporaries.
Heap: dynamically allocated objects.
Allocation Strategies
Static allocation
Stack allocation
Heap allocation
Requirements
Efficient allocation and deallocation.
Support for recursion.
Support for dynamic data structures.
Correct handling of variable lifetimes.
Protection from overlapping memory usage.
13. Static Storage Allocation 14 Marks
In static allocation, memory locations are fixed at compile time and remain unchanged during program execution.
Characteristics
Addresses are known before execution.
Storage is allocated once.
Variables normally remain alive for the whole program.
No runtime allocation overhead.
Suitable For
Global variables
Static variables
Languages without recursion
Fixed-size data
Advantages
Simple implementation.
Fast access.
No allocation and deallocation cost.
Easy address calculation.
Limitations
Does not naturally support recursion.
Memory may be wasted.
Cannot support variable-size dynamic objects efficiently.
Object lifetime is inflexible.
14. Dynamic Storage Allocation 14 Marks
Dynamic allocation assigns and releases memory during program execution according to runtime requirements.
Types
Stack-based dynamic allocation
Heap-based dynamic allocation
Heap Allocation
The heap stores objects whose lifetime does not follow procedure-call order.
Allocation Operations
Request a block of required size.
Find a suitable free block.
Mark it allocated.
Return its starting address.
Release or reclaim the block later.
Problems
Internal fragmentation
External fragmentation
Dangling pointers
Memory leaks
Garbage collection overhead
Advantages
Supports linked lists, trees and dynamic objects.
Uses memory according to actual need.
Supports flexible object lifetimes.
15. Stack-Based Memory Allocation 14 Marks
Stack allocation manages procedure activations in last-in, first-out order using activation records.
Working
On procedure call, push a new activation record.
Store parameters, local variables and control information.
Execute the procedure.
On return, pop the activation record.
Before Call:
+------------------+
| Caller Record |
+------------------+
After Call:
+------------------+
| Called Procedure |
+------------------+
| Caller Record |
+------------------+
Advantages
Supports recursion.
Fast allocation and deallocation.
Automatic lifetime management.
Efficient use of memory for nested calls.
Limitations
Only supports LIFO lifetimes.
Objects needed after return cannot remain on stack.
Very deep recursion can cause stack overflow.
16. Activation Record 14 Marks
An activation record is a block of stack memory containing information needed for one execution of a procedure.
Typical Fields
+-------------------------+
| Actual Parameters |
+-------------------------+
| Return Value |
+-------------------------+
| Return Address |
+-------------------------+
| Control Link |
+-------------------------+
| Access Link |
+-------------------------+
| Saved Machine Status |
+-------------------------+
| Local Variables |
+-------------------------+
| Temporaries |
+-------------------------+
Field Functions
Parameters: values passed to procedure.
Return value: result returned to caller.
Return address: instruction to execute after return.
Control link: points to caller's activation record.
Access link: provides access to non-local data.
Machine status: saved registers and processor information.
Locals and temporaries: procedure-specific storage.
Activation Tree
An activation tree shows the nesting relationship among procedure activations. The current stack contents correspond to a path from the root to the currently active procedure.
17. Symbol Table Management 14 Marks
A symbol table is a compiler data structure that stores information about identifiers and makes this information available to different compiler phases.
Stored Information
Name of identifier
Data type
Scope level
Storage class
Memory address or offset
Size and dimensions
Parameter information
Return type
Operations
Insert a symbol.
Search for a symbol.
Update attributes.
Begin a new scope.
End an existing scope.
Detect duplicate declaration.
Detect use of undeclared identifier.
Implementation Methods
Method
Advantage
Limitation
Linear list
Simple
Slow search
Ordered list
Supports ordered traversal
Costly insertion
Binary search tree
Reasonable search
Can become unbalanced
Hash table
Fast average search and insertion
Collision handling required
Scope Management
Nested scopes can be managed using separate tables, table stacks or chained entries.
Global Scope Table
|
Function Scope Table
|
Block Scope Table
Role in Compiler Phases
Lexical analysis enters identifiers.
Syntax and semantic analysis check declarations and types.
Intermediate-code generation obtains addresses.
Code generation uses size and location information.
Conclusion: Efficient symbol-table management is essential for declaration checking, type analysis, scope handling, memory allocation and target-code generation.
Symbol tables store identifier attributes and scope information.
Important RGPV Exam Questions
Long Answer Questions
Explain intermediate code generation and its importance.
Define three-address code and explain its statement types.
Explain quadruples, triples and indirect triples with examples.
Compare quadruples and triples.
Explain translation of assignment statements using syntax-directed rules.
Explain translation of array references and pointer expressions.
Explain translation of Boolean expressions using short-circuit evaluation.
Explain intermediate-code generation for if, if-else and while statements.
Define backpatching and explain makelist, merge and backpatch functions.
Explain runtime memory organization with a neat diagram.
Explain static and dynamic storage allocation.
Explain stack-based memory allocation and activation records.
Draw and explain the fields of an activation record.
Explain symbol-table management and its implementation methods.
Compare static, stack and heap allocation.
Short Answer Questions
What is intermediate code?
Define three-address code.
What is a quadruple?
What is an indirect triple?
Define short-circuit evaluation.
What is backpatching?
Define truelist and falselist.
What is an activation record?
What is a control link?
What information is stored in a symbol table?
Exam Strategy: For TAC questions, write the source expression, temporary instructions and representation table. For memory questions, draw runtime layout and activation-record diagrams.
Download Study Resources
Unit 4 PDF
Printable detailed notes will be uploaded soon.
Coming Soon
TAC Problems
Practice translations will be available soon.
Coming Soon
PYQ Analysis
Repeated Unit 4 questions will be added soon.
Coming Soon
Frequently Asked Questions
It is an intermediate representation in which each instruction normally contains one operator and at most three addresses.
Quadruples use explicit temporary result names, while triples refer to results by instruction positions.
It is used when a jump target is not known at the time the jump instruction is generated.
Stack-based allocation naturally supports recursion by creating a separate activation record for each call.
It stores identifier information such as type, scope, size, address and parameter details for use by compiler phases.