V.S.

B Engineering College, Karur - 639 111

(An Autonomous Institution, Affiliated to Anna University, Chennai)
Question Paper Code: 231569
B.E / B. Tech. End Semester Theory Examinations, April/May 2024
Fifth Semester
Computer Science and Engineering
CS 3501 - COMPILER DESIGN
(Regulations 2021)
Part - A (10 x 2 = 20 Marks)
1. Describe the two parts of a compilation.
Analysis and Synthesis are the two parts of compilation. The analysis part breaks
up the source program into constituent pieces and creates an intermediate representation of
the source program. The synthesis part constructs the desired target program from the
intermediate representation.
2. Outline the various compiler construction tools.
Compiler Construction Tools are specialized tools that help in the implementation
of various phases of a compiler. These tools help in the creation of an entire compiler or its
parts.
Some of the commonly used compiler constructions tools are:-
i. Parser Generator
ii. Scanner Generator
iii. Syntax Directed Translation Engines
iv. Automatic Code Generators
v. Data-Flow Analysis Engines
vi. Compiler Construction Toolkits
3. Define an ambiguous grammar
A grammar or a Context-Free Grammar (CFG) is said to be ambiguous if there exists more
than one leftmost derivation(LMDT) or more than one rightmost derivation(RMDT), or more than
one parse tree for a given input string.
Context-free grammar (CFG) represented by G = (N, T, P, S) is said to be ambiguous
grammar if there exists more than one string in L(G). Otherwise, the grammar will be
unambiguous.
One thing that should be transparent is that ambiguity is a property of grammar and not a
language.
Since Ambiguous Grammar can produce two Parse trees for the same expression, it's often
confusing for a compiler to find out which one among all available Parse Trees is the correct one
according to the context of the work. This is the reason ambiguity is not suitable for compiler
construction.
4. State Dangling reference
A dangling reference occurs in computer programming when a program attempts to access
a memory location that has already been deallocated or freed. This can happen, for example, when
a pointer points to a memory location that has been freed, but the pointer itself has not been updated
or cleared. As a result, attempting to access the memory through the dangling reference can lead to
undefined behavior, crashes, or security vulnerabilities. Dangling references are a common source
of bugs in programs, particularly in languages like C or C++ where manual memory management is
required.
5. Summarize the two rules for type checking
There are two main type checking algorithms: syntactic and semantic type checking in
compiler design. Syntactic type checking in compiler design involves verifying that the syntax of
the program is correct. This can be done using a parser to check for syntactic errors.
6. Infer Backpatching
Backpatching is basically a process of fulfilling unspecified information. This information
is of labels. It basically uses the appropriate semantic actions during the process of code generation.
It may indicate the address of the Label in goto statements while producing TACs for the given
expressions. Here basically two passes are used because assigning the positions of these label
statements in one pass is quite challenging. It can leave these addresses unidentified in the first pass
and then populate them in the second round. Backpatching is the process of filling up gaps in
incomplete transformations and information.
7. Mentiona the limitations of Static Allocation
i. The static allocation can be done only if the size of the data object is known at compile
time.
ii. The data structures can not be created dynamically. In the sense that, the static allocation
can not manage the allocation of memory at run time.
iii. Recursive procedures are not supported by this type of allocation.
8. Recall Symbol Table
The symbol table is defined as the set of Name and Value pairs.
Symbol Table is an important data structure created and maintained by the compiler in
order to keep track of semantics of variables i.e. it stores information about the scope and binding
information about names, information about instances of various entities such as variable and
function names, classes, objects, etc.
9. Discuss the main idea of dead code elimination and constant folding
Dead code refers to sections of code within a program that is never executed during
runtime and has no impact on the program’s output or behavior. Identifying and removing dead
code is essential for improving program efficiency, reducing complexity, and enhancing
maintainability.
Constant folding is an optimization technique in which the computation of constant is done at
compile time instead of execution time.
10. Write down the liveness of a variable calculation
A variable is live at any instant of time, during the process of compilation of a program
if its value is being used to process a computation as the evaluation of an arithmetic
operation at that instant or it holds a value that will be used in the future without the
variable being re-defined at any intermediate step.

PART - B (5 X 13 = 65 Marks)
11. a) Explain the various phases of compiler and trace i with the program segment
i=i*70+j+2.
A compiler is a computer program that decodes computer code composed in one
programming language into another language.
The 6 phases of a compiler are:
i. Lexical Analysis
ii. Syntactic Analysis or Parsing
iii. Semantic Analysis
iv. Intermediate Code Generation
v. Code Optimization
vi. Code Generation

1. Lexical Analysis:
Lexical analysis or Lexical analyzer is the initial stage or phase of the compiler. This phase
scans the source code and transforms the input program into a series of a token.
A token is basically the arrangement of characters that defines a unit of information in the source
code.
2. Syntax Analysis:
In the compilation procedure, the Syntax analysis is the second stage. Here the provided
input string is scanned for the validation of the structure of the standard grammar. Basically, in the
second phase, it analyses the syntactical structure and inspects if the given input is correct or not in
terms of programming syntax
3. Semantic Analysis:
In the process of compilation, semantic analysis is the third phase. It scans whether the
parse tree follows the guidelines of language. It also helps in keeping track of identifiers and
expressions. In simple words, we can say that a semantic analyzer defines the validity of the parse
tree, and the annotated syntax tree comes as an output.
4. Intermediate Code Generation:
The parse tree is semantically confirmed; now, an intermediate code generator develops
three address codes. A middle-level language code generated by a compiler at the time of the
translation of a source program into the object code is known as intermediate code or text.

