Intermediate Code Generation

Prefix, Postfix, Quadruple, Triple, Indirect Triple, Syntax Tree

Compiler Design

March 17, 2026

Compiler Design Intermediate Code Generation March 17, 2026 1 / 61

Intermediate Code Generation

Intermediate Code Generation (ICG) is a phase in compiler design.

Converts source code into an intermediate representation (IR).
IR is independent of source language and machine architecture.
Makes optimization and code generation easier.

Compiler Design Intermediate Code Generation March 17, 2026 2 / 61

Prefix Notation

Definition
Operator appears before operands.
Also called Polish Notation.
Example
Infix:
(A + B) ∗ C
Prefix:
∗ + ABC

Compiler Design Intermediate Code Generation March 17, 2026 3 / 61

Postfix Notation

Definition
Operator appears after operands.
Also called Reverse Polish Notation.
Example
Infix:
(A + B) ∗ C
Postfix:
AB + C ∗

Compiler Design Intermediate Code Generation March 17, 2026 4 / 61

Three Address Code

General Form

x = y op z
Example
Expression:
A=B +C ∗D
Three Address Code:
t1 = C ∗ D
t2 = B + t1
A = t2

Compiler Design Intermediate Code Generation March 17, 2026 5 / 61

Quadruple Representation

Structure:

Operator Arg1 Arg2 Result

Example:

Op Arg1 Arg2 Result

* C D t1
+ B t1 t2
= t2 - A

Compiler Design Intermediate Code Generation March 17, 2026 6 / 61

Triple Representation

Structure:

Index Operator Arg1 Arg2

Example:

Index Op Arg1 Arg2

0 * C D
1 + B (0)
2 = (1) A

Compiler Design Intermediate Code Generation March 17, 2026 7 / 61

Indirect Triple

Uses a pointer table to refer to triples.

Pointer Table
Pointer Triple Index
P0 0
P1 1
P2 2

Compiler Design Intermediate Code Generation March 17, 2026 8 / 61

Syntax Tree

Expression:

A+B ∗C
Syntax Tree Representation
+
/ \
A *
/\
B C

Compiler Design Intermediate Code Generation March 17, 2026 9 / 61

Evaluation of Expressions

In compiler design, expression evaluation determines the order in which

operators and operands are processed.
This depends on:
Operator precedence
Associativity
Parentheses
Example expression:

A+B ∗C
Since ∗ has higher precedence than +:
B ∗ C → first
A + (result) → second

Compiler Design Intermediate Code Generation March 17, 2026 10 / 61

Evaluation Steps

Intermediate representation:
t1 = B ∗ C
t2 = A + t 1
This form is used in intermediate code generation.

Compiler Design Intermediate Code Generation March 17, 2026 11 / 61

Three Address Code (TAC)

Three-address code is a common intermediate representation where each

instruction contains at most three addresses.
General form:

x = y op z
Where
x → result
y , z → operands
op → operator

Compiler Design Intermediate Code Generation March 17, 2026 12 / 61

Example of TAC

Expression:

A=B +C ∗D
Three-address code:
t1 = C ∗ D
t2 = B + t1
A = t2
t1 , t2 are temporary variables.

Compiler Design Intermediate Code Generation March 17, 2026 13 / 61

Common TAC Forms

Binary operation

x = y op z
Example:

t1 = a + b
Unary operation

x = op y
Example:

t1 = −a

Compiler Design Intermediate Code Generation March 17, 2026 14 / 61

More TAC Forms

Assignment

x =y
Conditional jump

if x < y goto L1

Compiler Design Intermediate Code Generation March 17, 2026 15 / 61

Synthesized Attributes

A Synthesized Attribute is an attribute whose value is computed from the

attributes of its child nodes in the syntax tree.
Information flows from bottom to top.
Used mainly in bottom-up parsing.
Example grammar:

E → E1 + T
Attribute rule:

E .val = E1 .val + T .val

Compiler Design Intermediate Code Generation March 17, 2026 16 / 61

Synthesized Attribute Example

Expression:

3+4
Evaluation:
T .val = 3
T .val = 4
E .val = 3 + 4 = 7
Thus the value is synthesized from children.

Compiler Design Intermediate Code Generation March 17, 2026 17 / 61

Inherited Attributes

An Inherited Attribute gets its value from parent or sibling nodes.

Information flows from top to bottom or sideways in the syntax tree.
Used mainly in top-down parsing.
Example grammar:

E → T E′

E′ → + T E′

E′ → ϵ

Compiler Design Intermediate Code Generation March 17, 2026 18 / 61

Inherited Attribute Example

Attributes may be passed like:

E ′ .inh = T .val
Later computation:

E ′ .val = E ′ .inh + T .val

