Special Edition for CSEDU
CSEDU Students

Students

TOUCH-N-PASS EXAM CRAM GUIDE SERIESCOMPILERS

Prepared By

Sharafat Ibn Mollah Mosharraf
CSE, DU
12 Batch (20052005-2006)
2006)
th

Table of Contents

CHAPTER 4: SYNTAX ANALYSIS .............................................................................................................................................. 1
THEORIES ........................................................................................................................................................................................ 1
EXERCISES ...................................................................................................................................................................................... 1
CHAPTER 5: SYNTAX-DIRECTED TRANSLATIONS ............................................................................................................. 5
THEORIES ........................................................................................................................................................................................ 5
EXERCISES ...................................................................................................................................................................................... 6
CHAPTER 6: INTERMEDIATE-CODE GENERATION ........................................................................................................... 8
THEORIES ........................................................................................................................................................................................ 8
THEORIES & EXERCISES (TYPE CHECKING) ................................................................................................................................... 9
EXERCISES (OTHERS) ................................................................................................................................................................... 10
CHAPTER 8: CODE GENERATION .......................................................................................................................................... 15
THEORIES ...................................................................................................................................................................................... 15
EXERCISES .................................................................................................................................................................................... 17
CHAPTER 9: MACHINE-INDEPENDENT OPTIMIZATION ................................................................................................ 20
THEORIES ...................................................................................................................................................................................... 20
EXERCISES .................................................................................................................................................................................... 22

CHAPTER 4SYNTAX ANALYSIS
Theories
4.1

What are the error recovery strategies generally used by parser? [2006. Marks: 2]
1. Panic-Mode Recovery
2. Phrase-Level Recovery
3. Error Productions
4. Global Correction

4.2

What is ambiguous grammar? [In-course 1, 2008-2009. Marks: 1]
A grammar is ambiguous if it can have more than one parse tree generating a given string ofterminals.

4.3

What is meant by left recursion in a grammar? [In-course 2005-2006. Marks: 1]
A grammar is left recursive if it has a nonterminal A such that there is a derivation A ⇒ Aα forsome string α. For example: A → Aα | β

4.4What is the problem with a production with an immediate left-recursion in a grammar?
How can we eliminate left recursion? [2005. Marks: 3]
A production with an immediate left-recursion can cause recursive-descent and top-down
predictive parsers to loop forever.
Removing immediate left recursion:
If A → Aα1 | Aα2 | … | Aαm | β1 | β2 | … | βnThen we can rewrite the grammar as below:
A → β1A′ | β2A′ | … | βnA′A′ → α1A′ | α2A′ | … | αmA′ | ∈

4.5

4.6

Can we create LR parser table from an ambiguous grammar? When or why would one
prefer to use ambiguous grammar? Justify your answer with example. [2008, In-course 1, 20082009. Marks: 1 + 3]
Give an unambiguous grammar that is not LR(1). [2006. Marks: 3]

4.7

Define LL(k) and LR(k) grammars. Write down the basic properties of LL(1) and LR(1)grammars. [2007. Marks: 2 + 4]

4.8

What is a synchronizing set? Write down the procedure for panic mode error recovery in
LL parsing. [2005. Marks: 4]

4.9
4.10

What is the difference between LR(0) grammar and SLR grammar? [2008. Marks: 2]
What is ∈-production? How ∈-productions are handled in bottom-up parsing? Explain it
from the grammar below: [2007. Marks: 4]
S → aBB → ∈ | x

4.11

What are inadequate states? How do we try to resolve the problem associated with suchstates in SLR and LR(1) parsing? [2005. Marks: 4]

4.12

What do you understand by shift-reduce and reduce-reduce conflicts? Why these conflicts
arise? Explain rules for resolving these conflicts in parsing table. [2007. Marks: 6]

4.13

Show that the construction of an LALR parser by merging LR(1) item sets with common
core of a LR(1) grammar will not introduce any shift/reduce conflict. [2004. Marks: 4]
1

4.14

Write down the general structure of LR parsers. [2003. Marks: 4]

4.15

What does the characters L, A, L, R and 1 in the name LALR(1) parser stand for? [Incourse. Marks: 1]

4.16

Which of the LL(1), SLR(1) and LR(1) can parse the following grammar? Why? [In-course.
Marks: 2.5]
S → A | B
A → b | c
B → c | a

4.17

What does a lexical analyzer do when prefixes of the input string matches more than one
patterns? [2007, 2004. Marks: 2]

Exercises
4.1

Consider the grammar:
S → (L) | a
L → L,S | S
i.
ii.
iii.

4.2

Find parse trees for the sentencs (a, (a,a)) and (a,((a,a),(a,a))).
Construct a leftmost derivation for each of the sentences in part (i).
Construct a rightmost derivation for each of the sentences in part (i). [2003. Marks: 6]

Eliminate ambiguities for the grammar: [In-course 1, 2008-2009. Marks: 5]
E → E + E | E * E | (E) | id

4.3

Eliminate left recursion from the following grammar:
S → SX | SSb | XS | a
X → Xb | Sa | b
When does the above algorithm of eliminating left recursion fail? [2008. Marks: 3 + 2]

4.4

Consider the grammar with the set of terminals:
S → (L) | a | b
L → L,S | S
(i)
(ii)

4.5

Remove left-recursion from the grammar and find the First and Follow sets for each
non-terminal of the modified grammar.
Write down a recursive descent parser (i.e. parsing algorithm) for the modified
grammar. [2007. Marks: 5 + 5]

