School of Computing

Department of Computer Science & Engineering

10211CS107 – COMPILER DESIGN

Category : Program Core
Credit : 3

Course Handling Faculty :

Dr. T.SAJU RAJ
Associate Professor

1/28/2025 1
 COURSE CONTENT
UNIT I Introduction to Compilers 9
• Compilers – Interpreters – Analysis of the source program –Cousins of the
Compiler – Grouping of Phases – Phases of a compiler – Compiler construction
tools – Lexical Analysis – Role of Lexical Analyzer – Input Buffering –
Recognition of Tokens – Specification of Tokens. Design of a Lexical Analyzer
Generator.
• Case Study: Lexical Analyzer for separating tokens, Counting whitespace, special
characters and newline character, Pattern Matching of strings – use relevant tool.

1/28/2025 2
Dr. T SAJU RAJ
 COURSE CONTENT
UNIT II Syntax Analysis 9
• Need and Role of the parser –Writing Grammars – Context-Free Grammars – Top
Down parsing – Recursive Descent Parsing – Predictive Parsing – Bottom-up
parsing – Shift Reduce Parsing – Operator Precedence Parsing – LR Parsers – SLR
Parser – Canonical LR Parser – LALR Parser.
• Case Study: Specification for desktop calculator, Error recovery of ambiguous
arithmetic grammar, Syntax Analyzer for looping construct - use relevant tool.
•

1/28/2025 Dr. T SAJU RAJ 3

 COURSE CONTENT
UNIT III Intermediate Code Generation L–9
• Intermediate languages – Implementation of Three
Address Code – Types and Declarations – Type
Checking – Assignment Statements – Boolean
Expressions – Switch Case Statements – Back
patching – Procedure calls.
• Case Study: Intermediate code for Array references
with subscripts, Intermediate code for decision
making and looping constructs of C, Intermediate
code for Expression Parsing.
1/28/2025 4
Dr. T SAJU RAJ
 INTERMEDIATE CODE

• Intermediate code is used to translate the source code into the

machine code.
• Intermediate code lies between the high-level language and the
machine language.

1/28/2025 Dr. T SAJU RAJ 5

 •If the compiler directly translates source code into the machine
code without generating intermediate code then a full native
compiler is required for each new machine.
•The intermediate code keeps the analysis portion same for all
the compilers that's why it doesn't need a full compiler for every
unique machine.
•Intermediate code generator receives input from its
predecessor phase and semantic analyzer phase. It takes input
in the form of an annotated syntax tree.
•Using the intermediate code, the second phase of the compiler
synthesis phase is changed according to the target machine.

1/28/2025 6
Dr. T SAJU RAJ
 Intermediate Representation

Intermediate code can be represented in two ways:

1. High Level intermediate code:

2. Low Level intermediate code

1/28/2025 Dr. T SAJU RAJ 7

 1. High Level intermediate code:

• High-level intermediate code representation is

very close to the source language itself.
• They can be easily generated from the source
code and we can easily apply code
modifications to enhance performance.
• But for target machine optimization, it is less
preferred.

1/28/2025 Dr. T SAJU RAJ 8

 2. Low Level intermediate code

• This one is close to the target machine, which

makes it suitable for register and memory
allocation, instruction set selection, etc.
• It is good for machine-dependent
optimizations.

Intermediate code can be either language specific

(e.g., Byte Code for Java)
Or
Language independent (three-address code).

1/28/2025 Dr. T SAJU RAJ 9

1/28/2025 Dr. T SAJU RAJ 10
 Intermediate Languages Types

• Graphical IRs:
✓ Abstract Syntax trees
✓ Directed Acyclic Graphs (DAGs)
✓ Control Flow Graphs
• Linear IRs:
➢ Stack based (postfix)
➢ Three address code
(quadruples)

1/28/2025 Dr. T SAJU RAJ 11

• Intermediate language can be many different languages, and
the designer of the compiler decides this intermediate
language.
– syntax trees can be used as an intermediate language.
– postfix notation can be used as an intermediate language.
– three-address code (Quadraples) can be used as
an intermediate language
• we will use Quadraples to discuss intermediate
code generation
• Quadraples are close to machine instructions, but they
are not actual machine instructions.
1/28/2025 Dr. T SAJU RAJ 12
 Parse tree and Syntax tree
