1.

Code Optimization Techniques

Code optimization is the process of making code more e cient by improving its
execution time, memory usage, and overall resource consumption. Below are
common optimization techniques:
a) Loop Unrolling:
Involves expanding loops to reduce the overhead of control instructions.

ffi
2. Compilation Process of position = initial + rate * 60
The expression position = initial + rate * 60 undergoes the following compiler
phases:
a) Lexical Analysis:
Breaks the statement into tokens like:
• position (identi er)
• = (operator)
• initial (identi er)
• + (operator)
• rate (identi er)
• * (operator)
• 60 (constant)
fi
fi
fi
3. Write a note on:
a) YACC (Yet Another Compiler Compiler):
YACC is a tool used to generate parsers. It reads a formal grammar of a
programming language and produces source code that implements a parser for
that language. It is commonly used in compiler construction to handle syntax
analysis by transforming grammar rules into a parsing function that can interpret
source code according to those rules. YACC generates a parse table and shift-
reduce parsing function, which are essential for recognizing language constructs.
b) Lex (Lexical Analyzer Generator):
 Lex is used to generate lexical analyzers or scanners. It converts input source
code into a series of tokens, where each token represents a meaningful piece of
the program such as identi ers, keywords, operators, and symbols. Lex takes a
set of regular expressions de ning these tokens and generates the scanning
function automatically.
Together with YACC, Lex and YACC provide the building blocks for building a full-
edged compiler or interpreter.
PHASES OF COMPILER:
1. Lexical Analysis (Scanning)
The rst phase of compilation is Lexical Analysis or scanning. During this phase,
the source code is broken down into a sequence of tokens, which represent the
smallest units of meaning, like keywords, operators, identi ers, or literals. The
lexical analyzer scans the program's characters, eliminates whitespace and
comments, and groups them into meaningful components.

2. Syntax Analysis (Parsing)

Syntax Analysis or parsing ensures that the sequence of tokens follows the
syntax or grammatical rules of the programming language. The parser generates a
parse tree or abstract syntax tree (AST) that represents the hierarchical structure
of the program according to the language's grammar. This phase helps detect
syntax errors in the source code.
Example: Input:
int x = 5;
The AST would look like:
Assignment
/ | \
DataType Identi er Literal
| | |
int x 5
3. Semantic Analysis
During Semantic Analysis, the compiler checks for semantic errors, ensuring that
the program is meaningful in the context of the language. This phase involves type
checking, ensuring variables are declared before use, and verifying that function
calls and expressions are valid.
int x = "Hello"; // Semantic error: incompatible types
4. Intermediate Code Generation
fl
fi
fi
fi
fi
fi
 In this phase, the compiler generates an intermediate representation (IR) of the
program. This intermediate code is simpler than the original source code and is
designed to be easy to manipulate or optimize, independent of the target machine.
The intermediate code might resemble assembly language, making it easier to
optimize for performance before code generation.
Example: For the statement x = a + b;, the intermediate code might look l
t1 = a + b;
x = t1;

5. Code Optimization
Code Optimization takes place after intermediate code generation and is aimed at
improving the e ciency of the intermediate code, reducing computational
overhead, memory use, and execution time. Some common optimizations include:
1. Dead Code Elimination: Any part of the code that doesn't a ect the output
(such as unreachable code) is eliminated.
2. Constant Folding: Expressions involving constant values (like 2 + 3) are
evaluated at compile time rather than during runtime.
The intermediate code undergoes several modi cations to achieve high-level
performance improvements while maintaining the logic intact. These optimizations
reduce runtime and make the program more e cient, bene ting resources such as
processor speed, memory, and disk storage.
6. Code Generation
The Code Generation phase is responsible for transforming the intermediate code
into machine-speci c code that a processor can understand directly. During this
phase, the intermediate representations, such as three-address code or
Intermediate Representation (IR), are converted into assembly or machine code.
Code Generation is highly architecture-dependent. Di erent processors may use
di erent instruction sets, optimizations, and formats for representing
computations. The output from this phase is typically assembly code or a low-level
intermediate representation ready to be translated to machine code by an
assembler or directly executed if it's in the form of executable machine code.
7. Code Linking
In the Linking phase, multiple code les and libraries are connected, making it
possible to combine object code from di erent modules or sources into a single
executable. Code linking is often split into two sub-phases: static linking and
dynamic linking.
Static Linking happens at compile time. It involves combining object code with
libraries and generating an executable le ready for use.
Dynamic Linking happens at runtime. Instead of combining the libraries at the
time of compilation, the program loads them during execution. This allows for
smaller executable sizes and more e cient memory usage across multiple
programs sharing common libraries.
By the end of this phase, the compiler ensures that all function calls, variables, and
external references are resolved. Once the linker nishes its work, the nal
executable code can be generated.
5. Discuss the optimization of loops with examples.
ff
ffi
fi
fi
ffi
fi
ff
ffi
fi
fi
ff
fi
ff
fi
 Loop optimization techniques aim to reduce the overhead caused by loops and