Consider the following grammar for arithmetic expressions.
E → E + T | E – T | T
T → T * F | T / F | F
F → (E) | id
i.
ii.

4.6

Write the above grammar eliminating immediate left recursion.
Draw the simplified transition diagram for the grammar. [2005. Marks: 4]

Consider the grammar with the set of terminals { (, ), , , a, b}:
S → (L) | a | b
L → L,S | S
a. Remove left-recursion from the grammar and find the First(1) and Follow(1) sets foreach non-terminal of the modified grammar.
b. Construct the operator precedence relation table for the grammar.
c. Find the right-most derivation in reverse for the string (a, (b, a)) and indicate the handles
at each step.
d. Draw the transition diagram of the grammar and simplify it (if possible). [2004. Marks: 3
2

+ 3 + 4 + 3 + 3]
e. Write down a recursive descent parser for the modified grammar. [In-course 2005-2006.
Marks: 5]
4.7

Left factor the following grammar: [2003. Marks: 3]
A → AabcA | Aad | AabA | Ad

4.8

Build an LL parsing table for the following grammar:
S → (L) | a
L → L,S | S
Is this an LL(1) grammar? Justify your answer. [2008. Marks: 5 + 2]

4.9

Show that the following grammar is SLR but not LR(0). [2008. Marks: 6]
S → A
A → a A
A → a

4.10

With LALR (lookahead LR) parsing, we can reduce the number of states in an LR(1) parser.
Justify the above statement using the following grammar: [2008. Marks: 8]
S → XX
X → aX
X → b

4.11

Consider the grammar: S → aSbS | bSaS | ∈. Show that the grammar is ambiguousby constructing two different left most derivations for a string. [2006. Marks: 3]

4.12

Find the LL(1) parsing table for the following grammar. Show the first and follow sets forthe non-terminals. [In-course. Marks: 4 + 4]
S → aS | Ab
A → XYZ | ∈X → cS | ∈Y → dS | ∈Z → eS

4.13

Give a grammar with the following first and follow sets. Your grammar should have noepsilon productions. The non-terminals are X, Y, Z and the terminals are a, b, c, d, e. [In-course.
Marks: 6]
X
First
Follow

4.14

a

b

c

d

e F

b, d, f b, d c, e a

b

c

d

e

$

Y

Z

c, e

a

f

$ b, d c, e c, e a $Consider the following grammar:
X → YaYb | ZbZa
Y → b
Z → a | ∈
i.
ii.
iii.
iv.

Give the parse tree for the string “babb”.
Show the sentential forms of each stage in a top-down leftmost derivation of “baa”.
Show the sentential forms of each stage in a bottom-up rightmost derivation of“babb”.
Work out the following sets: FIRST(X), FOLLOW(X), FOLLOW(Y). [2006. Marks: 2+ 3 + 3 + 3]

3

X → X + X | Y++
Y → a

4.15
i.
ii.
iii.

4.16

For the above grammar, construct the LR(1) parse table.
Point out where shift-reduce conflict(s) occurs. Give example(s) of a string(s) for
which the parser will face the conflict(s)?
If the shift-reduce conflict(s) is resolved in favor of shift, what is the associativity ofthe ‘+’ operator that corresponds to this choice? [2006. Marks: 6 + 3 + 1]