5. Code optimizer:
Now coming to a phase that is totally optional, and it is code optimization. It is used to
enhance the intermediate code. This way, the output of the program is able to run fast and consume
less space. To improve the speed of the program, it eliminates the unnecessary strings of the code
and organizes the sequence of statements.
6. Code Generator:
The final stage of the compilation process is the code generation process. In this final
phase, it tries to acquire the intermediate code as input which is fully optimized and map it to the
machine code or language. Later, the code generator helps in translating the intermediate code into
the machine code.

11. b) (i) Discuss in detail about the lexical analysis phase with the possible error recovery
schemes.
Lexical Analysis:
Lexical analysis is the first phase of the compiler where the source code is scanned and
broken down into meaningful components called tokens. These tokens are the smallest units of a
program, such as keywords, identifiers, constants, operators, and punctuation symbols. The
primary goal of lexical analysis is to transform the source code into a sequence of tokens for further
processing by the compiler.
Overview of how lexical analysis works:
i. Scanning: The source code is read character by character, and sequences of characters are
matched against predefined patterns to identify tokens.
ii. Tokenization: Once a sequence of characters matches a pattern, it is recognized as a token
and classified accordingly (e.g., as a keyword, identifier, operator, etc.).
iii. Error Handling: If the scanner encounters invalid characters or sequences that don't
match any predefined patterns, it generates a lexical error.
iv. Output: Finally, the scanner produces a stream of tokens, which are passed on to the next
phase of the compiler for further processing.
Error Recovery Schemes:
Error recovery in lexical analysis refers to the strategies used to handle lexical errors
encountered during scanning. Here are some common error recovery schemes:
i. Panic Mode Recovery: In this scheme, the scanner skips ahead in the source code until it
finds a predefined "synchronization token" before resuming normal scanning. For
example, if an error is encountered, the scanner might skip ahead until it finds the next
semicolon or closing brace.
ii. Global Correction: Instead of just skipping ahead, the scanner might attempt to identify
the likely point of error recovery based on the structure of the language and continue
scanning from there. This approach often involves more sophisticated algorithms to
determine the most appropriate recovery point.
iii. Error Reporting: Along with error recovery, it's essential to provide informative error
messages to the user, indicating the location and nature of the lexical error. This helps the
 programmer quickly identify and fix the issue in the source code.
iv. Partial Token Recovery: Sometimes, the scanner can recover from errors within a token
and continue scanning the rest of the source code. For example, if a numeric constant is
missing its closing quote, the scanner might still recognize the numeric part of the token
and continue scanning.
v. Interactive Error Handling: In interactive environments like IDEs, the lexical analyzer
might provide real-time feedback to the user, highlighting lexical errors as they type and
offering suggestions for correction.
Each error recovery scheme has its advantages and disadvantages, and the choice of scheme
often depends on factors such as the complexity of the language, the desired level of error
tolerance, and the performance requirements of the compiler.

11. b) (ii) Write the regular Expression for Delimiters and keywords and draw the
transition
diagram for the same.
(6)
Regular Expressions for Delimiters and Keywords
Delimiters
Common delimiters in programming languages include symbols like commas,
semicolons, parentheses, braces, and brackets. Here are the regular expressions for these
delimiters:
 Comma: ,
 Semicolon: ;
 Parentheses: \( and \)
 Braces: { and }
 Brackets: \[ \]
The combined regular expression for all delimiters can be written as:
[,;(){}[\]]

Keywords
Keywords are reserved words in a programming language that have a predefined
meaning. Here is a list of some common keywords and their regular expressions:
 if: if
 else: else
 while: while
 return: return
 int: int
 float: float
 void: void
The combined regular expression for these keywords can be written as:
if|else|while|return|int|float|void
Transition Diagram
A transition diagram for delimiters and keywords involves creating states and
transitions based on the input characters. Here’s a simplified version of such a diagram.
Delimiters Transition Diagram
State 0:
, --> State 1
; --> State 2
( --> State 3
) --> State 4
{ --> State 5
} --> State 6
[ --> State 7
] --> State 8
Each state corresponds to recognizing one specific delimiter.
 Keywords Transition Diagram
Here’s a transition diagram for a few keywords (if, else, while, return, int,
float, void):
State 0:
i --> State 1
e --> State 9
w --> State 15
r --> State 22
f --> State 29
v --> State 35

State 1:
f --> State 2 (if recognized)
n --> State 3
t --> State 4

State 2: (if recognized)

State 3:
t --> State 4

State 4:
(end of keyword int, return recognized)

State 9:
l --> State 10

State 10:
s --> State 11

State 11:
e --> State 12 (else recognized)

State 12: (else recognized)

State 15:
h --> State 16

State 16:
i --> State 17

State 17:
l --> State 18

State 18:
e --> State 19 (while recognized)

State 19: (while recognized)

State 22:
e --> State 23

State 23:
t --> State 24