When you create a parse tree then it contains more
details than actually needed.
So, it is very difficult to compiler to parse the parse tree.

1/28/2025 Dr. T SAJU RAJ 13

 Take the following parse tree as an
example:

•In the parse tree, most of the leaf nodes are

single child to their parent nodes.

•In the syntax tree, we can eliminate this

extra information.

•Syntax tree is a variant of parse tree. In the

syntax tree, interior nodes are operators and
leaves are operands.

•Syntax tree is usually used when represent

a program in a tree structure.

1/28/2025 Dr. T SAJU RAJ 14

1/28/2025 Dr. T SAJU RAJ 15
 Abstract syntax tree can be represented as:

• Abstract syntax trees are important data structures in a

compiler.
• It contains the least unnecessary information.
• Abstract syntax trees are more compact than a parse tree
and can be easily used by a compiler.
1/28/2025 Dr. T SAJU RAJ 16
 x = (a + b * c) / (a – b * c)

1/28/2025 Dr. T SAJU RAJ 17

 x = (a + b * c) / (a – b * c)

1/28/2025 Dr. T SAJU RAJ 18

 Postfix Notation

• Postfix notation is the useful form of intermediate code if the

given language is expressions.
• Postfix notation is also called as 'suffix notation' and 'reverse
polish'.
• Postfix notation is a linear representation of a syntax tree.
• In the postfix notation, any expression can be written
unambiguously without parentheses.

1/28/2025 Dr. T SAJU RAJ 19

 • The ordinary (infix) way of writing the sum of x
and y is with operator in the middle: x * y. But in
the postfix notation, we place the operator at
the right end as xy *.
• In postfix notation, the operator follows the
operand.

(a – b) * (c + d) + (a – b) is :
ab – cd + *ab -+.

1/28/2025 Dr. T SAJU RAJ 20

 Three address code
• Three-address code is an intermediate code.
• It is used by the optimizing compilers.
• In three-address code, the given expression is broken
down into several separate instructions.
• These instructions can easily translate into assembly
language.
• Each Three address code instruction has at most three
operands.
• It is a combination of assignment and a binary operator.

1/28/2025 Dr. T SAJU RAJ 21

 • A statement involving no more than three references(two for
operands and one for result) is known as three address statement.
• A sequence of three address statements is known as three address
code.
• Three address statement is of the form x = y op z , here x, y, z will
have address (memory location).
• Sometimes a statement might contain less than three references but
it is still called three address statement.

1/28/2025 Dr. T SAJU RAJ 22

Example – The three address code for the expression
a+b*c+d:
T1=b*c
T2=a+T1
T3=T2+d

T 1 , T 2 , T 3 are temporary variables.

1/28/2025 23
Dr. T SAJU RAJ
 Example
Given Expression:

a := (-c * b) + (-c * d)
Three-address code is as follows:

t1 := -c
t2 := b*t1
t3 := -c
t4 := d * t3
t5 := t2 + t4
a := t5
t is used as registers in the target program.

1/28/2025 Dr. T SAJU RAJ 24

1/28/2025 Dr. T SAJU RAJ 25
 The three address code can be represented in two forms:
Quadruples, triples and indirect triples.

Quadruples:
In quadruples representation, each instruction is splitted into the
following 4 different fields-
op, arg1, arg2, result
Here-
•The op field is used for storing the internal code of the operator.
•The arg1 and arg2 fields are used for storing the two operands used.
•The result field is used for storing the result of the expression.

1/28/2025 Dr. T SAJU RAJ 26

 Exceptions:

There are following exceptions-

Exception-01:

To represent the statement x = op y, we place-

op in the operator field
y in the arg1 field
x in the result field
arg2 field remains unused

Exception-02:
To represent the statement like param t1, we place-

param in the operator field

t1 in the arg1 field
Neither arg2 field nor result field is used

Exception-03:
To represent the unconditional and conditional jump statements, we place label of the target in
the result field.
1/28/2025 Dr. T SAJU RAJ 27
 Example
a := -b * c + d
Three-address code is as follows:
t1 := -b
t2 := c + d
t3 := t1 * t2
a := t3

1/28/2025 Dr. T SAJU RAJ 28

 Triples

• The triples have three fields to implement the three