Here the attribute value is inherited from the parent or sibling node.

Compiler Design Intermediate Code Generation March 17, 2026 19 / 61

Difference Between Attributes

Feature Synthesized Attribute Inherited Attribute

Flow of information Bottom → Up Top → Down / Sideways
Source Child nodes Parent / Sibling nodes
Used in Bottom-up parsing Top-down parsing
Computation From children From parent context

Compiler Design Intermediate Code Generation March 17, 2026 20 / 61

Syntax Tree Example

Expression:

3+5
Syntax tree:
+
/ \
3 5
Synthesized attribute evaluation:
[Link] = 3
[Link] = 5
+.val = 3 + 5 = 8

Compiler Design Intermediate Code Generation March 17, 2026 21 / 61

Inherited Attribute

An Inherited Attribute means:

A child node receives information from its parent or left sibling.
The attribute value is passed down the syntax tree.

Compiler Design Intermediate Code Generation March 17, 2026 22 / 61

Example: Variable Declaration

Consider the declaration:

int a, b

int represents the data type.

Identifiers a and b should inherit this type.

Compiler Design Intermediate Code Generation March 17, 2026 23 / 61

Grammar

Grammar rules:

D→T L

T → int

L → id

L → id, L
Where:
T = type
L = list of identifiers

Compiler Design Intermediate Code Generation March 17, 2026 24 / 61

Attribute Rule

Attribute rule:

[Link] = T .type
Meaning:
The identifier list L inherits the type from T .

Compiler Design Intermediate Code Generation March 17, 2026 25 / 61

Syntax Tree

D
/ \
T L
— /\
int a b

Compiler Design Intermediate Code Generation March 17, 2026 26 / 61

Attribute Flow

Step 1:

T .type = int
Step 2:

[Link] = T .type
So:

[Link] = int

Compiler Design Intermediate Code Generation March 17, 2026 27 / 61

Final Result

Now identifiers inherit the type:

[Link] = int

[Link] = int
Final meaning:

a : int

b : int

Compiler Design Intermediate Code Generation March 17, 2026 28 / 61

Syntax-Directed Definition
Syntax trees for assignment statements are produced by the
syntax-directed definition.
Non-terminal S generates an assignment statement.
Binary operators + and * follow usual associativity and precedence.
Example input:
a := b * -c + b * -c
Token id has attribute place pointing to the symbol-table entry.
[Link] represents the lexeme or its index in the lexical array.

Compiler Design Intermediate Code Generation March 17, 2026 29 / 61

Graphical Representation

Figure: Syntax tree for the input assignment statement

Compiler Design Intermediate Code Generation March 17, 2026 30 / 61

Syntax Tree Representations
Pointer-based nodes: each node is a record with operator and
children pointers.
Array-based nodes: nodes allocated in an array; index serves as
pointer.
Root node example: position 10.

Compiler Design Intermediate Code Generation

Figure: Syntax tree
March 17, 2026 31 / 61
Types of Three-Address Statements

1 Address pointer assignments: x := &y, x := *y, *x := y

2 Binary operation assignments: x := y op z
3 Unary operation assignments: x := op y
4 Copy statements: x := y
5 Unconditional jump: goto L
6 Conditional jump: if x relop y goto L
7 Procedure calls and returns: param x; call p, n; return y
8 Indexed assignments: x := y[i]; x[i] := y

Compiler Design Intermediate Code Generation March 17, 2026 32 / 61

Syntax-Directed Translation

Temporary names are created for interior nodes of the syntax tree.
Example assignment id := E:
Evaluate E into temporary t
Generate [Link] := t
Non-terminal E attributes:
[Link] – variable to hold value
[Link] – sequence of three-address statements

Compiler Design Intermediate Code Generation March 17, 2026 33 / 61

Example: Input Translation

Input:

a := b * -c + b * -c

Generate three-address code using newtemp for temporary variables.

Compiler Design Intermediate Code Generation March 17, 2026 34 / 61

Semantic Rules for While Statement
Production: S → while E do S1
Semantic Rules:
[Link] := newlabel
[Link] := newlabel
[Link] := gen([Link]′ :′ ) || E .code || gen(’if’ E .place = [Link] )
|| [Link] || gen(’goto’ [Link]) || gen([Link] ′ :′ )
newtemp() generates t1, t2, ...
gen(x := y + z) generates three-address code.
Control leaves the loop if E = 0.

Compiler Design Intermediate Code Generation March 17, 2026 35 / 61

Storage for Local Names

As declarations in a procedure or block are examined, storage is laid

out for local names.
Each local name gets a symbol-table entry with:
Type of the variable
Relative address in the activation record or static area
Relative address = offset from base of static data or local data in
activation record.

Compiler Design Intermediate Code Generation March 17, 2026 36 / 61