State 24:
u --> State 25

State 25:
r --> State 26

State 26:
n --> State 27 (return recognized)
State 27: (return recognized)

State 29:
l --> State 30

State 30:
o --> State 31

State 31:
a --> State 32

State 32:
t --> State 33 (float recognized)

State 33: (float recognized)

State 35:
o --> State 36

State 36:
i --> State 37

State 37:
d --> State 38 (void recognized)

State 38: (void recognized)

Explanation of the Transition Diagram
1. State 0 is the starting state. From here, the lexer transitions based on the first character
of the input.
2. States 1-2 handle the keyword if.
3. States 3-4 handle the keyword int.
4. States 9-12 handle the keyword else.
5. States 15-19 handle the keyword while.
6. States 22-27 handle the keyword return.
7. States 29-33 handle the keyword float.
8. States 35-38 handle the keyword void.
Each state transition is triggered by the corresponding character in the keyword or
delimiter. When the lexer reaches the final state for a keyword or delimiter, it recognizes
that token and transitions back to the start state (or continues processing the next
characters).

12. a) (i) Describe in detail about issues in syntax analysis

(7)
Syntax Analysis or Parsing is the second phase, i.e. after lexical analysis. It
checks the syntactical structure of the given input, i.e. whether the given input is in the
correct syntax (of the language in which the input has been written) or not. It does so by
building a data structure, called a Parse tree or Syntax tree. The parse tree is constructed
by using the pre-defined Grammar of the language and the input string. If the given input
string can be produced with the help of the syntax tree (in the derivation process), the
input string is found to be in the correct syntax. if not, the error is reported by the syntax
analyser.
Basic Issues in Parsing:
There are two important issues in parsing:
i. Specification of syntax
ii. Representation of input after parsing
 A very important issue n parsing is specification of syntax in programming
language. Specification of syntax means how to write any programming
statement.
 There are certain characteristic of specification of syntax:
i. This specification should be precise and unambiguous.
ii. This specification should be in detail, [Link] should cover all the details of
the programming language.
iii. This specification should be complete.
Such a specification is called “Context Free Grammar”.
 Another important issue in parsing is representation of the input after parsing.
This is important because all the subsequent phases of compiler take the
information from the parse tree being generated. This is important because the
information suggested by any input programming statement should not be
differed after building the syntax tree for it.
 Lastly the most crucial issue is the parsing algorithm based on which we get the
parse tree for the given input. We will discuss different approaches to parsing:
Top-down and Bottom-up. And we will study parsing algorithms concerning to
these approaches.

12. a) (ii) Explain the operations on strings with suitable example for each.
(6)
The string operations are shown in the following table.

Traditional
Operation Free-Form Syntax
Syntax
CAT (Concatenate
Concatenate + operator
Two Strings)
%CONCAT (Concatenate with
Concatenate strings with a separator
Separator)
Concatenate array elements with a %CONCATARR (Concatenate
separator Array Elements with Separator)
%LOWER (Convert to Lower
Convert to lower case
Case)
%UPPER (Convert to Upper
Convert to upper case
Case)
CHECK (Check
Check %CHECK (Check Characters)
Characters)
CHECKR (Check
Check Reverse %CHECKR (Check Reverse)
Reverse)
%STR (Get or Store
Create
Null-Terminated String)
%REPLACE (Replace Character
Replace
String)
SCAN (Scan
Scan %SCAN (Scan for Characters)
String)
%SCANR (Scan Reverse for
Scan Reverse
Characters)
%SCANRPL (Scan and Replace
Scan and Replace
Characters)
%SPLIT (Split String into
Split a string
Substrings)
 Traditional
Operation Free-Form Syntax
Syntax
%SUBST (Get Substring)
%LEFT (Get Leftmost
Substring SUBST (Substring) Characters)
%RIGHT (Get Rightmost
Characters)
Translate XLATE (Translate) %XLATE (Translate)
%TRIM (Trim Characters at
Edges)
%TRIML (Trim Leading
Trim Blanks
Characters)
%TRIMR (Trim Trailing
Characters)
Return the leftmost characters of a %LEFT (Get Leftmost
string Characters)
Return the number of bytes for
alphanumeric or double bytes for %LEN (Get or Set Length)
UCS-2 and graphic
Return the number of natural %CHARCOUNT (Return the
characters Number of Characters)
Return the rightmost characters of a %RIGHT (Get Rightmost
string Characters)
%STR (Get or Store
Work with a null-terminated string
Null-Terminated String)
Table 1. String Operations
 The string operations include concatenation, scanning, substringing, translation,
and verification. String operations can only be used on character, graphic, or
UCS-2 fields.
 The CAT operation concatenates two strings to form one.
 The CHECK and CHECKR operations verify that each character in factor 2 is
among the valid characters in factor 1. CHECK verifies from left to right and
CHECKR from right to left.
 The SCAN operation scans the base string in factor 2 for occurrences of another
string specified in factor 1.
 The SUBST operation extracts a specified string from a base string in factor 2. The
extracted string is placed in the result field.
 The XLATE operation translates characters in factor 2 according to the from and to
strings in factor 1.

(OR)