address code.
• The field of triples contains the name of the operator, the
first source operand and the second source operand.
• In triples, the results of respective sub-expressions are
denoted by the position of expression.
• Triple is equivalent to DAG while representing expressions.

1/28/2025 Dr. T SAJU RAJ 29

 Example:
a := -b * c + d

Three address code is as follows:

t1 := -b
t2 := c + d
t3 := t1 * t2
a := t3

These statements are represented by triples as follows:

1/28/2025 Dr. T SAJU RAJ 30

 Indirect Triples:

• This representation is an enhancement over triples

representation.

• It uses pointers instead of position to store results.

• This enables the optimizers to freely re-position the sub-

expression to produce an optimized code.

1/28/2025 Dr. T SAJU RAJ 31

 Problem-01:
Translate the following expression to quadruple, triple and indirect triple-
a + b *c / e ↑ f + b *c
Solution-
Three Address Code for the given expression is-

T1 = e ↑ f
T2 = b * c
T3 = T2 / T1
T4 = b *a
T5 = a + T3
T6 = T5 + T4

Now, we write the required representations-

1/28/2025 Dr. T SAJU RAJ 32

1/28/2025 Dr. T SAJU RAJ 33
1/28/2025 Dr. T SAJU RAJ 34
1/28/2025 Dr. T SAJU RAJ 35
 Problem-02:

Translate the following expression to quadruple, triple

and indirect triple-
a = b *– c + b * – c

Solution-

Three Address Code for the given expression is-

T1 = uminus c
T2 = b * T1
T3 = uminus c
T4 = b * T3
T5 = T2 + T4
1/28/2025
a = T5 Dr. T SAJU RAJ 36
1/28/2025 Dr. T SAJU RAJ 37
1/28/2025 Dr. T SAJU RAJ 38
1/28/2025 Dr. T SAJU RAJ 39
1/28/2025 Dr. T SAJU RAJ 40
1/28/2025 Dr. T SAJU RAJ 41
1/28/2025 Dr. T SAJU RAJ 42
1/28/2025 Dr. T SAJU RAJ 43
 • Assignment statements:
• x := y op z, where op is a binary operator
• x := op z, where op is a unary operator
• Copy statements
• x := y
• The unconditional jumps:
• goto L
• Conditional jumps:
• if x relop y goto L
• param x and call p, n and return y relating to procedure calls
• Assignments:
• x := y[i]
• x[i] := y
• Address and pointer assignments:
• x := &y, x := *y, and *x = y
`` Dr. T SAJU RAJ
1/28/2025 44
• Assignment: • Procedure call/return:
• x = y op z (op binary) • param x, k (x is the kth param)
• x = op y (op unary); • retval x
• x=y • call p
• Jumps: • enter p
• if ( x op y ) goto L (L a • leave p
label); • return
• goto L • retrieve x
• Pointer and indexed • Type Conversion:
assignments: • x = cvt_A_to_B y (A, B base types)
• x = y[ z ] e.g.: cvt_int_to_float
• y[ z ] = x • Miscellaneous
• x = &y • label L
• x = *y
1/28/2025 Dr. T SAJU RAJ 45
• *y = x.
 Write quadruple, triples and indirect triples for
following expression :
(x + y) * (y + z) + (x + y + z)

Three Address Code

t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

1/28/2025 Dr. T SAJU RAJ 46

 t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

1/28/2025 Dr. T SAJU RAJ 47

 t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

1/28/2025 Dr. T SAJU RAJ 48

 t1 = x + y
t2 = y + z
t3 = t1 * t2
t4 = t1 + z
t5 = t3 + t4

1/28/2025 Dr. T SAJU RAJ 49

 Syntax directed translation
scheme
❑ The Syntax directed translation scheme is a context -free grammar.

❑ The syntax directed translation scheme is used to evaluate the

order of semantic rules.

❑ In translation scheme, the semantic rules are embedded within

the right side of the productions.

❑ The position at which an action is to be executed is shown by

enclosed between braces. It is written within the right side of the
production.

1/28/2025 Dr. T SAJU RAJ 50

 Syntax directed translation
scheme
Syntax Directed Definition (SDD) is a kind of abstract
specification.

It is generalization of context free grammar in which

