AAT-II

Compiler Design
ACSC40

NAME : N. Mahesh
ROLL NO :21951A0592

Computer Science and Engineering

INSTITUTE OF AERONAUTICAL ENGINEERING

(Autonomous)
Dundigal, Hyderabad–500043, Telangana
March, 2024
1.For the following expression total =count+rate*5
construct the output after each phase of compiler?
Ans: Compiler operates in various phases each phase transforms
the source program from one representation to another. Every
phase takes inputs from its previous stage and feeds its output to
the next phase of the compiler.
There are 6 phases in a compiler. Each of this phase help in
converting the high-level langue the machine code. The phases of a
compiler are:

1. Lexical analysis
2. Syntax analysis
3. Semantic analysis
4. Intermediate code generator
5. Code optimizer
6. Code generator
Lexical Analysis is the first phase when compiler scans the source
code. This process can be left to right, character by character, and
group these characters into tokens.
Here, the character stream from the source program is grouped in
meaningful sequences by identifying the tokens. It makes the entry
of the corresponding tickets into the symbol table and passes that
token to next phase.
The primary functions of this phase are:
● Identify the lexical units in a source code
● Classify lexical units into classes like constants, reserved
words, and enter them in different tables. It will Ignore
comments in the source program
● Identify token which is not a part of the language

2.Construct the DAG for the following basic

block.D:=B*C E:=A+B B:=B+C A:=E-D

Ans : Construct the DAG for the basic block

d = b * c
e = a + b
b = b * c
a = e - d

Answer

8.5.2
Simplify the three-address code of Exercise 8.5.1, assuming

1. Only a is live on exit from the block.

2. a, b, and c are live on exit from the block.

Answer

1. Only a is live on exit from the block.

e = a + b
d = b * c
2. a = e - d
3. a, b, and c are live on exit from the block.
e = a + b
b = b * c
4. a = e - b

8.5.3
Construct the basic block for the code in block B6 of Fig. 8.9. Do not forget to include
the comparison i <= 10.
Answer

疑问

● “Construct the basic block” 被翻译成 “构造 DAG”，是这个意思吗？

● 如何为一个 “if goto” 语句 construct the basic block？

8.5.4
Construct the DAG for the code in block B3 of Fig. 8.9.

Answer
8.5.5
Extend Algorithm 8.7 to process three-statements of the form

1. a[i] = b
2. a = b[i]
3. a = *b
4. *a = b

8.5.6
Construct the DAG for the basic block
a[i] = b
*p = c
d = a[j]
e = *p
*p = a[i]

on the assumption that

1. p can point anywhere.

2. p can point only to b or d.

疑问

8.5.6 节讲指针赋值这里又没有 demo 啊！！！

 ● *p = c 和 c = *p 翻译成 DAG 是不是这样的：
● *p = a[i] 这样的语句用 DAG 如何表示？
● 8.5.6 节讲到：the operator =* must take all nodes that are currently associated
with identifiers as arguments。这句话再 DAG 中如何表示？

8.5.7 !
If a pointer or array expression, such as a[i] or *p is assigned and then used, without
the possibility of being changed in the interim, we can take advantage of the situation
to simplify the DAG. For example, in the code of Exercise 8.5.6, since p is not
assigned between the second and fourth statements,the statement e = *p can be
replaced by e = c, regardless of what p points to. Revise the DAG-construction
algorithm to take advantage of such situations, and apply your algorithm to the code
of Example 8.5.6.

8.5.8
Suppose a basic block is formed from the C assignment statements
x = a + b + c + d + e + f;
y = a + c + e;

1. Give the three-address statements (only one addition per statement) for this
block.
2. Use the associative and commutative laws to modify the block to use the
fewest possible number of instructions, assuming both x and y are live on exit
from the block.

Answer

1. three-address statements
t1 = a + b
t2 = t1 + c
t3 = t2 + d
t4 = t3 + e
t5 = t4 + f
x = t5
t6 = a + c
t7 = c + e
2. y = t6 + t7
3. optimized statments
t1 = a + c
t2 = t1 + e
y = t2
t3 = t2 + b
t4 = t3 + d
t5 = t4 + f
4. x = t5

3.Explain handle pruning in detail with example?

Ans: In compiler design, handle pruning is the technique used to
optimise the parsing process of a grammar. In order to replace
nonterminal symbols to handle, parsing algorithms apply reduction.
In LR parsing handle is a substring of the right side of the
production rule. Thus, it can be reduced to nonterminal on the left-
side of the rule.
Below are the types of handle pruning in compiler design.
1. Lookahead handle pruning: As the name suggests, it looks ahead to
the next token. In order to determine if the handle is relevant this
technique involves looking ahead to the next token. The parser is
required to access a lookahead buffer to predict the next token based on
the parser’s current state.

2. Nullbility handle pruning: It determines if a null value/symbol can

replace a handle. It is also responsible for determining if a symbol can be
derived from a nullable symbol.

3. Left-to-Right Parsing: It is a bottom-up parsing technique. In order to