b) Explain the lex program for tokens and describe in detail the tool for generating
lexical analyzer with an example program (13)
Lex is a powerful tool used for generating lexical analyzers, also known as scanners
or tokenizers, for processing text. It operates by recognizing patterns in an input stream and
translating those patterns into a series of tokens for further processing by a parser or other
components of a compiler or interpreter.
Here's a breakdown of how Lex works:
1. Defining Patterns: In Lex, you start by defining patterns using regular
expressions. Regular expressions are a concise way of describing sets of strings.
 For example, the regular expression "[a-zA-Z]+" matches one or more
occurrences of any uppercase or lowercase letter.
2. Associating Actions: Along with each pattern, you can specify an action to be
performed when that pattern is matched. Actions are typically written in C, though
Lex supports other programming languages as well. These actions can include
tasks like outputting a token, manipulating the input buffer, or invoking other
functions.
3. Compilation: Once you've defined your patterns and associated actions in a Lex
file (usually with a .l extension), you compile it using the Lex compiler (lex or
flex). This produces a C program that implements the lexical analyzer.
4. Integration with Other Components: Finally, you integrate the generated lexical
analyzer into your larger program. This typically involves incorporating the
generated C code into your project and linking it with other components, such as a
parser.
13. a) Compute if the following grammar is a LALR grammar or not and parse the
string.
Cdd
S->CC
C->cC|d. (13)

Solution:
Step1 − Construct LR (1) Set of items. First of all, all the LR (1) set of items should be
generated.

 In these states, states I3 and I6 can be merged because they have the same core or
first component but a different second component of Look Ahead.
Similarly, states I4 and I7 are the same.
Similarly, states I8 and I9 are the same.
So, I3 and I6 can be combined to make I36.
I4 and I7 combined to make I47.
I8 and I9 combined to make I89.
So, the states will be

∴ I3 = goto (I0, c)
But I3 , I6 combined to make I36
∴ I36 = goto (I0, c)
∴ I4 = goto (I0, d)
But I4 , I7 combined to make I47
∴ I47 = goto (I0, d)
∴ I6 = goto (I2, c)
∴ I36 = goto (I2, c)
∴ I7 = goto (I2, d)
∴ I47 = goto (I2, d)
∴ goto (I3, C) = I8
But I8 is now part of I89
∴ goto (I36, C) = I89
Similarly,goto (I3, d) = I4, goto (I6, d) = I7 ∴ goto (I36, d) = I47
Construction of LALR Parsing Table
Filling of "𝐬𝐡𝐢𝐟𝐭" Entries(s)
Consider goto(I0, c) = I36
∴ Action[0, c] = s36
∴ Write s36 in front of Row state 0 and column c.
Similarly, consider
goto(I2, d) = I47
∴ Action[2, d] = 47
∴ Write s47 in front of Row State 2 and column d.
Filling the "𝐫𝐞𝐝𝐮𝐜𝐞" Entries (r)
Consider productions of the form A → α ∙ ,
For example, Consider State
I47 = goto(I0, d)
C → d ∙, c |d |$
∴ C → d ∙, c |d |$ is of form A → α ∙ , a.
Since C → d is production number (3) in given Question.
∴ Write r3 in front of Row State 47 and column c, d, $.
Because c, d looks ahead symbols in production C → d ∙ , c | d.
Filling of goto Entries
It can found out only for Non-Terminal.
For example, Consider
goto(I0, S) = I1
∴ goto [0, S] = 1

Filling of "𝐀𝐜𝐜𝐞𝐩𝐭" Entry

Since, S′ → S ∙ , $ is in I1
∴ Write accept in front of Row state 1 & column $.
LALR Parsing table can also be obtained by merging the rows of combined states of CLR
parsing, i.e., Merge Row corresponding to 3, 6, then 4, 7 and then 8, 9.
The resulting LALR Parsing table will be −

(OR)
b) Construct a predictive parsing table for the following grammar and parse the string.
Id+id*id
E-E+T|T
T-T*F|F
F->(E)|id.
(13)