each grammar production X → a is associated with it a
set of production rules of the form s = f(b1, b2, ……bk)
where s is the attribute obtained from function f.

Example:
E → E1 + T { E.val = E1.val + T.val}

1/28/2025 Dr. T SAJU RAJ 51

1/28/2025 Dr. T SAJU RAJ 52
 Annotated Parse Tree
Annotated Parse Tree – The parse tree containing the values of
attributes at each node for given input string is called annotated or
decorated parse tree.

Features –
•High level specification
•Hides implementation details
•Explicit order of evaluation is not specified

1/28/2025 Dr. T SAJU RAJ 53

1/28/2025 54
Dr. T SAJU RAJ
 Types of attributes

1.Synthesized Attributes – These are those attributes which derive their

values from their children nodes.

i.e. value of synthesized attribute at node is computed from the values of

attributes at children nodes in parse tree.
Example:
E --> E1 + T { E.val = E1.val + T.val}
In this, E.val derive its values from E1.val and T.val

1/28/2025 Dr. T SAJU RAJ 55

 Types of attributes(..contd)

Inherited Attributes – These are the attributes which derive their values
from their parent or sibling nodes i.e. value of inherited attributes are
computed by value of parent or sibling nodes.

Example:
A→BCD { C.in = A.in, C.type = B.type }

Computation of Inherited Attributes –

•Construct the SDD using semantic actions.
•The annotated parse tree is generated and attribute values are computed
in top down manner.

1/28/2025 Dr. T SAJU RAJ 56

 Types of attributes(..contd)

Two attributes:
E.place, a name that will hold the value of E,
E.code, the sequence of three-address statements
evaluating E.
A function gen(…) to produce sequence of three address
statements
– The statements themselves are kept in some data structure,
e.g. list
– SDD operations described using pseudo code 5

1/28/2025 Dr. T SAJU RAJ 57

 Declarations

➢ A variable or procedure has to be declared before it can be

used.

➢ Declaration involves allocation of space in memory and entry

of type and name in the symbol table.

➢ A program may be coded and designed keeping the target

machine structure in mind, but it may not always be possible
to accurately convert a source code to its target language.

1/28/2025 Dr. T SAJU RAJ 58

 Declarations (…contd)

When we encounter declarations, we need to lay out storage for the declared
variables.
For every local name in a procedure, we create a ST(Symbol Table) entry containing:
1.The type of the name
2.How much storage the name requires

Consider the Grammar

P→D
D→D;D
D → id : T
T → integer
T → real
1/28/2025 Dr. T SAJU RAJ 59
 Declarations (…contd)

Production rule Semantic actions

S→ D {OFFSET=0}
D → id : T Enter_Tab(id.name, T.type, offset);
offset = offset + T.width
T → integer T.type = integer;
T.width = 4
T → real T.type = real;
T.width = 8

T → array [ num ] of T1 T.type = array(num.val, T1.type)

T.width = num.val x T1.width

T → *T1 T.type = pointer(T1.type)

T.width = 4
1/28/2025 Dr. T SAJU RAJ 60
 Nested Declarations

Assume following language

P→D
D → D ;D | id : T | proc id ;D ; S
• a new symbol table is created when procedure
declaration
D → proc id ; D1 ; S is seen
❖ entries for D1 are created in the new symbol table
❖ the name represented by id is local to the enclosing procedure

1/28/2025 Dr. T SAJU RAJ 61

 Assignment Statements

• Translation scheme to produce three address code for

assignment statement.
• Emit (instruction): emit a three address statement to the
output
• newtemp: return a new temporary
• lookup(identifier): check if the identifier is in the symbol
table.
• Grammar:
S→id:=E
E → E1+E2
E → E1*E2
E → -E
E →(E1)
E → id
E → num
1/28/2025 Dr. T SAJU RAJ 62
 Assignment Statements: SDD
(..contd)
Production rule Semantic actions
S→id:=E {p:=lookup(id.name);
if (p!=nil) then emit(p ‘:=‘ E.place); else
error}
E → E1+E2 {E.place = newtemp;
emit(E.place ‘:=‘ E1.place ‘+’ E2.place);}
E → E1*E2 {E.place = newtemp;
emit(E.place ‘:=‘ E1.place ‘*’ E2.place);}
E → -E1 {E.place = newtemp;
emit(E.place ‘:=‘ ‘-’ E1.place);}