reduce handles till the last symbol, the parser reads the input from left to
right. The handle is the substring of input symbols which could be
reduced on the left side in a production rule.

4. Left-to-Left Parsing: It is a top-down parsing technique. To reduce the

handle, it expands the handle recursively. The handle is the substring of
input symbols which could be reduced on the top-down in a production
rule.

5. Shift-Reduce parsing: It is also a bottom-up technique. A stack of

symbols is maintained until a handle is identified. It is quite similar to LR
parsing, but shift-parsing makes the decision based on the current stack.
On the other hand, LR parsing uses finite automation for decisions.

Features of handle pruning in compiler design

Some of the features of handle pruning in compiler design are:
1. Improved parsing speed: The parser can work efficiently if the parse
stack is small.

2. Reduced parse stack size: The size and memory of the stack can be
reduced if handle pruning removes irrelevant handles.

3. Increased parsing efficiency: In order to increase the efficiency of the

parsing process, handle pruning reduced the number of possible parse
trees. It allows the parser to focus on eliminating the irrelevant nodes.

4. Improved error recovery: To recover from errors, handle pruning

reduces the number of parse trees. It makes it easier for the parser to
handle errors and continue parsing the input.

Also check out - Phases of Compiler and Cross Compiler

Advantages of Handle Pruning in Compiler Design

Advantages of handle pruning in compiler design:
1. Performance: With the help of handle pruning, we can improve the
performance of parsing. It reduces the number of irrelevant handles and
parse trees, which helps in the reduction of memory and time needed for
parsing.

2. Better error recovery: With the help of handle pruning, we can recover
from errors more efficiently. The pruning process reduces leads to faster
and more accurate parsing results by reducing the number of possible
parse trees.

3. Compatible with various parsing techniques: Handle pruning is

compatible with parsing techniques like LL, LR, and LALR parsers.

4.Define translation scheme and write for ac?

Ans: 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.

5.Explain the specification of a simple type checker .

Ans: A type checker for a simple language checks the type
of each identifier. The type checker is a translation scheme
that synthesizes the type of each expression from the types
of its subexpressions. The type checker can handle arrays,
pointers, statements and functions. A Simple Language
Consider the following grammar: P → D ; E D → D ; D |
id : T T → char | integer | array [ num ] of T | ↑ T E →
literal | num | id | E mod E | E [ E ] | E ↑ Translation
scheme: P → D ; E D → D ; D D → id:T
{ addtype(id.entry ,T.type) } T→char { T.type: = char}
T→integer { T.type: = integer} T →↑T1 { T.type: =
pointer(T1.type)} T → array [ num ] of T1 { T.type : =
array ( 1… num.val , T1.type) } In the above language, →
There are two basic types : char and integer ; →
type_error is used to signal errors; → the prefix operator ↑
builds a pointer type. Example , ↑ integer leads to the type
expression pointer ( integer ). Type checking of expressions
In the following rules, the attribute type for E gives the
type expression assigned to the expression generated by E.
1. E → literal { E.type: = char } E→num { E.type: = integer}
Here, constants represented by the tokens literal and num
have type char and integer. 2. E→id { E.type: = lookup
( id.entry)} lookup ( e ) is used to fetch the type saved in
the symbol table entry pointed to by e. 3. E → E1modE2
{ E.type: = if E1. type = integerand E2. type = integer
then ROHINI COLLEGE OF ENGINEERING AND
TECHNOLOGY CS8602 COMPILER DESIGN integer else
type_error}
Theexpressionformedbyapplyingthemodoperatortotwosubex
pressionsoftypeintegerhast ype integer; otherwise, its type
istype_error.

6.Explain briefly about source language issues?

Ans:A control stack is used to keep track of live procedure activations.
The idea is to push the node for an activation onto the control stack as
the activation begins and to pop the node when the activation ends.
The contents of the control stack are related to paths to the root of the
activation tree. When node n is at the top of control stack, the stack
contains the nodes along the path from n to the root.

The Scope of a Declaration:

A declaration is a syntactic construct that associates information with

a n Declarations may be explicit, such as:
var i : integer ;
or they may be implicit. Example, any variable name starting with I is
assumed to denote an integer. The portion of the program to which a
declaration applies is called the scope of that declaration.

Binding of names:
Even if each name is declared once in a program, the same name may
denote different data objects at run time. “Data object” corresponds to
a storage location that holds values. The term environment refers to a
function that maps a name to a storage location. The term state refers
to a function that maps a storage location to the value held there.
When an environment associates storage location s with a name x, we
say that x is bound to s. This association is referred to as a binding of x.

7.Explain role of DAG representation in optimization

with example?
Ans:A DAG for basic block is a directed acyclic graph with the
following labels on nodes:

1. The leaves of graph are labeled by unique identifier and

that identifier can be variable names or constants.

2. Interior nodes of the graph is labeled by an operator

symbol.
 3. Nodes are also given a sequence of identifiers for labels to

store the computed value.