Given grammar:
E -> E + T | T
T -> T * F | F
F -> ( E ) | id
Step 1: Rewrite the Grammar to Eliminate Left Recursion
To create a predictive parsing table, we need to eliminate left recursion in the
grammar.
1. Eliminate Left Recursion for `E`:
E -> TE'
E' -> +TE' | ε
2. Eliminate Left Recursion for `T:
T -> FT'
F` remains the same:
F -> ( E ) | id
Rewritten grammar:
E -> TE'
E' -> +TE' | ε
T -> FT'
T' -> *FT' | ε
F -> ( E ) | id
Step 2: Compute First and Follow Sets
1. First Sets:
First(E) = First(T) = First(F) = {id, (}
First(E') = {+, ε}
First(T') = {*, ε}
2. Follow Sets:
Follow(E) = Follow(E') = {$, )}
Follow(T)* = Follow(T') = {+, $, )}
Follow(F) = {*, +, $, )}
Step 3: Construct the Predictive Parsing Table

Non-Terminal id + * ( ) $

E E->TE’ E->TE’

E’->+TE
E
E’-> ᵋ E’-> ᵋ
T T->FT’ T->FT’

T’->*FT
T
T’-> ᵋ T’-> ᵋ T’-> ᵋ
F F->id F->(E)

Step 4: Parsing the String "id+id*id"

Input: `id + id * id`
| Stack | Input | Action
|-------------|--------------------|--------------
| $E | id+id*id$ | E → TE'
| $E'T | id+id*id$ | T → FT'
| $E'T'F | id+id*id$ | F → id
| $E'T'id | id+id*id$ | Match id
| $E'T' | +id*id$ | T' → ε
| $E' | +id*id$ | E' → +TE'
| $E'T+ | +id*id$ | Match +
| $E'T | id*id$ | T → FT'
| $E'T'F | id*id$ | F → id
| $E'T'id | id*id$ | Match id
| $E'T' | *id$ | T' → *FT'
| $E'T'F* | *id$ | Match *
| $E'T'F | id$ | F → id
| $E'T'id | id$ | Match id
| $E'T' |$ | T' → ε
| $E' |$ | E' → ε
|$ |$ | Accept

The string `id+id*id` is successfully parsed using the constructed predictive

parsing table.
Each step in the parsing process involves matching input tokens with the
production rules and managing the stack accordingly.

14. a) Demonstrate the following : (i) Syntax Tree. (ii) Quadruples. (iii) Triples. (iv)
Indirect Triples using the arithmetic expression.
A=b*-c+b*-c, by converting it into three address code (13)

First need to convert the expression into three-address code. Here are the steps:
Converting to Three-Address Code
First, break down the expression ( A = b * -c + b * -c ) into smaller, manageable parts.
1. `t1 = -c`
2. `t2 = b * t1`
3. `t3 = -c`
4. `t4 = b * t3`
5. `t5 = t2 + t4`
6. `A = t5`
(i) Syntax Tree
The syntax tree represents the hierarchical structure of the expression. Here is the syntax
tree for ( A = b * -c + b * -c ):
=
/\
A +
/\
* *
/\ /\
b -c b -c
(ii) Quadruples
Quadruples represent each operation in four fields: operator, argument1, argument2, and
result.
| Operator | Arg1 | Arg2 | Result
|-------------|--------|-------|--------|
|- |c | | t1
|* |b | t1 | t2
|- |c | | t3
|* |b | t3 | t4
|+ | t2 | t4 | t5
|= | t5 | |A
(iii) Triples
Triples use the index of the temporary results instead of variable names.
| Index | Operator | Arg1 | Arg2 |
|---------|------------|--------|--------|
|0 |- |c |
|1 |* |b | (0)
|2 |- |c |
|3 |* |b | (2)
|4 |+ | (1) | (3)
|5 |= | (4) | A
(iv) Indirect Triples
Indirect triples use pointers (or array indices) to reference the triples.
| Index | Triple Pointer |
|---------|------------------|
|0 | (0) |
|1 | (1) |
|2 | (2) |
|3 | (3) |
|4 | (4) |
|5 | (5) |
Triples table (referenced by the indices above):

| Index | Operator | Arg1 | Arg2

|---------|------------|--------|--------
|0 |- |c |
|1 |* |b | (0)
|2 |- |c |
|3 |* |b | (2)
|4 |+ | (1) | (3)
|5 |= | (4) | A
 Syntax Tree shows the hierarchical structure of the arithmetic expression.
 Quadruples provide a table with each operation broken down into four components.
 Triples simplify this by using indices for the temporary results.
 Indirect Triples further abstract this by using pointers to triples.
These representations help in the intermediate steps of code generation and
optimization during the compilation process.

(OR)
14. b) Illustrate in detail about the translation for flow of control statements and find the
three- address code for the following
While a<b does
If c<d then
x=y+z
else
x=y-z. (13)
Translation for Flow of Control Statements
Flow of control statements include constructs like loops (`while`, `for`) and conditionals
(`if`, `else`). The translation of these statements into three-address code involves creating labels for
different parts of the code and using conditional and unconditional jumps.
While Loop
A `while` loop is translated by placing the test condition at the beginning and using jumps
to repeat the loop or exit based on the condition.

If-Else Statement
An `if-else` statement is translated by evaluating the condition and then using jumps to
execute the appropriate block of code based on the result of the condition.
Given Pseudocode
while a < b do
if c < d then
x=y+z
else
x=y–z
Three-Address Code Generation
1. Start of the `while` loop:
 Test condition `a < b`.
 Jump to the end if the condition is false.
2. Inside the `while` loop:
 Test the `if` condition `c < d`.
 Jump to the `else` block if the condition is false.
 Execute the `then` block if the condition is true.
 Jump to the end of the `if-else` block.
3. End of the `if-else` block:
 Jump back to the beginning of the `while` loop to re-evaluate the condition.
4. End of the `while` loop:
 Mark the end of the loop execution.
Three-Address Code
1. `L1: if a >= b goto L2`
2. `L3: if c >= d goto L4`
3. `x = y + z`
4. `goto L5`
5. `L4: x = y - z`
6. `L5: goto L1`
7. `L2:`
Explanation of the Three-Address Code
1. L1: Label for the start of the `while` loop.
2. if a >= b goto L2: If `a` is not less than `b`, exit the loop by jumping to `L2`.
3. L3: Label for the `if` condition inside the loop.
4. if c >= d goto L4: If `c` is not less than `d`, jump to the `else` block at `L4`.
5. x = y + z: If `c` is less than `d`, execute `x = y + z`.
6. goto L5: After executing the `then` block, jump to `L5` to skip the `else` block.
7. L4: Label for the `else` block.
8. x = y - z: If `c` is not less than `d`, execute `x = y - z`.
9. L5: Label for the end of the `if-else` block.
10. goto L1: After completing the `if-else` block, re-evaluate the `while` loop condition.
11. L2: Label for the end of the `while` loop.

15. a) Discuss the various Storage allocation Strategies in detail.

(13)
A compiler is a program that converts HLL(High-Level Language) to
LLL(Low-Level Language) like machine language. In a compiler, there is a need for
storage allocation strategies in Compiler design because it is very important to use the
right strategy for storage allocation as it can directly affect the performance of the
software.

Storage Allocation Strategies

There are mainly three types of Storage Allocation Strategies:

1. Static Allocation
2. Heap Allocation
3. Stack Allocation

1. Static Allocation

Static allocation lays out or assigns the storage for all the data objects at the
compile time. In static allocation names are bound to storage. The address of these
identifiers will be the same throughout. The memory will be allocated in a static location
once it is created at compile time. C and C++ use static allocation.

For example:

int number = 1;
static int digit = 1;

Advantages of Static Allocation

i. It is easy to understand.
ii. The memory is allocated once only at compile time and remains the same
throughout the program completion.
iii. Memory allocation is done before the program starts taking memory only on
compile time.

Disadvantages of Static Allocation

i. Not highly scalable.

ii. Static storage allocation is not very efficient.
iii. The size of the data must be known at the compile time.

2. Heap Allocation

Heap allocation is used where the Stack allocation lacks if we want to retain the
values of the local variable after the activation record ends, which we cannot do in stack
allocation, here LIFO scheme does not work for the allocation and de-allocation of the
activation record. Heap is the most flexible storage allocation strategy we can
dynamically allocate and de-allocate local variables whenever the user wants according
to the user needs at run-time. The variables in heap allocation can be changed according
to the user’s requirement. C, C++, Python, and Java all of these support Heap Allocation.

For example:

Int*ans = new int[5];

Advantages of Heap Allocation

i. Heap allocation is useful when we have data whose size is not fixed and can
change during the run time.
ii. We can retain the values of variables even if the activation records end.
iii. Heap allocation is the most flexible allocation scheme.

Disadvantages of Heap Allocation

i. Heap allocation is slower as compared to stack allocation.

ii. There is a chance of memory leaks

3. Stack Allocation

Stack is commonly known as Dynamic allocation. Dynamic allocation means the

allocation of memory at run-time. Stack is a data structure that follows the LIFO
principle so whenever there is multiple activation record created it will be pushed or
popped in the stack as activations begin and ends. Local variables are bound to new
storage each time whenever the activation record begins because the storage is allocated
at runtime every time a procedure or function call is made. When the activation record
gets popped out, the local variable values get erased because the storage allocated for the
activation record is removed. C and C++ both have support for Stack allocation.

For example:

void sum(int a, int b) {in tans = a+b;cout<<ans;}

//when we call the sum function in the example above,
Memory will be allotted for the variable ans

Different storage allocation strategies play an important role in determining the

best-fit storage allocation strategy according to the need of the user as the helps in
determining how the memory is going to be allocated and deallocated. Different storage
allocation strategies have their own advantages and disadvantages and the choice
depends on the factors like speed, memory allocation, efficiency, etc. So we can choose
the allocation strategy according to the requirement.
(OR)
15. b) Explain in detail about the various issues in code generation with examples
(13)