E →(E1) {E.place = E1.place;}

E → id {p = lookup(id.name);
if (p!= nil) then E.place := p; else error;}
1/28/2025 Dr. T SAJU RAJ 63
E → num {E.place = num.val;}
 SDT for Assignment Statement

Production rule Semantic actions

S→id:=E S.code := E.code || gen(id.place:= E.place)
E → E1+E2 E.place:= newtmp
E.code:= E1 .code || E2 .code || gen(E.place := E1 .place +
E2 .place)
E → E1*E2 E.place:= newtmp
E.code := E1 .code || E2 .code || gen(E.place := E1 .place *
E2 .place)
E → -E1 E.place := newtmp
E.code := E1 .code || gen(E.place := - E1 .place)
E →(E1) E.place := E1 .place
E.code := E1 .code
E → id E.place := id.place
Dr. T SAJU RAJ
1/28/2025 E.code := ‘ ‘ 64
 Array references in arithmetic
expressions

Elements of arrays can be accessed quickly if the elements are stored in a

block of consecutive location. Array can be one dimensional or two
dimensional.
For one dimensional array:
1.A: array[low..high] of the ith elements is at:
2.base + (i-low)*width → i*width + (base - low*width)
Multi-dimensional arrays:
Row major or column major forms
•Row major: a[1,1], a[1,2], a[1,3], a[2,1], a[2,2], a[2,3]
•Column major: a[1,1], a[2,1], a[1, 2], a[2, 2],a[1, 3],a[2,3]
•In row major form, the address of a[i1, i2] is
•Base+((i1-low1)*(high2-low2+1)+i2-low2)*width

1/28/2025 Dr. T SAJU RAJ 65

 Translation scheme for array
elements

Limit(array, j) returns nj=highj-lowj+1

place: the temporary or variables
offset: offset from the base, null if not an array reference

The production:
1.S → L := E
2. E → E+E
3. E → (E)
4. E → L
5. L → Elist ]
6. L → id
7. Elist → Elist, E
8. Elist → id[E

1/28/2025 Dr. T SAJU RAJ 66

 Translation scheme for array
elements (...contd)

Production Rule Semantic Action

S → L := E {if L.offset = null then emit(L.place ':=' E.place)
else EMIT (L.place'['L.offset ']' ':=' E.place);
}
E → E+E {E.place := newtemp;
EMIT (E.place ':=' E1.place '+' E2.place);
}
E → (E) {E.place := E1.place;}
E→L {if L.offset = null then E.place = L.place
else {E.place = newtemp;
EMIT (E.place ':=' L.place '[' L.offset ']');
}
1/28/2025
} Dr. T SAJU RAJ 67
 Translation scheme for array
elements (...contd)

Production Rule Semantic Action

L → Elist ] {L.place = newtemp; L.offset = newtemp;
EMIT (L.place ':=' c(Elist.array));
EMIT (L.offset ':=' Elist.place '*' width(Elist.array);
}
L → id {L.place = lookup(id.name);
L.offset = null;
}

1/28/2025 Dr. T SAJU RAJ 68

 Translation scheme for array
elements (...contd)

Production Rule Semantic Action

Elist → Elist, E {t := newtemp;
m := Elist1.ndim + 1;
EMIT (t ':=' Elist1.place '*' limit(Elist1.array, m));
EMIT (t, ':=' t '+' E.place);
Elist.array = Elist1.array;
Elist.place := t;
Elist.ndim := m;
}
Elist → id[E {Elist.array := lookup(id.name);
Elist.place := E.place
Elist.ndim := 1;
}
1/28/2025 Dr. T SAJU RAJ 69
 Example with arrays

Three address code for the given code

is-
Consider the following code-
(1) prod = 0
prod = 0 ; (2) i = 1
i=1; (3) T1 = 4 x i
(4) T2 = a[T1]
do
(5) T3 = 4 x i
{ (6) T4 = b[T3]
prod = prod + a[ i ] x b[ i ] ; (7) T5 = T2 x T4
i=i+1; (8) T6 = T5 + prod
} while (i <= 10) ; (9) prod = T6
(10) T7 = i + 1
(11) i = T7
(12) if (i <= 10) goto (3)
1/28/2025 Dr. T SAJU RAJ 70
 Example

For a = b * -c + b * -c
following code is generated

t1 = -c
t2 = b * t1
t3 = -c
t4 = b * t3
t5 = t2 + t4
a = t5
1/28/2025 Dr. T SAJU RAJ 71
 Flow of Control Statements

S → while E do S1

Desired Translation is
S. begin :
E.code
if E.place = 0 goto S.after S.begin := newlabel
S1 .code S.after := newlabel
goto S.begin S.code := gen(S.begin:) || E.code ||
S.after : gen(if E.place = 0 goto S.after) ||
S1 .code || gen(goto S.begin) ||
gen(S.after:)

1/28/2025 Dr. T SAJU RAJ 72

 Flow of Control
Statements(…contd)

S → if E then S1 else S2

S.else := newlabel
Desired Translation is S.after := newlabel
E.code
S.code = E.code ||
if E.place = 0 goto S.else
gen(if E.place = 0 goto S.else) ||
S1.code
goto S.after S1.code ||
S.else: gen(goto S.after) ||
S2.code gen(S.else :) ||
S.after: S2.code ||
gen(S.after :)

1/28/2025 Dr. T SAJU RAJ 73

 SDT FOR BOOLEAN EXPRESSION

•Boolean expressions have two primary purposes.

•They are used for computing the logical values true means 1 and false means 0.

•They are also used as conditional expression using if-then-else or while-do.

Consider the grammar

E → id relop id
E → true
E → false

1/28/2025 Dr. T SAJU RAJ 74

 SDT FOR BOOLEAN EXPRESSION

Write 3AC for the boolean

expression
If(a<b) or c
Sol:
100)if a<b goto 103
101)t1=0
102)goto 104
103)t1=1
104)t2=t1 or c
105).......