improve their performance. Since loops are often among the most computationally
intensive parts of a program, optimizing them can yield substantial bene ts. Below
are common loop optimization strategies:
1. Loop Unrolling
Loop unrolling is a technique that reduces the overhead of loop control by
performing multiple operations per loop iteration. This can increase performance
by minimizing the number of jumps in the code and making better use of the CPU
pipeline.
Consider the following loop:

Bene t: The new operation uses cheaper CPU cycles and thus reduces the time
required to perform each iteration of the loop.
2. Loop Fusion
Loop fusion combines two or more loops that iterate over the same range or on
the same data. Combining them into a single loop minimizes the overhead of loop
control and can enhance cache locality.
fi
fi
 Bene t: Loop fusion reduces the number of iterations, which reduces the
overhead associated with loop counters and enhances cache e ciency, as fewer
iterations result in fewer data accesses. 3. Loop
Inversion (Loop Distribution)
Loop inversion involves splitting or distributing loops based on certain conditions
to separate computations. By splitting di erent operations into separate loops, it
might be possible to enable better optimization of each individual loop.
Example:
fi
ff
ffi
6. Test whether the given grammar is LL(1) or not and
construct a predictive parsing table for it.
An LL(1) grammar is a context-free grammar that can be parsed from Left to
right, with Leftmost derivation, and uses 1 lookahead symbol to decide which
production to apply. To test whether a given grammar is LL(1) and create a
predictive parsing table, we need to perform several steps:
Testing for LL(1) Condition:
1. First sets: These represent the set of terminals that can appear at the
beginning of any string derived from a non-terminal.
2. Follow sets: These represent the set of terminals that can appear
immediately after a non-terminal in a derivation.
The grammar is LL(1) if, for each non-terminal and each pair of productions, the
First sets of the productions do not overlap and the Follow sets do not interfere
with any non-terminal that derives an empty string.
 7. Global Data Flow Analysis Used in Basic Blocks
Data ow analysis is a crucial method in compiler optimization, enabling a
detailed examination of the ow of variables and other entities within a program.
When this analysis is applied to basic blocks (sequences of instructions with no
branches except at the entry/exit points), it helps identify opportunities for
optimizations such as dead code elimination, constant propagation, and more.
Key Data Flow Concepts:
• Basic Blocks: A basic block is a sequence of consecutive statements with
only one entry point and one exit point.
Example:

• Data Flow Information: This refers to how variables are de ned (assigned)
and used throughout a program.
• IN (incoming ow): Variables that are available when the block starts.
• OUT (outgoing ow): Variables that are available when the block ends.
• GEN (generated): Variables calculated or generated inside a block.
• KILL (killed): Variables whose previous values are overwritten in the current
block.
fl
fl
fl
fl
fi
 Data Flow Equations:
1. IN[B] = Union of OUT[P] for each predecessor P of B.
2. OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])
This ow of data allows a compiler to nd variables that are unused or redundant,
thus enabling dead code eliminationor constant propagation optimizations.

8. Various Types of Compiler Optimizations

Optimization techniques in compilers aim to improve the e ciency of the resulting
code, targeting various computational areas such as execution time, memory
usage, and CPU cycles. Below are some common types of compiler optimizations:
1. Loop Optimization
• Loop Unrolling: This optimization reduces the overhead caused by loop
control (like increment and comparison operations). By performing multiple
operations within each iteration, the compiler cuts down on loop control
overhead.
Example:
fl
fi
ffi
• Constant Propagation: Variables whose values are known at compile time
are propagated to other expressions, reducing runtime calculations.
3. Dead Code Elimination
Dead code refers to computations or instructions that do not a ect the program’s
output and are therefore unnecessary. Identifying and removing dead code
reduces program size and improves performance.

4. Inline Expansion
In cases where a function is small and used frequently, it may be bene cial to
replace function calls with the function’s body (inline expansion). This reduces
function call overhead.
Example:
ff
fi
9. SLR(1) Parsing
SLR(1) Parsing (Simple LR Parsing) is a bottom-up parsing technique used to
parse context-free grammars. An SLR(1)parser uses a single lookahead symbol
and builds an LR parsing table that tells the parser how to decide which rule to
apply.
Consider the grammar:

Step 2: Construct the SLR(1) Parsing Table

The SLR(1) parsing table consists of Action and Goto tables.

Explanation:
• State 0: If the input is id, we shift and move to state 1. If we have $, the
parser should accept.
• State 1: If the lookahead is +, we shift to state 2; otherwise, if $ is found,
the input is accepted.
• State 2: The parser can reduce T to id based on the previous derivations.
By following the parsing table, the parser reads the input token by token (with one
token lookahead) and decides whether to shift, reduce, or accept based on the
states and actions provided in the table.