Code generator converts the intermediate representation of source code into a

form that can be readily executed by the machine. A code generator is expected to
generate the correct code. Designing of the code generator should be done in such a way
that it can be easily implemented, tested, and maintained.
The following issue arises during the code generation phase:
Input to code generator

The input to the code generator is the intermediate code generated by the front end,
along with information in the symbol table that determines the run-time addresses of the
data objects denoted by the names in the intermediate representation. Intermediate codes
may be represented mostly in quadruples, triples, indirect triples, Postfix notation, syntax
trees, DAGs, etc. The code generation phase just proceeds on an assumption that the
input is free from all syntactic and state semantic errors, the necessary type checking has
taken place and the type-conversion operators have been inserted wherever necessary.
Target program

The target program is the output of the code generator. The output may be
absolute machine language, relocatable machine language, or assembly language.
 Absolute machine language as output has the advantages that it can be
placed in a fixed memory location and can be immediately executed. For
example, WATFIV is a compiler that produces the absolute machine code
as output.
 Relocatable machine language as an output allows subprograms and
subroutines to be compiled separately. Relocatable object modules can be
linked together and loaded by a linking loader. But there is added expense
of linking and loading.
 Assembly language as output makes the code generation easier. We can
generate symbolic instructions and use the macro-facilities of assemblers
in generating code. And we need an additional assembly step after code
generation.

Memory Management

Mapping the names in the source program to the addresses of data objects is done
by the front end and the code generator. A name in the three address statements refers to
the symbol table entry for the name. Then from the symbol table entry, a relative address
can be determined for the name.

Instruction selection