Array and Pointer Width

Width of an array = width of element × number of elements.

Width of a pointer = 4 (assumed).
Types and relative addresses of declared names are computed during
semantic analysis.

Compiler Design Intermediate Code Generation March 17, 2026 37 / 61

Keeping Track of Scope: Nested Procedures

Processing of enclosing procedure declarations is suspended when a

nested procedure is encountered.
Example grammar:

P→D
D → D; D | id : T | proc id; D; S

Implementation uses a linked list of symbol tables.

Each nested procedure has its own symbol table pointing back to the
enclosing procedure’s table.

Compiler Design Intermediate Code Generation March 17, 2026 38 / 61

Symbol Table Operations

mktable(previous): Creates a new symbol table; points to enclosing

table.
enter(table, name, type, offset): Adds a name entry with type and
relative address.
addwidth(table, width): Stores cumulative width of all entries in
table.
enterproc(table, name, newtable): Adds procedure entry pointing
to its symbol table.

Compiler Design Intermediate Code Generation March 17, 2026 39 / 61

Syntax-Directed Translation: Declarations

P →M D {addwidth(top(tblptr), top(offset)); pop(tblptr); pop(offset);}

M→ϵ {t := mktable(nil); push(t, tblptr ); push(0, offset)}
D → D1 ; D2
D → proc id; N D1 ; S {t := top(tblptr );
addwidth(t, top(offset)); pop(tblptr ); pop(offset);
enterproc(top(tblptr ), [Link], t)}
D → id : T {enter (top(tblptr ), [Link], T .type, top(offset));
top(offset) := top(offset) + T .width}
N→ϵ {t := mktable(top(tblptr )); push(t, tblptr ); push(0, offset)}

Compiler Design Intermediate Code Generation March 17, 2026 40 / 61

Stacks for Symbol Tables and Offsets

Stack tblptr stores pointers to tables of procedures like sort,

quicksort, partition.
Top of stack offset = next available relative address for a local
variable.
Actions of subtrees are executed before actions at the end of a
production.
Nonterminal M initializes the outermost scope.
Nonterminal N creates a new table for a nested procedure, using the
enclosing scope.

Compiler Design Intermediate Code Generation March 17, 2026 41 / 61

Variable Declarations

Nonterminal P generates a sequence of declarations id : T.

Before processing the first declaration: offset := 0.
For each name:
Enter it into symbol table with current offset.
Increment offset by [Link].
Procedure enter(name, type, offset) creates the symbol-table
entry.
Attribute type = type expression (integer, real, pointer, array).

Compiler Design Intermediate Code Generation March 17, 2026 42 / 61

Attributes

For an expression E we use two attributes:

[Link] : name that holds the value of E
[Link] : sequence of three-address statements evaluating E
Helper functions:
newtemp() – creates temporary variables
gen() – generates three-address statements
|| – concatenation of code

Compiler Design Intermediate Code Generation March 17, 2026 43 / 61

Assignment Translation

Production Rule

S -> id := E

Semantic Rule

[Link] = [Link] || gen([Link] := [Link])

Example:

t1 = b + c
a = t1

Compiler Design Intermediate Code Generation March 17, 2026 44 / 61

Addition Expression

E -> E1 + E2
[Link] := newtemp
[Link] := [Link] || [Link] ||
gen([Link] := [Link] + [Link])

Example:

t1 = a + b

Compiler Design Intermediate Code Generation March 17, 2026 45 / 61

Multiplication Expression

E -> E1 * E2
[Link] := newtemp
[Link] := [Link] || [Link] ||
gen([Link] := [Link] * [Link])

Example:

t1 = a * b

Compiler Design Intermediate Code Generation March 17, 2026 46 / 61

Unary Minus

E -> -E1
[Link] := newtemp
[Link] := [Link] || gen([Link] := -[Link])

Example:

t1 = -a

Compiler Design Intermediate Code Generation March 17, 2026 47 / 61

Boolean Expressions
Boolean expressions are used to:
Compute logical values
Control flow of program

Syntax Directed Translation:

E -> E1 or E2
[Link] := newtemp
emit([Link] := [Link] or [Link])

E -> E1 and E2
[Link] := newtemp
emit([Link] := [Link] and [Link])

E -> not E1
[Link] := newtemp
emit([Link] := not [Link])

Compiler Design Intermediate Code Generation March 17, 2026 48 / 61

Boolean Expressions

E -> (E1)
[Link] := [Link]

E -> id1 relop id2

[Link] := newtemp
emit(if [Link] relop [Link] goto nextstat+3)
emit([Link] = 0)
emit(goto nextstat+2)
emit([Link] = 1)

Compiler Design Intermediate Code Generation March 17, 2026 49 / 61