For the following grammar, construct the DFA, recognizing viable prefixes, that includes
just those states of an LR(1) parser that are pushed on the stack during a parse of the input:(id||id&. The set of terminals is { |, &, (, ), id } [2005. Marks: 8]
Bexp → Bexp || Btrm | Bexp | Btrm |Bexp → Bexp | Btrm
Bexp → Btrm
Btrm → Btrm && Bfct | Btrm & Bfct | Bfct
Bfct → (Bepr) | id

4.17

Consider the following grammar:
S → aBX | Ay
A → ab
B → a | b
Prove that this grammar is not LR(0), but is SLR(1).

4.18

Construct the LALR parse table for the following grammar that generates a subset of all
possible regular expressions. Resolve shift/reduce or reduce/reduce conflicts (if occurs) using theusual precedence rules of the operators. The set of input symbols is {|, ., *, id} [2004. Marks: 12]
R → R ‘|’ R | R.R | R* | id

4.19

Construct the LALR parser table for the following grammar. Show all the necessary steps.
[2003. Marks: 12]
P → PaQ | Q
Q → QR | R
R → Rb | c | d

4.20

Construct the predictive parsing table for the following grammar: [In-course. Marks: 6]
E → TAA → +TA | -TA | ∈T → FBB → *FB | /FB | ∈F → -S | S
S → v | (E)Show that the following grammar is not SLR(1): [In-course. Marks: 4]
S → Aa | bAc | dc | bda
A → d

4.21

Construct SLR parsing table for the following grammar. [In-course 1, 2008-2009. Marks: 10]
S → AS | b
A → SA | a

4.22

The following grammar for if-then-else statements is proposed to remedy the dangling-else
ambiguity:
stmt → if expr then stmt | matched_stmt
matched_stmt → if expr then matched_stmt else stmt | other
Justify whether this grammar is ambiguous or not. If the grammar is still ambiguous,4

rewrite the grammar by removing dangling-else ambiguity. [2003. Marks: 6]
4.23

Construct the DFA, recognizing viable prefixes, that includes just those states of an LR(1)parser for the following grammar, that are pushed on the stack during a parse of the input
y+++y. [In-course. Marks: 6]
S → A
A → A + A | B++
B → y
E → E ‘|’ T | T
T → TF | F
F → F* | F+ | (E) | a | b

4.24

i.
ii.
iii.

Modify the grammar for LL(1) parser.
Find First and Follow for each non-terminal of the modified grammar.
What are the items of the state associated with the viable prefix E | T (E in SLR
parsing for the grammar in (i). Show why the items are valid for the state. [In-course.
Marks: 4 + 6 + 6 + 4]

5

CHAPTER 5SYNTAX-DIRECTED TRANSLATIONS
Theories
5.1

5.2

Define synthesized and inherited attributes. [2003. Marks: 2]

What is L-attributed definition? “Every s-attributed definition is L-attributed” – Justify
your answer. [In-course 2, 2008-2009. Marks: 2 + 2]
An SDD is called L-attributed definition if each attribute associated with the production bodies iseither:An SDD is called s-attributed definition if every attribute is synthesized. On the other hand, Lattributed definition can have inherited attributes besides synthesized attributes. Hence, every sattributed definition is also L-attributed.
5.3

Explain how a translator for an s-attributed definition can be implemented as part ofbottom-up parser. [In-course 2, 2008-2009. Marks: 3.5]
When an SDD is s-attributed, its attributes can be evaluated in any bottom-up order of the nodesof the parse tree. It is often simple to evaluate the attributes by performing a post-order traversal of theparse tree and evaluating the attributes at a node N when the traversal leaves N for the last time. Thatis, the function postoder() defined below is applied to the root of the parse tree.
postorder(N) {for (each child C of N, from the left)
postorder(C);evaluate the attributes associated with node N;}
S-attributed definition can be implemented during bottom-up parsing, since a bottom-up parser
corresponds to a post-order traversal. Post-order corresponds exactly to the order in which an LRparser reduces a production body to its head.
6

5.4

Write an algorithm for constructing a dependency graph from a given parse tree. [In-course
2, 2008-2009. Marks: 3]
Put each semantic rule in to the form b := f(c1, c2, …, ck).
for each node n in the parse tree dofor each attribute a of the grammar symbol at n do
construct a node in the dependency graph for a;for each node n in the parse tree dofor each semantic rule b := f (c1, c2, … ,ck ) associated with the production used at n do
for i := 1 to k do
construct an edge from the node for ci to the node for b;

Exercises
5.1

Translate the arithmetic expression a*-(b+c) intoi.
A syntax treeii.
Postfix notationiii.
Three-address code [2003. Marks: 4]
*
a

minus

abc+-*

t1 = b + c
t2 = minus t1
t3 = a * t2

Postfix Notation

3-Address Code+bcSyntax Tree

5.2

Consider the following grammar for declaration of identifiers. [2003. Marks: 4]
D → TLT → integer | real
L → L, id | idi.

Write down a syntax directed definition to propagate the type information using
inherited and synthesized attributes.
ii. Rewrite the grammar so that the type information can be propagated using synthesized
attributes only.

5.3

i.
A syntax directed definition for declaring identifiers is
Productions Semantic Actions
D → TLL.in := T.type
T → int
T.type := integer
T → realT.type := real
L → L1, id L1.in := L.in,
addtype(id.entry, L.in)
L → idaddtype(id.entry, L.in)i.
Draw an annotated parse tree for the sentence real id1, id2, id3
ii.
Draw the dependency graph for the parse tree in (i). [In-course 2, 2008-2009. Marks:
3 + 3]
7

5.4

Consider the following SDD:

i.
ii.

Productions Rules
T → FT′
T′.inh = F.val
T.val = T′.syn
T′ → *FT1′ T1′.inh = T′.inh × F.val
T′.syn = T1′.synT′.syn= T′.inh
T′ → ∈
F → digit
F.val = digit.lexval
Draw the annotated parse tree for the expression 3*5*7 using the semantic rules
given above.
Draw the dependency graph. [2008. Marks: 2 + 1]

i.

ii.

8

CHAPTER 6
INTERMEDIATE-CODE GENERATION
Theories
6.1

What are the advantages of using intermediate code generation? [In-course 2, 2008-2009.
Marks: 2.5]
OR, Why would we be interested to generate intermediate code as the final product of thefront end of a compiler? [2005. Marks: 2]
With a suitably defined intermediate representation, a compiler for language i and machine j canthen be built by combining the front end for language i with the back end for machine j. This approachto creating suite of compilers can save a considerable amount of effort: m × n compilers can be built by
writing just m front ends and n back ends.

6.2

Translate the expression (a+b)*(c+d)+(b+c) intoi.
ii.

Quadruples
Triplesiii. Indirect triples [In-course 2, 2008-2009. Marks: 3]
Discuss the comparative advantages and disadvantages of the above representations. [2007.
Maks: 2]
ALSO, What are the advantages and disadvantages of using indirect triple representation of
3-address codes? [2004. Marks: 2]
t1 = a + b
t2 = c + d
t3 = t1 * t 2
t4 = b + c
t5 = t3 + t 4
3-Address Code

0
1
2
3
4

op
+
+
*
+
+

arg1
a
c
t1
b
t3

arg2
b
d
t2
c
t4

result
t1
t2
t3
t4
t5

0
1
2
3
4

Quadruples

op
+
+
*
+
+

arg1
a
c
(0)
b
(2)

arg2
b
d
(1)
c
(3)

Triples

instruction
35 (0)
36 (1)
37 (2)
38 (3)
39 (4)
…

0
1
2
3
4

op
+
+
*
+
+

arg1
a
c
(0)
b
(2)

arg2
b
d
(1)
c
(3)

Indirect Triples

Comparative Advantages and Disadvantages:
Advantages

Disadvantages

Quadruples

Instructions can be moved around without Takes more memory space thanrequiring changing all references to it.
Triples.

Triples

Takes less memory space.

Indirect
Triples

Instructions can be moved by reordering the Takes more memory space thaninstruction list, without affecting the triples Triples.
themselves. Thus, changes to all references tothe moved instruction are not needed.

Moving an instruction may requirechanging all references to it.

6.3

Find the expression that computes the relative address of the array element A[i1, i2, …, in],where A is a 10 × 10 × … × 10 array stored in row-major form. [2006. Marks: 2]

6.4

What is backpatching? What is the advantage of backpatching? Explain with an example.
[In-course 2, 2008-2009. Marks: 2 + 4]
OR, Write short notes on backpatching. [2007. Marks: 3]
Backpatching is the activity of filling up unspecified information of labels using appropriate
semantic actions during the code generation process.
In the code generation process, a separate pass is needed to bind jump labels to addresses.
9Backpatching merges the intermediate and target code generation into one pass.
Theories & Exercises (Type Checking)
6.1

Define static and dynamic type checking. [2006.
[
Marks: 3]

6.2

What are type constructors? Name and explain the basic type constructors. [2003.
[
Marks: 2+ 3]

6.3

What is name and structural equivalence of type expressions? [In-course[ course 2, 2007. Marks: 1]
1

6.4

Write type expression for the following type: An array of pointers to reals, where arrayindex ranges from 1 to 100. [2005.
2005. Marks: 2]2

6.5

Show whether the following recursive type expressions are equivalent or not: [2005. Marks:
2]

6.6

How do we determine the structural equivalence to types? [In-course[ course 2, 2007. Marks: 2]
ALSO, Give an algorithm for testing structural equivalence of type expressions and explain
how it works? [2003.
2003. Marks: 3]3

6.7

How is encoding of type expressions used for checking structural equivalence of type
expressions and what are its advantages (if any)? [2005, 2003; In-course
course 2, 2007.
2007 Marks: 3]

6.8

Consider the following grammar in a programming language. Here, P, D, T, S and E
represent the program, the declarations, types, statements and expressions respectively.
P → D; S
D → D; D | id : T
T → char | int | array[num] of T
S → id = E | if E then S | S; S
E → literal | num | id | E[E]
Write down the syntax-directedsyntax directed translation for type checking and determine eachdeclaration’s offset in the activation record. Define the basic types, type constructs andfunctions you use. [2004.
2004. Marks: 7]7

6.9

Let the following attribute grammar is used for type checking. [2008.
[2008. Marks: 5]5

Now consider the following declarations:
I: integer;
A: array[20] of integer;
B: array[20] of ^integer;10F: ^integer → integer;
Show how type checking is performed for the following expressions using the grammar
(i)
(ii)

I := B[F(A[3])]I := A[F(B[3])]Exercises (Others)
6.1

Write an SDD to generate 3-address code for the following grammar:
P → S
S → assign | if (B) S1 | S1 S2B → B1 || B2 | B1 && B2 | id1 rel id2 | true | false

According to your SDD what code will be generated for the following expression?
if (x < 100 || x > 200 && x != y) x = 0 [2008. Marks: 6 + 2]

11

Code for the expression if (x < 100 || x > 200 && x != y) x = 0:

6.2

Write a syntax-directed definition that generates three-address code for Boolean expressionof the following grammar:
E → E1 or E2 | E1 and E2 | not E1 | (E1) | id1 relop id2 | true | false

Using your definition, generate code for the expression[In-course 2, 2008-2009. Marks: 6 + 3.5]m < n or p < q and s < t[This grammar is a subset of the grammar from the above question (6.1). Just replace B with E, ||with or, && with and, ! with not, rel with relop in the following SDD.]
Code for the expression m < n or p < q and s < t :

L2:
L3:

6.3

if m < n goto L1
goto L2
if p < q goto L3
goto L4
if s < t goto L5
goto L6

Write down a SDT scheme with backpatching to generate 3-address code for the following
grammar:
S → if E then S | if E then S else S | while E do S | do S while E | {L} | A
E → E and E | E or E | not E | (E) | id relop id | true | false12L → L; S | S
Construct the annotated parse tree for the code segment below:
while (i > j) and (k < m ) do
if a > b then s = s + 1 else s = s – 1
Assume the arithmetic statements “s = s + 1” and “s = s – 1” above are generated from thenon-terminal A in the above grammar. [2003. Marks: 8 + 4]
[The grammars are similar to the following grammars:]

6.4

The following grammar generates the assignment statements of single dimensional array andidentifiers
13S → E = E
E → E + E | id | id[E]i.

Write a syntax-directed translation scheme for the grammar to produce 3-address
codes.
ii. Draw the annotated parse tree for the statement: x[i] = x[x[i]] + i, according to
your translation scheme. Assume the array x[] is a 10 element array where eachelement occupies 2 bytes. [2007. Marks: 5 + 5]
6.5

Consider the following grammar: [2007, 2005. Marks: 8 + 6]
S → if E then S | for id = NUM to NUM Step by NUM S| {L} | A
E → E or E | id relop id | id relop NUM
L → L; S | S
i. Write down a syntax-directed translation scheme with backpatching to generate 3address codes for the grammar. Assume A generates assignment statements (e.g. a = a +1) that are represented by a single quad. The semantics of “for”: id will be initialized to
the first NUM, incremented in each iteration by the amount specified by the third NUM
up to the second NUM. The token NUM is a signed integer.
ii. According to your translation scheme for the grammar in question (i), construct the
annotated parse tree for the following code fragment. Assume the 3-address codes startfrom quad 100.
for a = 1 to 10 step by 2 {if b > 10 or a < c then b = b – 1;c = c – b}a = a + 1

6.6

Consider the following grammar: [2004. Marks: 8 + 6]
S → if E then S else S | for (A; E; A) S | {L} | A
E → E and E | E or E | id relop id | id relop NUM
L → L; S | S
i.

Write down a syntax-directed translation scheme with backpatching to generate 3address codes for the grammar. Assume A generates assignment statements (e.g. a = a +1) that are represented by a single quad and “for” has the same semantics of C’s forloop.
ii. According to your translation scheme for the grammar in question (i), construct the
annotated parse tree for the following code fragment. Assume the priority of ‘and’ isgreater than that of ‘or’ and the 3-address codes start from quad 100.
if (b > 10 or a < d and a > c) then b = b – 1 else d = d + 1
a = a + 1
iii. According to your translation scheme for the grammar in question (i), construct the
annotated parse tree for the following code fragment. Assume the priority of ‘and’ isgreater than that of ‘or’ and the 3-address codes start from quad 20. [In-course 2, 2007.
Marks: 5]a = a + 1;
for (b = 0; b > a; b = b + 1) {if b < c and b > 10 then b = c – 1
else b = c - 2}
c = 2;
6.7

Consider the following grammar: [2006. Marks: 8 + 6]
S → if E then S | repeat S until E| {L} | A
E → E or E | id relop id
14

L → L; S | S
i. Write down a syntax-directed translation scheme with backpatching to generate 3address codes for the grammar. Assume A generates assignment statements (e.g. a = a +1) that are represented by a single quad and relop represents any relational operator.
ii. According to your translation scheme for the grammar in question (i), construct the
annotated parse tree for the following code fragment. Assume the 3-address codes startfrom quad 10.
repeat {a = a + 1;
if b < 10 or a > b then b = b + 1} until (a > c)
6.8

Consider the following grammar: [2006. Marks: 8 + 6]
S → if E then S | repeat S until E| {L} | A
E → E and E | id relop id | (E)L → L; S | S
i. Add production to generate “break” and “continue” statements. Write down a syntaxdirected translation scheme with backpatching to generate 3-address codes for themodified grammar. Assume:
a. A generates assignment statements (e.g. a = a + 1) that are represented by a single
quad.
b. “break” and “continue” statements have the semantics that those statements havein C language.
ii. According to your translation scheme for the grammar in question (i), construct the
annotated parse tree for the following code fragment. Assume the 3-address codes startfrom quad 100.
repeat {if (a > b and a < c) then break;a = a – b
} until (a > d)a = a + 1

6.9

The following grammar generates expressions formed by applying an arithmetic operator +to integer and real constants. When two integers are added, the resulting type is integer,
otherwise, it is real:
E → E + T | T
T → num . num | num
Give an SDD to determine the type of each sub-expression. [2006. Marks: 4]15

CHAPTER 8
CODE GENERATION
Theories
8.1

Briefly describe the issues in the design of a code generator. [In-course 3, 2008-2009. Marks:
4]
Issues in the design of a code generator:
1. Input to the Code Generator

2. The Target Program

3. Instruction Selection

4. Register Allocation

16

5. Evaluation Order

8.2

Write short notes on the following: [2003. Marks: 2 × 4]
i.
ii.

i.

Basic blocks
Peephole optimization
Basic blocks are maximal sequences of consecutive three-address instructions with theproperties thata. The flow of control can only enter the basic block through the first instruction in theblock. That is, there are no jumps into the middle of the block.
b. Control will leave the block without halting or branching, except possibly at the last
instruction in the block.

ii.

8.3

With the help of an example describe the “next-use” algorithm. [In-course 3, 2008-2009.
Marks: 4.5]•

Input: A basic block B of three-address statement. Initially the symbol table shows all
nontemporary variables in B as being live on exit.

•

Output: At teach statement i: x = y + z in B, attach to I the liveness and next-use information ofx, y, z.

•Method: Start at the last statement in B and scan backwards. At each statement i: x = y + z in
B, do
– Attach to statement i the information currently found in the symbol table regarding thenext use and liveness of x, y, z.
– In the symbol table, set x to “not live” and “no next use” (i.e., “dead”)– In the symbol table, set y and z to “live” and the next uses of y and z to i.

Example:17

Table:Initial
D
t1
D
t2
D
t3
D
t4
D
t5
D
t6
D
t7
L(0)
a
L(0)
b
prod L(0)
L(0)
i
8.4

Step 1
D
D
D
D
D
D
D
L(0)
L(0)
L(0)
L(10)

Step 2
D
D
D
D
D
D
L(9)
L(0)
L(0)
L(0)
D

Step 3
D
D
D
D
D
D
D
L(0)
L(0)
L(0)
L(8)

Step 4
D
D
D
D
D
L(7)
D
L(0)
L(0)
D
L(8)

Step 5
D
D
D
D
L(6)
D
D
L(0)
L(0)
L(6)
L(8)

Step 6
D
L(5)
D
L(5)
D
D
D
L(0)
L(0)
L(6)
L(8)

Step 7
D
L(5)
L(4)
D
D
D
D
L(0)
L(4)
L(6)
L(8)

Step 8
D
L(5)
D
D
D
D
D
L(0)
L(4)
L(6)
L(3)

Step 9
L(2)
D
D
D
D
D
D
L(2)
L(4)
L(6)
L(3)

Step 10
D
D
D
D
D
D
D
L(2)
L(4)
L(6)
L(1)

Write down the heuristic for graph coloring. What options do we have when an interferencegraph is found not to be k-colorable when there are k registers in the target machine? How do
we determine the cost of fixing that problem? [In-course. Marks: 3 + 3]
ALSO, Describe the heuristic used to color an interference graph. [In-course. Marks: 2.5]

Exercises
8.1

Describe the code generation algorithm for a 2-address machine. Generate the code for thefollowing code segment according to the algorithm. [In-course. Marks: 6 + 4]
T1 := a + c
T2 := b * T1
T3 := T1 – T2
T4 := T3
a := T3 * T4

18

8.2

Consider a hypothetical machine with four registers R1, R2, R3, R4 and six addressing
modes with the following costs.
Addressing Mode
Cost
Absolute Memory Address
1
Register0
Literal0Indirect Register1
Indirect Plus Address
1
Double Indirect2
Now use an efficient algorithm to generate code for the target machine from the following
block of 3-address codes:
t1 := a + b
t2 := t1 * c
t3 := t2 – t1
b := t3

Calculate the cost of generated code and compare with cost of code generated with naïve
approach to code generation. [2008. Marks: 8]
8.3

Draw the flow graph for the following program: [In-course 3, 2008-2009. Marks: 4]
begin
prod := 0;i := 1;do begin
prod := prod + a[i] * b[i];i := i + 1;
end
while (i <= 20);
end

8.4

8.5

8.6

Draw the flow graph for the following sequence of 3-address codes. [2008. Marks: 3]
(1)
i = 0
(9)
if t4 <= 20 goto (5)(2)
t1 = 10(10)
t6 = z[t5](3)t2 = i < t1(11)*(t7) = t6
(4)
if False t2 goto (15)(12)
t8 = 1(5)
t3 = 4(13)i = i + t9
(6)
t4 = t3 * i(14)goto (2)(7)
t5 = a + t4
(15)
return(8)
if t5 >= 100 goto (15)For the following code fragment, determine the next-use information (assume that all thevariables are live and all temporaries are dead at the end of the block). [2008. Marks: 5](1)
t6 := 4 * i(6)(2)
x := a[t6](7)(3)
t7 := 4 * i(8)(4)
t8 := 4 * j(9)(5)
t9 := a[t8]Consider the following block of 3-address code:a[t7] := t9
t10 := 4 * jb[t10] := xgoto ....

t1 := z * x
t2 := z + t1
y := t2 * z
z := x + y
t1 := z * x
y := x / t1

Use the graph coloring algorithm for register allocation for the block of code given above.
19

Assume the number of registers is R = 3 and all temporaries are dead at the end of the block.
[2008. Marks: 6]
Liveness Information:
t1 := z * x
t2 := z + t1
y := t2 * z
z := x + y
t1 := z * x
y := x / t1

Interference Graph with Coloring:{x, z}{x, z, t1}{x, z, t2}{x, y}{x, z}{x, z, t1}{x, y, z}

Stack: t1, z, t2, x, y

20

x

z

y

t2

t1

CHAPTER 9
MACHINE-INDEPENDENT OPTIMIZATIONS
Theories
9.1

What do you understand by peephole optimizations? [In-course 3, 2008-2009. Marks: 4]

9.2

What is a copy statement? When can we eliminate copy statements? Give an example. [2007,2004. Marks: 4]
Assignments of the form u = v are called copy statements.
We can eliminate copy statements when there are common sub-expressions in statements.
Example:9.3

What is meant by dead code? Give examples. [2007. Marks: 2]
Dead code are statements that compute values that never get used.
For example, suppose a variable debug is set to FALSE at various points in the program, and usedin statements like if (debug) print… If copy propagation replaces debug by FALSE, then the printstatement is dead because it cannot be reached. Hence, both the test and the print operation can beeliminated from the object code.

21

9.4

In order to generate optimized code, you have the options to do dead-code elimination, copy
propagation, CSE (Common Sub-expression Elimination), global register allocation andinstruction scheduling. In which order would you perform these operations? Justify your choicewith proper reasoning. [2006. Marks: 5]
1. First of all, copy propagation should be performed. It would increase the possibility of finding
2.
3.
4.
5.

9.5

9.6

common sub-expressions.
Then, CSE should be performed.
After these two steps, there would be a good possibility of existence of dead-code. So, at thisstage, dead-code elimination should be performed.
Then, instruction scheduling might increase the chance of a more efficient register allocation.
So, it should be performed.
Finally, Register allocation should be applied.

Define UD- and DU-chains. What purposes do they serve? [2007, 2004. Marks: 4]
UD-Chain:Purpose of UD-Chain:

DU-Chain:Purpose of DU-Chain:

What are the techniques to optimize a loop? Describe any one of them. [In-course 3, 20082009. Marks: 3.5]
ALSO, What is the basic loop optimization technique? [2004. Marks: 1]
The techniques to optimize a loop are as follows:
1. Code Motion
2. Induction-Variable Elimination
3. Reduction in Strength
The basic loop optimization technique is code motion. If an expression is computed within a loop
and it does not depend on variables that change in the loop, then it can be moved to just before theloop.
Example:22

9.7

Why would you be concerned to find whether a flow graph is reducible or not? [2007.
Marks: 2]
OR, For loop optimization, why are we interested in determining whether a flow graph isreducible or not? [2004. Marks: 2]

9.8

Write down an algorithm for detecting loop invariant computations. [2007, 2005. Marks: 6]

Exercises
9.1

Consider the following fragment of intermediate code:
y = w
z = 4
v = y * yu = z + 2
r = w ** 2 //this is exponentiationt = r * v
s = u * t

Assume the only variable live at the exit is s. Show the result of applying constantpropagation, algebraic simplification, common sub-expression elimination, constant folding,copy propagation and dead code elimination as much as possible to this code. You should
explain the changes in each step. [2007, 2005. Marks: 6]
y = w
z = 4
v = y * y
= w * w
u = z + 2
= 4 + 2= 6
r = w ** 2
= w * w
= v

[Copy Propagation][Constant Propagation][Constant Folding][Algebraic Simplification][Common Sub-expression Elimination]23t = r * v= v * vs = u * t
= 6 * t[Copy Propagation][Constant Propagation]

After dead-code elimination:v = w * w
t = v * v
s = 6 * t

9.2

Consider the following fragment of intermediate code:
w = 2
u = z
y = w + 1
v = y * yr = v ** 2 //this is exponentiationt = u * us = u * tx = y * yAssume the only variables live at the exit are s, x. Show the result of applying constantpropagation, algebraic simplification, common sub-expression elimination, constant folding,copy propagation and dead code elimination as much as possible to this code. You should
explain the changes in each step. [In-course. Marks: 4]
w = 2
u = z
y = w + 1
= 2 + 1= 3
v = y * y
= 3 * 3= 9
r = v ** 2
= v * v
= 9 * 9= 81
t = u * u
= z * zs = u * t
= z * tx = y * y
= 3 * 3= 9[Constant Propagation][Constant Folding][Constant Propagation][Constant Folding][Algebraic Simplification][Constant Propagation][Constant Folding][Copy Propagation][Copy Propagation][Constant Propagation][Constant Folding]After dead-code elimination:t = z * zs = z * t
x = 9

9.3

For the following code fragment, list all the dependencies between statements and draw thedependency graph. [2006. Marks: 3]
(1)
(2)
(3)
(4)

j = 4
k = j + 1
j = 6
m = k * j

(5)
(6)
(7)

m = m + 2
k = j + l
j = k + j

List of dependencies between statements:
1. (2) depends on (1) for value of j.
2. (4) depends on both (2) and (3) for values of k and j respectively.
3. (5) depends on (4) for value of m.
24

4. (6) depends on (3) for value of j.
5. (7) depends on both (3) and (6) for values of j and k respectively.
Dependency Graph:Let, for statements A and B, A

B denotes that A is dependent on B.
1

2

3
7

4

9.4

5

6

Consider the following code fragment. [2003. Marks: 3 + 2 + 7]
begin
for i := 1 to n do
for j := 1 to n do
begin
c[i,j] := 0;for k := 1 to n do
c[i,j] = c[i,j] + a[i,k] * b[k,j];
end
end
i.
ii.
iii.

9.5

Assume a, b and c are allocated static storage and there are 2 bytes per word in a byte
addressable memory. Produce three-address code for the code fragment.
Construct the flow graph from the three address statement.
Optimize the code by eliminating common sub-expressions, eliminating dead-codeand different loop optimization techniques.

Consider the following code segment. [2006. Marks: 3 + 5 + 4]
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
i.
ii.

iii.
9.6

i = b + cb = 10k = 9
a = b + c
d = e + f
k = j + 1
if p > 10 goto (9)goto (11)
e = 5

(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)

goto (13)g = -kf = d + 4
c = 25h = e + 10
j = b + j
if q > 10 goto (4)exitDraw the control flow graph (CFG).
Perform global CSE and draw the CFG for the code that results from CSE. You neednot to show the computation for finding available expressions. Only show theavailable expressions at the input of each basic block.
Find all natural loops and identify the loop invariant statements. Which statements
are safe to be moved to the loop’s pre-header and why?

Consider the code segment below: [2004. Marks: 3 + 6]
(1)
(2)
(3)
(4)
(5)
(6)
(7)

m = 5
f = 0
g = 1
if m < 10 goto (6)return mi = 2
if i < m goto (9)i. Construct a flow graph.
ii. Find the live variables at the end of each block.

25

(8)
(9)
(10)
(11)
(12)
(13)

return g
h = f – g
g = f
f = h
i = i + 1
goto (7)

m=5
f=0
g=1
if m < 10 goto B3

B1

use B1 = {}def B1 = {m, f, g}

B2

return m

use B2 = {m}def B2 = {}

B3

i=2

use B3 = {}def B3 = {i}B4

if i < m goto B6

use B4 = {i, m}
def B4 = {}B5

return g

use B5 = {g}def B5 = {}

h=f–g
g=f
f=h
i=i+1
goto B4

B6

use B6 = {f, g, i}
def B6 = {f, g, h, i}IN[B]0OUT[B]1

IN[B]1

OUT[B]2

IN[B]2OUT[B]3

IN[B]3

B1{}{ f, g, m }{}{ f, g, m }{}{ f, g, m }

{}

B2

{}

{}

{m}

{}

{m}

{}

{m}

B3

{}

{ f, g, i, m }{ f, g, m }{ f, g, i, m }{ f, g, m }{ f, g, i, m }{ f, g, m }B4{}{ f, g, i }{ f, g, i, m } { f, g, i, m } { f, g, i, m } { f, g, i, m } { f, g, i, m }

B5

{}

{}

{g}

B6

{}

{}

{ f, g, i }

{}

{g}

{}

{g}

{ f, g, i, m } { f, g, i, m } { f, g, i, m } { f, g, i, m }∴ Live variables after each block:
B1: { f, g, m }B2: { }
B3: { f, g, i, m }B4: { f, g, i, m }B5: { }
B6: { f, g, i, m }[Points to be noted from this answer:
1. There is no edge from the block containing return m to the following block, because after
returning from a block, the program never flows below in the block. The same case holds for
return g, too. This is according to the rule of putting an edge in flow graph (from page 529,
bullet point no. 2).
2. As there is no edge outgoing from return m, hence its OUT is empty. However, its IN is not
empty as it uses m.
3. Block B4 should be counted – even though there is no variable assignment statement. That’s
because the compiler must know to before comparing i < m whether both are live or not. And
after the end of the block, should i and m be dead and discarded or not. Similarly, m in B1
should also be counted.
4. m is not used in B1 as can be mistakenly assumed from the if instruction. That’s because m is26

defined before it is used in this block. From the definition of useB (from page 609, point 2), m
is not used. Similarly, h is not used in B6. (Also see page 609, the paragraph after Example
9.13 for further clarification.)
5. Although usually live variable analysis includes a block containing EXIT, in this particularcase, there should be no exit block. That’s because the last block B6 includes as its laststatement an unconditional jump – goto B3, after executing which the program control will
always flow to B4 and never to any other block.]
9.7

Consider the following sequence of 3-address codes: [In-course. Marks: 4 + 6]
(1)
(2)
(3)
(4)
(5)
(6)
(7)

e = e – bd = a * cif e < d goto (1)i = e + f
j = a + b
c = c * 2
if c > d goto (9)

(8)
(9)
(10)
(11)
(12)
(13)
(14)

goto (11)g = a * cgoto (13)i = d * dj = c + 1
if i > j goto (5)exiti. Draw the flow graph.
ii. Compute live variables at the end of each block using the iterative solution to dataflow
equations for live variable analysis.
9.8

Consider the following sequence of 3-address codes: [In-course. Marks: 2 + 6 + 2]
(1)
(2)
(3)
(4)
(5)
(6)
(7)

c = a + b
d = a * ce = d * di = 1f[i] = a + b
c = c * 2
if c > d goto (9)

(8)
(9)
(10)
(11)
(12)
(13)
(14)

goto (11)g[i] = a * cgoto (13)g[i] = d * di = i + 1
if i > 10 goto (5)exiti. Draw the flow graph.
ii. Compute the available expressions at the beginning of each block using the iterative
solution to dataflow equations for available expressions.
iii. Draw the flow diagram after global CSE.
9.9

Consider the following sequence of 3-address codes: [2007. Marks: 4 + 6]
(1)
(2)
(3)
(4)
(5)
(6)
(7)

a = a – df = b * dc = a + b
d = c – aif d > x goto (7)d = b * db = a + b

(8)
(9)
(10)
(11)
(12)
(13)
(14)

e = c – aif e > 10 goto (3)goto (13)a = b * db = a – dif b > 10 goto (1)exit

i. Draw the flow graph.
ii. Compute live variables at the end of each block using the iterative solution to dataflow
equations for live variable analysis.
iii. Show the execution of the algorithm solving the data flow equations set up for available
expressions. [In-course. Marks: 6]
9.10

Consider the following sequence of 3-address codes: [2005. Marks: 2 + 5]
(1)
(2)
(3)
(4)
(5)
(6)

i = m – 1
j = n
a = u1i = i + 1
j = j - 1
if i > j goto (8)

(7)
(8)
(9)
(10)
(11)

27

goto (9)a = u2i = u3
if u3 > 0 goto (4)exiti. Draw the flow graph.
ii. Find the definitions reaching the end of each block by iteratively solving the dataflow
equations for reaching definitions.

∴ Definitions reaching at the end of each block:
B1: { d1, d2, d3 }B2: { d3, d4, d5, d6 }B3: { d4, d5, d6 }B4: { d3, d5, d6, d7 }9.11

Consider the following flow graph: [In-course 3, 2008-2009. Marks: 4 + 2]
i. Compute UD and DU-chain for the flow graph.
ii. Compute live variables at the end of each block of the flow
graph.
i. UD-Chain:[•, •][•]

DU-Chain:

28

[•]

[• ]

[•]

9.12

Consider the following flow graph: [2008. Marks: 4 + 2 + 2 + 4 + 4]

i. Compute UD and DU-chain for the above flow graph.
ii. Compute live variables at the end of each block of the flow graph.
iii. Compute available expressions for the flow graph.
iv. Is any constant folding possible in the flow graph? If so, do it.
v. Are there any common sub-expressions in the flow graph? If so, do it.
9.13

Consider the CFG below where only definition (v = …)
and use (… = v) of the interesting variables are shown.
i. List the webs as webi = {list of statements Sks inwebi}.
ii. Draw the interference graph.
iii. If coloring is possible and if you have three registers
R0, R1, R2, identify for each node the allocatedregister allocation. Assume the variable k cannot beallocated to register R2. Otherwise, which node
would you choose to spill and why? [2006. Marks: 2+ 3 + 3]

29

9.14

Consider the CFG below where only definition (v = …)
and use (… = v) of the interesting variables are shown.
i. List the webs as webi = {list of statements Sks inwebi}.
ii. Draw the interference graph.
iii. If you have three registers, show the code after
register allocation (if coloring is possible). [2005.
Marks: 2 + 3 + 3]30