Selecting the best instructions will improve the efficiency of the program. It
includes the instructions that should be complete and uniform. Instruction speeds and
machine idioms also play a major role when efficiency is considered. But if we do not
care about the efficiency of the target program then instruction selection is
straightforward. For example, the respective three-address statements would be
translated into the latter code sequence as shown below:

P:=Q+R
S:+P+T

MOV Q, R0
ADD R, R0
MOV R0, P
MOV P, R0
ADD T, R0
MOV R0, S

Here the fourth statement is redundant as the value of the P is loaded again in that
statement that just has been stored in the previous statement. It leads to an inefficient
code sequence. A given intermediate representation can be translated into many code
sequences, with significant cost differences between the different implementations. Prior
knowledge of instruction cost is needed in order to design good sequences, but accurate
cost information is difficult to predict.
Register allocation issues

Use of registers make the computations faster in comparison to that of memory, so

efficient utilization of registers is important. The use of registers is subdivided into two
subproblems:
 During Register allocation – we select only those sets of variables that will
reside in the registers at each point in the program.
 During a subsequent Register assignment phase, the specific register is picked to
access the variable.

To understand the concept consider the following three address code sequence

t:=a+b
t:=t*c
t:=t/d

Their efficient machine code sequence is as follows:

MOV a.R0
ADD b.R0
MUL c.R0
DIV d.R0
MOV R0,t
Evaluation order

The code generator decides the order in which the instruction will be executed.
The order of computations affects the efficiency of the target code. Among many
computational orders, some will require only fewer registers to hold the intermediate
results. However, picking the best order in the general case is a difficult NP- complete
program.
Approaches to code generation issues:

Code generator must always generate the correct code. It is essential because of the
number of special cases that a code generator might face. Some of the design goals of
code generator are:
 Correct
 Easily maintainable
 Testable
 Efficient
Disadvantages in the design of a code generator:
Limited flexibility:

Code generators are typically designed to produce a specific type of code, and as a
result, they may not be flexible enough to handle a wide range of inputs or generate code
for different target platforms. This can limit the usefulness of the code generator in
certain situations.
Maintenance overhead:

Code generators can add a significant maintenance overhead to a project, as they

need to be maintained and updated alongside the code they generate. This can lead to
additional complexity and potential errors.
Debugging difficulties:

Debugging generated code can be more difficult than debugging hand-written

code, as the generated code may not always be easy to read or understand. This can make
it harder to identify and fix issues that arise during development.

Performance issues:
Depending on the complexity of the code being generated, a code generator may
not be able to generate optimal code that is as performant as hand-written code. This can
be a concern in applications where performance is critical.

Learning curve:

Code generators can have a steep learning curve, as they typically require a deep
understanding of the underlying code generation framework and the programming
languages being used. This can make it more difficult to on board new developers onto a
project that uses a code generator.

Over-reliance:

It’s important to ensure that the use of a code generator doesn’t lead to
over-reliance on generated code, to the point where developers are no longer able to write
code manually when necessary. This can limit the flexibility and creativity of a
development team, and may also result in lower quality code overall.

PART – C (1 x 15 = 15 Marks)
16. a) Explain in detail about optimization of Basic Blocks and construct the DAG for
the following Basic Block.
(i) t1: =4*I,
(ii) t2: =a[t1],
(iii) t3: =4*I,
(iv) t4: =b[t3],
(v) t5: =t2*t4,
(vi) t6: =prod+t5,
(vii) prod: =t6,
(viii) t7: =i+1,
(ix) i: =t7,
(x) if i<=20 goto (1). (15)

Optimization of Basic Blocks:

Optimization of basic blocks involves transforming a sequence of statements to
improve efficiency without changing the program's output. Common optimization
techniques include:
i. Constant Folding: Evaluate constant expressions at compile time.
ii. Common Sub-expression Elimination: Reuse results of expressions previously
computed.
iii. Dead Code Elimination: Remove code that does not affect the program.
iv. Strength Reduction: Replace expensive operations with cheaper ones.
v. Copy Propagation: Replace variables with their values when possible.
Directed Acyclic Graph (DAG):
A Directed Acyclic Graph (DAG) is a tool used in compiler optimization to
represent expressions in a basic block. Nodes represent values, and edges represent
dependencies between these values. DAGs help in identifying common subexpressions
and eliminating redundant computations.
Basic Block and DAG Construction:
The given basic block is:
(i) t1 := 4*I
(ii) t2 := a[t1]
(iii) t3 := 4*I
(iv) t4 := b[t3]
(v) t5 := t2*t4
(vi) t6 := prod + t5
(vii) prod := t6
(viii) t7 := I + 1
(ix) I := t7
(x) if I <= 20 goto (i)
Constructing the DAG
1. Node Creation:
 `4 * I`: Create a single node for `4 * I`, used in `t1` and `t3`.
 `a[t1]` and `b[t3]`: Create nodes for `a[]` and `b[]` indexed by `4 * I`.
 `t2 * t4`: Create a node for the product of `t2` and `t4`.
 `prod + t5`: Create a node for the sum of `prod` and `t5`.
 `I + 1`: Create a node for `I + 1`.