Boolean Numerical Representation

E -> true
[Link] := newtemp
emit([Link] = 1)

E -> false
[Link] := newtemp
emit([Link] = 0)

Example:

a or b and not c

t1 = not c
t2 = b and t1
t3 = a or t2

Compiler Design Intermediate Code Generation March 17, 2026 50 / 61

Relational Expression Example

Example: a < b

if a < b goto L1
t = 0
goto L2
L1: t = 1
L2:

Compiler Design Intermediate Code Generation March 17, 2026 51 / 61

Example Translation
Expression:
a < b or c < d and e < f
if a < b goto L1
t1 = 0
goto L2
L1: t1 = 1

if c < d goto L3
t2 = 0
goto L4
L3: t2 = 1

if e < f goto L5
t3 = 0
goto L6
L5: t3 = 1
Compiler Design Intermediate Code Generation March 17, 2026 52 / 61
Short Circuit Evaluation

Short circuit evaluation avoids computing the entire expression.

In E1 or E2, if E1 is true, E2 is not evaluated.
In E1 and E2, if E1 is false, E2 is not evaluated.
This improves efficiency.

Compiler Design Intermediate Code Generation March 17, 2026 53 / 61

Syntax Directed Translation: Conditional Statements
If Statement:
[Link] = [Link] || gen([Link]’:’) || [Link]

If-Else Statement:
[Link] = [Link] || gen([Link]’:’) || [Link] || gen(goto [Link]) || gen([Link]’:’)
|| [Link]

Compiler Design Intermediate Code Generation March 17, 2026 54 / 61

SDT for Switch-Case Statements

Syntax:

switch E
begin
case V1: S1
case V2: S2
...
case Vn-1: Sn-1
default: Sn
end

Compiler Design Intermediate Code Generation March 17, 2026 55 / 61

Syntax Directed Translation
Syntax Directed Translation:
goto Ltest

L1: code for S1

goto Lnext

L2: code for S2

goto Lnext
...
Ln-1: code for Sn-1
goto Lnext

Ln: code for Sn

goto Lnext

Ltest:
if t = V1 goto L1
if t = V2 goto L2
...
if t = Vn-1 goto Ln-1
goto Ln

Lnext:
Compiler Design Intermediate Code Generation March 17, 2026 56 / 61
What is Backpatching?

Backpatching is a technique used in compiler intermediate code generation to handle forward

jumps whose targets are not yet known.
It maintains lists of incomplete jump instructions (e.g., True and False lists).
Once the target labels are generated, backpatching fills in these jump addresses.
Critical in generating code for boolean expressions, conditional statements, loops, and
switch-case.

Compiler Design Intermediate Code Generation March 17, 2026 57 / 61

Backpatching: Production Rules
E -> E1 OR M E2
backpatch([Link], [Link]);
[Link] = merge([Link], [Link]);
[Link] = [Link];

E -> E1 AND M E2
backpatch([Link], [Link]);
[Link] = [Link];
[Link] = merge([Link], [Link]);

E -> NOT E1
[Link] = [Link];
[Link] = [Link];

E -> (E1)
[Link] = [Link];
[Link] = [Link];

E -> id1 relop id2

[Link] = mklist(nextquad);
[Link] = mklist(nextquad + 1);
emit(if id1 relop id2 goto _);
emit(goto _);

Compiler Design Intermediate Code Generation March 17, 2026 58 / 61

E -> true
[Link] = mklist(nextquad);
[Link] = empty;

E -> false
[Link] = empty;
[Link] = mklist(nextquad);

M -> epsilon
[Link] = nextquad;

Compiler Design Intermediate Code Generation March 17, 2026 59 / 61

Example: A < B OR C < D AND P < Q

100: if A < B goto _

101: goto _
102: if C < D goto _
103: goto _
104: if P < Q goto _
105: goto _

Backpatch Lists:
Backpatch([Link], 102)
[Link] = 100, 104
[Link] = 103, 105

Compiler Design Intermediate Code Generation March 17, 2026 60 / 61

SDT for Procedure Call
Procedure Call: For a function fun with arguments a1 , a2 , . . . , an :

fun(a1 , a2 , . . . , an )

Syntax Directed Translation:

codeGen_expr(E):
codeGen_expr_list(arguments);
[Link] = newtemp([Link]);
[Link] = code to evaluate arguments
Param a1
Param a2
...
Param an
Call fun, n
retrieve [Link]
Where: Param pushes each argument for the function call.
Example: Statement: n = f (a[i]), where a is an integer array and f returns integer.
Three-Address Code:
t1 = i * 4
t2 = a[t1]
param t2
t3 = call f, 1
n = t3
Compiler Design Intermediate Code Generation March 17, 2026 61 / 61