1/28/2025 Dr. T SAJU RAJ 75

 SDT FOR BOOLEAN EXPRESSION

1/28/2025 Dr. T SAJU RAJ 76

 SDT FOR BOOLEAN EXPRESSION

1/28/2025 Dr. T SAJU RAJ 77

 SDT FOR BOOLEAN EXPRESSION

Syntax tree:
codeGen_bool(B, trueDst, falseDst):
relop /* base case: B.nodetype == relop */
B.code = E1.code  E2.code
 newinstr(relop, E1.place, E2.place, trueDst)
 newinstr(GOTO, falseDst, NULL, NULL);
E1 E2

Example: B  x+y > 2*z.

Suppose trueDst = Lbl1, falseDst = Lbl2.

E1  x+y, E1.place = tmp1, E1.code   ‘tmp1 = x + y’ 

E2  2*z, E2.place = tmp2, E2.code   ‘tmp2 = 2 * z’ 
B.code = E1.code  E2.code  ‘if (tmp1 > tmp2) goto Lbl1’  goto Lbl2
=  ‘tmp1 = x + y’ , ‘tmp2 = 2 * z’, ‘if (tmp1 > tmp2) goto Lbl1’ , goto Lbl2 

1/28/2025 Dr. T SAJU RAJ 78

 SDT FOR BOOLEAN EXPRESSION

Here is the example which generates the three address code using the above
translation scheme:
p>q AND r>s OR u>r
100: if p>q goto 103
101: t1:=0
102: goto 104
103: t1:=1
104: if r>s goto 107
105: t2:=0
106: goto 108
107: t2:=1
108: if u>v goto 111
109: t3:=0
110: goto 112
111: t3:= 1
112: t4:= t1 AND t2
113: t5:= t4 OR t3

1/28/2025 Dr. T SAJU RAJ 79

 Example of ICG for Boolean Statements
using SDT

1/28/2025 Dr. T SAJU RAJ 80

 Alternative : Translation of Boolean
Statements

1/28/2025 Dr. T SAJU RAJ 81

 Example : Alternative : Translation of Boolean
Statements

1/28/2025 Dr. T SAJU RAJ 82

 SDT FOR SWITCH CASE STATMENTS

❖Switch and case statement is available in a variety of languages.

❖A switch statement allows a variable to be tested for equality against a list of values.
Each value is called a case, and the variable being switched on is checked for
each switch case.
❖The syntax of case statement is as follows:

1/28/2025 Dr. T SAJU RAJ 83

 TRANSLATION OF SWITCH CASE
STATMENTS

The translation scheme for this shown below:

1/28/2025 Dr. T SAJU RAJ 84

 EXAMPLE and Solution

Generate three address code for the Three address code for the given code
following code- is-

switch (ch) if ch = 1 goto L1

{ if ch = 2 goto L2
case 1 : c = a + b; L1:
break; T1 = a + b
c = T1
case 2 : c = a – b;
goto Last
break; L2:
} T1 = a – b
c = T2
goto Last
Last:

1/28/2025 Dr. T SAJU RAJ 85

 EXAMPLE-SOLUTION
Sol:
1)t1=x+y
Construct 3AC for switch case statements
2)goto 12
Switch(x+y)
{ 3)t2=y+z
Case 1: 4)x=t2
X=y+z; 5)goto15
Break; 6)t3=w+u
Case 2: 7)v=t3
v=w+u; 8)goto15
Break; 9)t4=b+c
Default: 10)a=t4
A=b+c;
11)goto15
Break;
} 12)if t1=1 goto3
13)ift1=2 goto6
14)goto9
15).......

1/28/2025 Dr. T SAJU RAJ 86

 Back Patching

❖ Easiest way to implement the SDD for Boolean

expression is to use two passes.
❖ First, construct the Syntax Tree for the input, and then
walk the tree in depth first order, computing the
translations.
❖ The main problem with generating the code in single
pass is that during one pass we may not know the labels
that control must go to at the time the jump statements
are generated.
❖ Hence a series of branching statements with the targets
of the jumps left unspecified is generated.
❖ Then the subsequent filling in the labels is called
backpatching
Dr. T SAJU RAJ
1/28/2025 87
 Back Patching

The problem in generating three address codes

in a single pass is that we may not know the labels
that control must go to at the time jump statements
are generated.
So to get around this problem a series of
branching statements with the targets of the jumps
temporarily left unspecified is generated.
Back Patching is putting the address instead of
labels when the proper label is determined.

1/28/2025 Dr. T SAJU RAJ 88

• For non-terminal B we use two attributes B.truelist
and B.falselist together with following functions:

1/28/2025 Dr. T SAJU RAJ 89

1/28/2025 Dr. T SAJU RAJ 90
1/28/2025 Dr. T SAJU RAJ 91
 Backpatching for Boolean Expressions

1/28/2025 Dr. T SAJU RAJ 92

1/28/2025 Dr. T SAJU RAJ 93
1/28/2025 Dr. T SAJU RAJ 94
1/28/2025 Dr. T SAJU RAJ 95
 Statements that alter the flow of
control
The goto statement alters the flow of control.
If we implement goto statements then we need
to define a LABEL for a statement.

A production can be added for this purpose:

1.S → LABEL : S
2. LABEL → id

In this production system, semantic action is

attached to record the LABEL and its value in the
symbol table.
1/28/2025 Dr. T SAJU RAJ 96
 Translation scheme for statement that alters flow of
1.S → if E then S control
2. S → if E then S else S •Introduce the marker non-terminal M as in
case of grammar for Boolean expression.
3. S → while E do S
4. S → begin L end •This M is put before statement in both if then
5. S→ A else. In case of while-do, we need to put M
6. L→ L ; S before E as we need to come back to it after
7. L→ S executing S.

Here, •In case of if-then-else, if we evaluate E to be

S is a statement, true, first S will be executed.
L is a statement-list,
A is an assignment statement •After this we should ensure that instead of
and second S, the code after the if-then else will be
executed. Then we place another non-terminal
E is a Boolean-valued
marker N after first S.
expression.

1/28/2025 Dr. T SAJU RAJ 97

 The grammar is as follows:
1.S → if E then M S
1.S → if E then S
2. S → if E then M S else M S
2. S → if E then S else S
3. S → while M E do M S
3. S → while E do S
4. S → begin L end
4. S → begin L end
5. S→ A
5. S→ A
6. L→ L ; M S
6. L→ L ; S
7. L→ S
7. L→ S
8. M→ ∈
9. N→ ∈

1/28/2025 Dr. T SAJU RAJ 98

1/28/2025 Dr. T SAJU RAJ 99
 PROCEDURE CALL