2. Edges Creation:
 `4 * I`: Used by `t1` and `t3`.
 `a[4 * I]` and `b[4 * I]`: Dependent on `4 * I`.
 `t2 * t4`: Dependent on `t2` and `t4`.
 `prod + t5`: Dependent on `prod` and `t5`.
 `I + 1`: Dependent on `I`.
DAG Representation
(I)
|
(4 * I)
/ \
a[4*I] b[4*I]
| |
t2 t4
\ /
(t2 * t4)
|
t5
|
(prod + t5)
|
t6
|
prod
|
(I + 1)
|
t7
Optimized Basic Block
Using the DAG, we can optimize the basic block by eliminating redundant
computations and reusing existing results.
 (i) t1 := 4*I
(ii) t2 := a[t1]
(iii) t4 := b[t1] ; Reuse t1 instead of recomputing 4*I
(iv) t5 := t2 * t4
(v) t6 := prod + t5
(vi) prod := t6
(vii) t7 := I + 1
(viii) I := t7
(ix) if I <= 20 goto (i)
1. Common Subexpression Elimination: `4 * I` is computed once and stored in `t1`. This
value is reused for indexing both `a` and `b`.
2. Reuse of Indices: Instead of computing `4 * I` twice, `t1` is used for both array accesses.
3. Final Optimized Code: The redundant computation of `4 * I` is removed, leading to
more efficient code.
 DAG Construction: Helps in visualizing dependencies and identifying optimization
opportunities.
 Optimization Techniques: Common subexpression elimination is applied here.
 Optimized Basic Block: Leads to improved code efficiency by reusing
computations and minimizing redundant operations.

(OR)
16. b) Develop an efficient data flow graph and algorithm with example. (15)
Data Flow Graph (DFG)
A Data Flow Graph (DFG) is a graphical representation of the data dependencies
between operations in a program. In a DFG, nodes represent operations or computations,
and edges represent the flow of data between these operations. DFGs are used for
optimizing and parallelizing code, especially in the context of compiler design and digital
signal processing.
Developing an Efficient Data Flow Graph
Consider the following sequence of operations:
1. t1 = a + b
2. t2 = t1 * c
3. t3 = a + b
4. t4 = t3 - d
5. t5 = t2 + t4
Steps to Create an Efficient DFG
1. Identify Operations and Data Dependencies: Determine the operations and their
dependencies.
2. Eliminate Redundant Computations: Use common subexpression elimination to avoid
duplicate computations.
3. Construct Nodes and Edges: Create nodes for each operation and edges to represent data
dependencies.
4. Optimize Node Placement: Arrange nodes to highlight parallelism and data reuse.

Data Flow Graph Construction

Step 1: Identify Operations and Dependencies
1. t1 = a + b
2. t2 = t1 * c (depends on t1
3. t3 = a + b
4. t4 = t3 - d (depends on t3
5. t5 = t2 + t4 depends on t2 and t4
Step 2: Eliminate Redundant Computations
t1 and t3 are the same:
 t1 = a + b. We can reuse t1.
Optimized Sequence
1. t1 = a + b
2. t2 = t1 * c
3. t4 = t1 - d
4. t5 = t2 + t4
Step 3: Construct Nodes and Edges
 Nodes: \( t1 \), \( t2 \), \( t4 \), \( t5 \)
 Edges: Data dependencies between these nodes
Step 4: Optimize Node Placement
(a) (b) (c) (d)
\ / | |
\ / | |
(t1) (t2) |
|\ | /
| \ | /
| \ | /
| (t4) | /
\ | | /
\ | | /
\ | |/
\ | |/
(t5)

Example Data Flow Graph

a b
\ /
\/
t1 (t1 = a + b)
|\
| \
| \
| \
t2 t4
| / (t4 = t1 - d)
| /
\/
t5 (t5 = t2 + t4)
Data Flow Graph Algorithm
1. Initialization: Start with an empty set of nodes and edges.
2. Node Creation: For each operation, create a node.
3. Edge Creation: For each data dependency, create an edge between nodes.
4. Optimization:
 Common Subexpression Elimination: Detect and reuse common subexpressions.
 Dead Code Elimination: Remove nodes that do not contribute to the final result.
5. Final Graph Construction: Connect the nodes with directed edges based on data
dependencies.
Algorithm Implementation
```python
class Node:
def __init__(self, operation, dependencies=[]):
[Link] = operation
[Link] = dependencies
def create_dfg(operations):
nodes = {}
for op in operations:
if op not in nodes:
nodes[op] = Node(op)
for dep in nodes[op].dependencies:
if dep not in nodes:
nodes[dep] = Node(dep)
return nodes
def optimize_dfg(nodes):
# Common Subexpression Elimination
seen = {}
for node in [Link]():
if [Link] not in seen:
seen[[Link]] = node
else:
node = seen[[Link]]
# Dead Code Elimination
used = set()
for node in [Link]():
[Link]([Link])
nodes = {op: node for op, node in [Link]() if [Link] in used}
return nodes
Example operations
operations = [
"t1 = a + b",
"t2 = t1 * c",
"t3 = a + b",
"t4 = t3 - d",
"t5 = t2 + t4"
]
nodes = create_dfg(operations)
optimized_nodes = optimize_dfg(nodes)
Display the optimized data flow graph
for node in optimized_nodes.values():
print(f"Operation: {[Link]}, Dependencies: {[Link]}")