4. DAGs are a type of data structure. It is used to

implement transformations on basic blocks.

5. DAG provides a good way to determine the common sub-

expression.

6. It gives a picture representation of how the value

computed by the statement is used in subsequent

statements.

8.Explain the primary structure preserving

transformations on basic blocks?

Ans: Optimization is applied to the basic blocks after the

intermediate code generation phase of the compiler. Optimization is
the process of transforming a program that improves the code by
consuming fewer resources and delivering high speed. In
optimization, high-level codes are replaced by their equivalent
efficient low-level codes. Optimization of basic blocks can be
machine-dependent or machine-independent. These
transformations are useful for improving the quality of code that
will be ultimately generated from basic There are two types of basic
block optimizations:
1. Structure preserving transformations

2. Algebraic transformations

Structure-Preserving Transformations:

The structure-preserving transformation on basic blocks includes:

1. Dead Code Elimination

2. Common Subexpression Elimination

3. Renaming of Temporary variables

4. Interchange of two independent adjacent statements

1.Dead Code Elimination:

Dead code is defined as that part of the code that never executes
during the program execution. So, for optimization, such code or
dead code is eliminated. The code which is never executed during
the program (Dead code) takes time so, for optimization and speed,
it is eliminated from the code. Eliminating the dead code increases
the speed of the program as the compiler does not have to
translate the dead code.

9.Explain Local optimization in detail with example?

Ans: The back-propagation strategy is a steepest gradient method,

a local optimization technique. Therefore, it also suffers from the
major drawback of these methods, namely that it can become
locked in a local optimum. Many variants have been developed to
overcome this drawback . None of these does however really solve
the problem.
A way to obtain an idea on the robustness of the obtained solution is
to retrain the network with a different weight initialization. The
results of the different training sessions can be used to define a
range around the performance curve. This procedure can also be
used to compare different networks.

The code optimization in the synthesis phase is a program

transformation technique, which tries to improve the intermediate
code by making it consume fewer resources (i.e. CPU, Memory) so
that faster-running machine code will result. Compiler optimizing
process should meet the following objectives :

● The optimization must be correct, it must not, in any way,

change the meaning of the program.

● Optimization should increase the speed and performance of

 the program.

● The compilation time must be kept reasonable.

● The optimization process should not delay the overall

compiling process.

When to Optimize?

Optimization of the code is often performed at the end of the

development stage since it reduces readability and adds code that is
used to increase the performance.

Why Optimize?

Optimizing an algorithm is beyond the scope of the code

optimization phase. So the program is optimized. And it may
involve reducing the size of the code. So optimization helps to:

● Reduce the space consumed and increases the speed of

compilation.

● Manually analyzing datasets involves a lot of time. Hence

we make use of software like Tableau for data analysis.

Similarly manually performing the optimization is also

tedious and is better done using a code optimizer.

● An optimized code often promotes re-usability.

Types of Code Optimization: The optimization process can be
broadly classified into two types :

1. Machine Independent Optimization: This code optimization

phase attempts to improve the intermediate code to get a

better target code as the output. The part of the

intermediate code which is transformed here does not

involve any CPU registers or absolute memory locations.

2. Machine Dependent Optimization: Machine-dependent

optimization is done after the target code has been

generated and when the code is transformed according to

the target machine architecture. It involves CPU registers

and may have absolute memory references rather than

relative references. Machine-dependent optimizers put

efforts to take maximum advantage of the memory

hierarchy.

10. Explain about the DAG ? Mention its remember ?

Ans: A graph is formed by vertices and by edges connecting pairs of
vertices, where the vertices can be any kind of object that is connected in
pairs by edges. In the case of a directed graph, each edge has an
orientation, from one vertex to another vertex. A path in a directed graph is
a sequence of edges having the property that the ending vertex of each
edge in the sequence is the same as the starting vertex of the next edge in
the sequence; a path forms a cycle if the starting vertex of its first edge
equals the ending vertex of its last edge. A directed acyclic graph is a
directed graph that has no cycles.

A vertex v of a directed graph is said to be reachable from another vertex u

when there exists a path that starts at u and ends at v. As a special case,
every vertex is considered to be reachable from itself (by a path with zero
edges). If a vertex can reach itself via a nontrivial path (a path with one or
more edges), then that path is a cycle, so another way to define directed
acyclic graphs is that they are the graphs in which no vertex can reach
itself via a nontrivial path.

The transitive closure of a DAG is the graph with the most edges that has
the same reachability relation as the DAG. It has an edge u → v for every

pair of vertices (u, v) in the reachability relation ≤ of the DAG, and may

therefore be thought of as a direct translation of the reachability relation ≤

into graph-theoretic terms. The same method of translating partial orders
into DAGs works more generally: for every finite partially ordered set (S, ≤),
the graph that has a vertex for every element of S and an edge for every
pair of elements in ≤ is automatically a transitively closed DAG, and has (S,

≤) as its reachability relation. In this way, every finite partially ordered set
can be represented as a DAG.