• Procedure is an important and frequently used programming construct for a

compiler.

• It is used to generate good code for procedure calls and returns.

• The run time routines that handle procedure argument passing, calls and returns
are part of the run time support packages

1/28/2025 Dr. T SAJU RAJ 100

 Calling sequence:

The translation for a call includes a calling sequence of actions taken

in a entry to and exit from each procedure.

The falling are the actions that taker place in a calling sequence:

•When a procedure call occurs then space is allocated for activation record.
•Evaluate the argument of the called procedure.
•Establish the environment pointers to enable the called procedure to access
data in enclosing blocks.
•Save the state of the calling procedure so that it can resume execution after
the call.
•Also save the return address. It is the address of the location to which the
called routine must transfer after it is finished.
•Finally generate a jump to the beginning of the code for the called procedure.
1/28/2025 Dr. T SAJU RAJ 101
 ACTIVATION RECORD

1/28/2025 Dr. T SAJU RAJ 102

1/28/2025 Dr. T SAJU RAJ 103
 Let us consider a grammar for a simple procedure call statement
1.S → call id(Elist)
2. Elist → Elist, E
3. Elist → E

A suitable transition scheme for procedure call would be:

Production Rule Semantic Action

for each item p on QUEUE do
S → call id(Elist) GEN (param p)
GEN (call id.PLACE)
Elist → Elist, E append E.PLACE to the end of QUEUE
initialize QUEUE to contain only
Elist → E
E.PLACE
Queue is used to store the list of parameters in the procedure call

1/28/2025 Dr. T SAJU RAJ 104

 Practice Problems: 1

Generate three address code for the

following code-

c=0
do
{
if (a < b) then
x++;
else
x–;
c++;
} while (c < 5)

1/28/2025 Dr. T SAJU RAJ 105

 Practice Problems: 1 Solution

Solution-
Three address code for the given code is-
Generate three address code for the
1.c = 0 following code-
2. if (a < b) goto (4)
3. goto (7) c=0
4. T1 = x + 1 do
5. x = T1 {
6. goto (9) if (a < b) then
7. T2 = x – 1 x++;
8. x = T2 else
9. T3 = c + 1 x–-;
10. c = T3 c++;
11. if (c < 5) goto (2) } while (c < 5)

1/28/2025 Dr. T SAJU RAJ 106

 Practice Problems: 2

Generate three address code for the following code-

while (A < C and B > D) do

if A = =1 then C = C + 1
else
while A <= D
do A = A + B

1/28/2025 Dr. T SAJU RAJ 107

 Practice Problems: 2 Solution

Solution-
Three address code for the given code is-
1: if (A < C) goto (3)
Generate three address code for the
2: goto (15)
following code-
3: if (B > D) goto (5)
4: goto (15)
while (A < C and B > D) do
5:if (A == 1) goto (7)
if A = 1 then C = C + 1
6:goto (10)
else
7: T1 = c + 1
while A <= D
8: c = T1
do A = A + B
9: goto (1)
10: if (A <= D) goto (12)
11:goto (1)
12:T2 = A + B
13:A = T2 Dr. T SAJU RAJ
1/28/2025 108
14: goto (10)
 Practice Problems: 3

Generate three address code for the following code-

switch (ch)
{
case 1 : c = a + b;
break;
case 2 : c = a – b;
break;
}

1/28/2025 Dr. T SAJU RAJ 109

 Practice Problems: 3 Solution

Solution-
Three address code for the given code is-
if ch = 1 goto L1
if ch = 2 goto L2 Generate three address code for the
L1: following code-
T1 = a + b switch (ch)
{
c = T1
case 1 : c = a + b;
goto Last
break;
L2: case 2 : c = a – b;
T1 = a – b break;
c = T2 }
goto Last
Last:
1/28/2025 Dr. T SAJU RAJ 110
 Practice Problems: 4

Write Three Address Code for the following expression-

-(a x b) + (c + d) – (a + b + c + d)
Solution-

Three Address Code for the given expression is-

(1) T1 = a x b
(2) T2 = uminus T1
(3) T3 = c + d
(4) T4 = T2 + T3
(5) T5 = a + b
(6) T6 = T3 + T5
(7) T7 = T4 – T6

1/28/2025 Dr. T SAJU RAJ 111