UNIT - I

Introduction: The structure of a compiler, the science of building a compiler, programming

language basics.
Lexical Analysis: The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens,
Design of a Lexical-Analyzer Generator using Lex, Finite Automata, From Regular
Expressions to Automata, , Optimization of DFA-Based Pattern Matchers.

1.1 INTRODUCTION
A compiler is a translator that converts the high-level language into the machine language.
High-level language is written by a developer and machine language can be understood by
the processor. The compiler also makes the end code efficient which is optimized for
execution time and memory space. The main purpose of compiler is to change the code
written in one language without changing the meaning of the program and also used to show
errors to the programmer.

When you execute a program which is written in HLL programming language then it
executes into two parts. In the first part, the source program compiled and translated into the
object program (low level language).

In the second part, object program translated into the target program through the Interpreter.

Features of Compilers
• Correctness

Page 1 of 26
 • Speed of compilation
• Preserve the correct the meaning of the code
• The speed of the target code
• Recognize legal and illegal program constructs
• Good error reporting/handling
• Code debugging help

Types of Compiler
Following are the different types of Compiler:
• Single Pass Compilers
• Two Pass Compilers
• Multipass Compilers

Single Pass Compiler

In single pass Compiler source code directly transforms into machine code. For example,
Pascal language.

Two Pass Compiler

Two pass Compiler is divided into two sections, viz.
1. Front end: It maps legal code into Intermediate Representation (IR).
2. Back end: It maps IR onto the target machine

The Two pass compiler method also simplifies the retargeting process. It also allows multiple
front ends.

Page 2 of 26
Multipass Compilers
The multipass compiler processes the source code it divided a large program into multiple
small programs and process them. It develops multiple intermediate codes. All of these
multipass take the output of the previous phase as an input. So it requires less memory.

Tasks of Compiler
Main tasks performed by the Compiler are:
• Breaks up the up the source program into pieces and impose grammatical structure on
them
• Allows to construct the desired target program from the intermediate representation
and also create the symbol table.
• Compiles source code and detects errors in it
• Manage storage of all variables and codes.
• Support for separate compilation
• Read, analyze the entire program, and translate to semantically equivalent
• Translating the source code into object code depending upon the type of machine

History of Compiler
Important Landmark of Compiler's history are as follows:
• The "compiler" word was first used in the early 1950s by Grace Murray Hopper
• The first compiler was build by John Backum and his group between 1954 and 1957
at IBM
• COBOL was the first programming Languages which was compiled on multiple
platforms in 1960
• The study of the scanning and parsing issues were pursued in the 1960s and 1970s to
provide a complete solution.

Page 3 of 26
Steps for Language processing systems
Before knowing about the concept of compilers, we first need to understand a few other tools
which work with compilers.

• Preprocessor: The preprocessor a tool which produces input for Compiler. It deals
with macro processing, language extension, etc.
• Interpreter: An interpreter is like Compiler which translates object program into target
program. The main difference between both is that interpreter reads and transforms
code line by line. Compiler reads the entire code at once and creates the machine
code.
• Assembler: It translates assembly language code into machine understandable
language. The output result of assembler is a combination of machine instructions as
well as the data required to store these instructions in memory.
• Linker: The linker helps to link and merge various object files to create an executable
file. All these files might have been compiled separately. The main task of a linker is
to search for called modules in a program and to find out the memory location where
all modules are stored.

Page 4 of 26
 • Loader: The loader is a part of the OS, which performs the tasks of loading executable
files into memory and run them. It also calculates the size of a program which creates
additional memory space.
Compiler Construction Tools
Compiler construction tools were introduced as computer-related technologies spread all over
the world. They are also known as a compiler- compilers, compiler- generators or translator.
These tools use specific language or algorithm for specifying and implementing the
component of the compiler. Following are the example of compiler construction tools.
• Scanner generators: This tool takes regular expressions as input. For example LEX for
Unix Operating System.
• Syntax-directed translation engines: These software tools offer an intermediate code
by using the parse tree. It has a goal of associating one or more translations with each
node of the parse tree.
• Parser generators: A parser generator takes a grammar as input and automatically
generates source code which can parse streams of characters with the help of a
grammar.
• Automatic code generators: Takes intermediate code and converts them into Machine
Language
• Data-flow engines: This tool is helpful for code optimization. Here, information is
supplied by user and intermediate code is compared to analyze any relation. It is also
known as data-flow analysis. It helps you to find out how values are transmitted from
one part of the program to another part.

Uses of Compiler
• Compiler verifies entire program, so there are no syntax or semantic errors
• The executable file is optimized by the compiler, so it is executes faster
• There is no need to execute the program on the same machine it was built
• Translate entire program in other language
• Link the files into an executable format
• Check for syntax errors and data types
• Helps to handle language performance issues
• The techniques used for constructing a compiler can be useful for other purposes
as well

Page 5 of 26
Applications of Compiler
• Compiler design helps full implementation of High-Level Programming Languages
• Support optimization for Computer Architecture Parallelism
• Design of New Memory Hierarchies of Machines
• Widely used for Translating Programs
• Used with other Software Productivity Tools

1.2 STRUCTURE OF A COMPILER

Any large software is easier to understand and implement if it is divided into well-defined
modules. The design of compiler can be decomposed into several phases, each of which
converts one form of source program into another.
The different phases of compiler are as follows:
1. Lexical analysis
2. Syntax analysis
3. Semantic analysis
4. Intermediate code generation
5. Code optimization
6. Code generation
All of the aforementioned phases involve the following tasks:
• Symbol table management.
• Error handling.

Page 6 of 26
 Figure: The structure of a compiler.
Lexical Analysis
• Lexical analysis is the first phase of compiler which is also termed as scanning.
• Source program is scanned to read the stream of characters and those characters are
grouped to form a sequence called lexemes which produces token as output.
• Token: Token is a sequence of characters that represent lexical unit, which matches
with the pattern, such as keywords, operators, identifiers etc.
• Lexeme: Lexeme is instance of a token i.e., group of characters forming a token. ,
• Pattern: Pattern describes the rule that the lexemes of a token takes. It is the structure
that must be matched by strings.

Example: c=a+b*5;

Lexemes Tokens
C identifier
= assignment symbol
A identifier
+ + (addition symbol)

Page 7 of 26
 B identifier
* * (multiplication symbol)
5 5 (number)
; Semicolon

Syntax Analysis
• Syntax analysis is the second phase of compiler which is also called as parsing.
• Parser converts the tokens produced by lexical analyzer into a tree like representation
called parse tree.
• Syntax tree is a compressed representation of the parse tree in which the operators appear
as interior nodes and the operands of the operator are the children of the node for that
operator.

Semantic Analysis
• Semantic analysis is the third phase of compiler.
• It checks for the semantic consistency.
• Type information is gathered and stored in symbol table or in syntax tree.
• Performs type checking.

Page 8 of 26
Intermediate Code Generation

• Intermediate code generation produces intermediate representations for the source

program which are of the following forms:
➢ Postfix notation
➢ Three address code
➢ Syntax tree

Most commonly used form is the three address code.

t1 = inttofloat (5)

t2 = id3* tl

t3 = id2 + t2

id1 = t3
Code Optimization
• Code optimization phase gets the intermediate code as input and produces optimized
intermediate code as output.
• It results in faster running machine code.
• It can be done by reducing the number of lines of code for a program.
• This phase reduces the redundant code and attempts to improve the intermediate code so
that faster-running machine code will result.

Page 9 of 26
• During the code optimization, the result of the program is not affected.
• To improve the code generation, the optimization involves
➢ Deduction and removal of dead code (unreachable code).
➢ Calculation of constants in expressions and terms.
➢ Collapsing of repeated expression into temporary string.
➢ Loop unrolling.
➢ Moving code outside the loop.
➢ Removal of unwanted temporary variables.
t1 = id3* 5.0
id1 = id2 + t1
Code Generation
• Code generation is the final phase of a compiler.
• It gets input from code optimization phase and produces the target code or object code as
result.
• Intermediate instructions are translated into a sequence of machine instructions that
perform the same task.
• The code generation involves
➢ Generation of correct references.
➢ Generation of correct data types.
➢ Generation of missing code.
LDF R2, id3
MULF R2, # 5.0
LDF R1, id2
ADDF R1, R2
STF id1, R1

Symbol Table Management

• Symbol table is used to store all the information about identifiers used in the program.
• It is a data structure containing a record for each identifier, with fields for the attributes of
the identifier.
• It allows finding the record for each identifier quickly and to store or retrieve data from
that record.
• Whenever an identifier is detected in any of the phases, it is stored in the symbol table.

Page 10 of 26
Example
char a,b,c; const:5
Symbol name Type Address
A char 1000
b char 1002
C char 1004
5 const 1008

Error Handling
• Each phase can encounter errors. After detecting an error, a phase must handle the error
so that compilation can proceed.
• In lexical analysis, errors occur in separation of tokens.
• In syntax analysis, errors occur during construction of syntax tree.
• In semantic analysis, errors may occur at the following cases:
➢ When the compiler detects constructs that have right syntactic structure but no
meaning
➢ During type conversion.
• In code optimization, errors occur when the result is affected by the optimization. In code
generation, it shows error when code is missing etc.

Page 11 of 26
1.3 THE SCIENCE OF BUILDING A COMPILER

Page 12 of 26
A compiler must accept all source programs that conform to the specification of the language;
the set of source programs is infinite and any program can be very large, consisting of
possibly millions of lines of code. Any transformation performed by the compiler while
translating a source program must preserve the meaning of the program being compiled.
Compiler writers thus have influence over not just the compilers they create, but all the
programs that their compilers compile. This leverage makes writing compilers particularly
rewarding; however, it also makes compiler development challenging.

Modeling in compiler design and implementation

The study of compilers is mainly a study of how we design the right mathematical models
and choose the right algorithms, while balancing the need for generality and power against
simplicity and efficiency.

The science of code optimization

The term "optimization" in compiler design refers to the attempts that a compiler makes to
produce code that is more efficient than the obvious code. "Optimization" is thus a misnomer,
since there is no way that the code produced by a compiler can be guaranteed to be as fast or
faster than any other code that performs the same task.

Finally, a compiler is a complex system; we must keep the system simple to assure that the
engineering and maintenance costs of the compiler are manageable. There is an infinite
number of program optimizations that we could implement, and it takes a nontrivial amount
of effort to create a correct and effective optimization. We must prioritize the optimizations,
implementing only those that lead to the greatest benefits on source programs encountered in
practice.

1.4 PROGRAMMING LANGUAGE BASICS

To design an efficient compiler, we should know some language basics.

Page 13 of 26
 Figure: Programming Language Basics
Static and Dynamic Distinction

• Static - Events occur at compile time.

• Dynamic - Events occur at run time.
Example

• The scope of a declaration of x is the region of the program in which uses of x refer to
this declaration.
• A language uses static scope or lexical scope if it is possible to determine the scope of
a declaration by looking only at the program.
• Otherwise, the language uses dynamic scope. With dynamic scope, as the program
runs, the same use of x could refer to any of several different declarations of x.
Environment and States

• The environment is mapping from names to locations in the store.

Since variables refer to locations, we could alternatively define an environment as a
mapping from names to variables.
• The state is a mapping from locations in store to their values.

Figure: Environment and States

Static Scope and Block Structure

• The scope rules for C are based on program structure. The scope of a declaration is
determined implicitly by where the declaration appears in the program.

Page 14 of 26
 • Programming languages such as C++, Java, and C#, also provide explicit control over
scopes through the use of keywords like public, private, and protected.
• A block is a grouping of declarations and statements. C uses braces { and } to delimit
a block, the alternative use of begin and end in some languages.

Explicit Access Control

• Classes and Structures introduce a new scope for their members.

• If p is an object of a class with a field (member) x, then the use of x in p.x refers to
field x in the class definition.
• Through the use of keywords like public, private, and protected, object oriented
languages such as C++ or Java provide explicit control over access to member names
in a super class. These keywords support encapsulation by restricting access.
o Public - Public names are accessible from outside the class
o Private - Private names include method declarations and definitions associated
with that class and any "friend" classes.
o Protected - Protected names are accessible to subclasses.

Dynamic Scope

• The term dynamic scope, however, usually refers to the following policy: a use of a
name x refers to the declaration of x in the most recently called procedure with such a
declaration.
• Dynamic scoping of this type appears only in special situations. The two dynamic
policies are:
o Macro expansion in the C
o Method resolution in OOPs

Parameter Passing Mechanisms

• Every language has some method for passing parameters to functions and procedures.
• Formal Parameters: The identifier used in a method to stand for the value that is
passed into the method by a caller.
• Actual Parameters: The actual value that is passed into the method by a caller.
o Call by Value - The actual parameter is evaluated (if it is an expression) or
copied (if it is a variable) in a formal parameter.

Page 15 of 26
 o Call by Reference - The address of the actual parameter is passed as value of
the corresponding formal parameter.
o Call by Name - The Called object execute as if the actual parameter were
substituted literally for the formal parameter.
Aliasing

• When two names refer to the same location in memory.

• There is an interesting consequence of call-by-reference parameter passing or its
simulation, as in Java, where references to objects are passed by value.
• It is possible that two formal parameters can refer to the same location; such variables
are said to be aliases of one another.
• As a result, any two variables, which may appear to take their values from two
distinct formal parameters, can become aliases of each other.
1.4 THE ROLE OF THE LEXICAL ANALYZER
As the first phase of a compiler, the main task of the lexical analyzer is to read the input
characters of the source program, group them into lexemes, and produce as output tokens for
each lexeme in the source program. This stream of tokens is sent to the parser for syntax
analysis. It is common for the lexical analyzer to interact with the symbol table as well. When
the lexical analyzer discovers a lexeme constituting an identifier, it needs to enter that lexeme
into the symbol table. This process is shown in the following figure.

Figure : Lexical Analyzer

When lexical analyzer identifies the first token it will send it to the parser, the parser receives
the token and calls the lexical analyzer to send next token by issuing the getNextToken()

Page 16 of 26
command. This Process continues until the lexical analyzer identifies all the tokens. During
this process the lexical analyzer will neglect or discard the white spaces and comment lines.

TOKENS, PATTERNS AND LEXEMES:

A token is a pair consisting of a token name and an optional attribute value. The token name
is an abstract symbol representing a kind of lexical unit, e.g., a particular keyword, or a
sequence of input characters denoting an identifier. The token names are the input symbols
that the parser processes. In what follows, we shall generally write the name of a token in
boldface. We will often refer to a token by its token name.

A pattern is a description of the form that the lexemes of a token may take [ or match]. In the
case of a keyword as a token, the pattern is just the sequence of characters that form the
keyword. For identifiers and some other tokens, the pattern is a more complex structure that
is matched by many strings.

A lexeme is a sequence of characters in the source program that matches the pattern for a
token and is identified by the lexical analyzer as an instance of that token. Example: In the
following C language statement ,
printf ("Total = %d\n‖, score) ;

both printf and score are lexemes matching the pattern for token id, and "Total = %d\n‖ is a
lexeme matching literal [or string].

Figure: Examples of Tokens

Page 17 of 26
1.5 INPUT BUFFERING
The lexical analyzer scans the input from left to right one character at a time. It uses two
pointers begin ptr(bp) and forward to keep track of the pointer of the input scanned.

Initially both the pointers point to the first character of the input string as shown below

The forward ptr moves ahead to search for end of lexeme. As soon as the blank space is
encountered, it indicates end of lexeme. In above example as soon as ptr (fp) encounters a
blank space the lexeme “int” is identified.

Page 18 of 26
The fp will be moved ahead at white space, when fp encounters white space, it ignore and
moves ahead. then both the begin ptr(bp) and forward ptr(fp) are set at next token.

The input character is thus read from secondary storage, but reading in this way from
secondary storage is costly. hence buffering technique is used. A block of data is first read
into a buffer, and then second by lexical analyzer. there are two methods used in this context:
One Buffer Scheme, and Two Buffer Scheme. These are explained as following below.

1. One Buffer Scheme:

In this scheme, only one buffer is used to store the input string but the problem with this
scheme is that if lexeme is very long then it crosses the buffer boundary, to scan rest of the
lexeme the buffer has to be refilled, that makes overwriting the first of lexeme.

2. Two Buffer Scheme:

To overcome the problem of one buffer scheme, in this method two buffers are used to store
the input string. the first buffer and second buffer are scanned alternately. when end of
current buffer is reached the other buffer is filled. the only problem with this method is that if
length of the lexeme is longer than length of the buffer then scanning input cannot be scanned
completely.

Page 19 of 26
Initially both the bp and fp are pointing to the first character of first buffer. Then the fp
moves towards right in search of end of lexeme. as soon as blank character is recognized, the
string between bp and fp is identified as corresponding token. to identify, the boundary of
first buffer end of buffer character should be placed at the end first buffer.

Similarly end of second buffer is also recognized by the end of buffer mark present at the end
of second buffer. when fp encounters first eof, then one can recognize end of first buffer and
hence filling up second buffer is started. in the same way when second eof is obtained then it
indicates of second buffer.

Alternatively both the buffers can be filled up until end of the input program and stream of
tokens is identified. This eof character introduced at the end is calling Sentinel which is used
to identify the end of buffer.

1.6 THE LEXICAL-ANALYZER GENERATOR USING - LEX

• Lex is a program that generates lexical analyzer. It is used with YACC parser
generator.
• The lexical analyzer is a program that transforms an input stream into a sequence of
tokens.
• It reads the input stream and produces the source code as output through
implementing the lexical analyzer in the C program.
The function of Lex is as follows:

Page 20 of 26
 • Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex
compiler runs the lex.1 program and produces a C program [Link].c.
• Finally C compiler runs the [Link].c program and produces an object program [Link].
• [Link] is lexical analyzer that transforms an input stream into a sequence of tokens.

Lex file format

A Lex program is separated into three sections by %% delimiters. The formal of Lex source
is as follows:
{ definitions }
%%
{ rules }
%%
{ user subroutines }

• Definitions include declarations of constant, variable and regular definitions.

• Rules define the statement of form p1 {action1} p2 {action2}....pn {action}.
• Where pi describes the regular expression and action1 describes the actions what action
the lexical analyzer should take when pattern pi matches a lexeme.
• User subroutines are auxiliary procedures needed by the actions. The subroutine can be
loaded with the lexical analyzer and compiled separately.

1.7 FINITE AUTOMATA

Finite automata is a state machine that takes a string of symbols as input and changes its state
accordingly. Finite automata is a recognizer for regular expressions. When a regular
expression string is fed into finite automata, it changes its state for each literal. If the input

Page 21 of 26
string is successfully processed and the automata reaches its final state, it is accepted, i.e., the
string just fed was said to be a valid token of the language in hand.

The mathematical model of finite automata consists of:

• Finite set of states (Q)
• Finite set of input symbols (Σ)
• One Start state (q0)
• Set of final states (qf)
• Transition function (δ)
The transition function (δ) maps the finite set of state (Q) to a finite set of input symbols (Σ),
Q×Σ➔Q
Finite Automata Construction
Let L(r) be a regular language recognized by some finite automata (FA).
• States : States of FA are represented by circles. State names are written inside circles.
• Start state : The state from where the automata starts, is known as the start state. Start
state has an arrow pointed towards it.
• Intermediate states : All intermediate states have at least two arrows; one pointing to
and another pointing out from them.
• Final state : If the input string is successfully parsed, the automata is expected to be in
this state. Final state is represented by double circles. It may have any odd number of
arrows pointing to it and even number of arrows pointing out from it. The number of
odd arrows are one greater than even, i.e. odd = even+1.
• Transition : The transition from one state to another state happens when a desired
symbol in the input is found. Upon transition, automata can either move to the next
state or stay in the same state. Movement from one state to another is shown as a
directed arrow, where the arrows points to the destination state. If automata stays on
the same state, an arrow pointing from a state to itself is drawn.
Example : We assume FA accepts any three digit binary value ending in digit 1. FA =
{Q(q0, qf), Σ(0,1), q0, qf, δ}

Page 22 of 26
1.8 REGULAR EXPRESSIONS
Regular expression
• Regular expression is a sequence of pattern that defines a string. It is used to denote
regular languages.
• It is also used to match character combinations in strings. String searching algorithm
used this pattern to find the operations on string.
• In regular expression, x* means zero or more occurrence of x. It can generate {e, x,
xx, xxx, xxxx,.....}
• In regular expression, x+ means one or more occurrence of x. It can generate {x, xx,
xxx, xxxx,.....}
Operations on Regular Language
The various operations on regular language are:

1. Union: If L and M are two regular languages then their union L U M is also a union.
L U M = {s | s is in L or s is in M}

2. Intersection: If L and M are two regular languages then their intersection is also an
intersection.
L ⋂ M = {st | s is in L and t is in M}

3. Kleene closure: If L is a regular language then its kleene closure L1* will also be a
regular language.
L* = Zero or more occurrence of language L.

Example
Write the regular expression for the language:
L = {abn w:n ≥ 3, w ∈ (a,b)+}

Page 23 of 26
Solution:
The string of language L starts with "a" followed by atleast three b's. Itcontains atleast one
"a" or one "b" that is string are like abbba, abbbbbba, abbbbbbbb, abbbb.....a
So regular expression is:

r= ab3b* (a+b)+
Here + is a positive closure i.e. (a+b)+ = (a+b)* - ∈

1.9 OPTIMIZATION OF DFA

To optimize the DFA you have to follow the various steps. These are as follows:
Step 1: Remove all the states that are unreachable from the initial state via any set of the
transition of DFA.
Step 2: Draw the transition table for all pair of states.
Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states
and T2 contains non-final states.
Step 4: Find the similar rows from T1 such that:
Step 5: Repeat step 3 until there is no similar rows are available in the transition table T1.
Step 6: Repeat step 3 and step 4 for table T2 also.
Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the
transition table of minimized DFA.
Example

Solution:
Step 1: In the given DFA, q2 and q4 are the unreachable states so remove them.
Step 2: Draw the transition table for rest of the states.

Page 24 of 26
Step 3:
Now divide rows of transition table into two sets as:
1. One set contains those rows, which start from non-final sates:

2. Other set contains those rows, which starts from final states.

Step 4: Set 1 has no similar rows so set 1 will be the same.

Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to same state on 0 and 1.
So skip q5 and then replace q5 by q3 in the rest.

Step 6: Now combine set 1 and set 2 as:

Now it is the transition table of minimized DFA.

Transition diagram of minimized DFA:

Page 25 of 26
Fig: Minimized DFA

Page 26 of 26
 UNIT - II

Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar, Top-Down

Parsing, Bottom-Up Parsing, Introduction to LR Parsing: Simple LR, More Powerful LR
Parsers, Using Ambiguous Grammars and Parser Generators.

2.1 INTRODUCTION
Syntax Analysis is a second phase of the compiler design process in which the given input
string is checked for the confirmation of rules and structure of the formal grammar. It
analyses the syntactical structure and checks if the given input is in the correct syntax of the
programming language or not.
Syntax Analysis in Compiler Design process comes after the Lexical analysis phase. It is also
known as the Parse Tree or Syntax Tree. The Parse Tree is developed with the help of pre-
defined grammar of the language. The syntax analyser also checks whether a given program
fulfills the rules implied by a context-free grammar. If it satisfies, the parser then creates the
parse tree of that source program. Otherwise, it will display error messages.

Figure: Syntax Analyser Process

2.2 CONTEXT-FREE GRAMMARS

Context-free grammars can generate Context-Free-Langauges. They do this by taking a set of
variables which are defined recursively, in terms of one another, by a set of production rules.
Context-free grammars are named as such because any of the production rules in the

Page 1 of 37
grammar can be applied regardless of context—it does not depend on any other symbols that
may or may not be around a given symbol that is having a rule applied to it.

Context-free grammars have the following components:

• A set of terminal symbols which are the characters that appear in the language/strings
generated by the grammar. Terminal symbols never appear on the left-hand side of the
production rule and are always on the right-hand side.
• A set of nonterminal symbols (or variables) which are placeholders for patterns of
terminal symbols that can be generated by the nonterminal symbols. These are the
symbols that will always appear on the left-hand side of the production rules, though
they can be included on the right-hand side. The strings that a CFG produces will
contain only symbols from the set of nonterminal symbols.
• A set of production rules which are the rules for replacing nonterminal symbols.
Production rules have the following form: variable \rightarrow→ string of variables
and terminals.
• A start symbol which is a special nonterminal symbol that appears in the initial string
generated by the grammar.

A context-free grammar can be described by a four-element Tuples Σ = (V, T, P, S) Where,

• V is a finite set of variables (which are non-terminal)
• T is a finite set of Terminal
• P is a set of production rules where each production rule maps a variable to a strings
• S is a start symbol.

Example:
L= {wcwR | w € (a, b)*}
Production rules:
1. S → aSa
2. S → bSb
3. S → c
Now check that abbcbba string can be derived from the given CFG.
S ⇒ aSa
S ⇒ abSba

Page 2 of 37
 S ⇒ abbSbba
S ⇒ abbcbba
By applying the production S → aSa, S → bSb recursively and finally applying the
production
S → c, we get the string abbcbba.

Derivation
A derivation is basically a sequence of production rules, in order to get the input string.
During parsing, we take two decisions for some sentential form of input:
• Deciding the non-terminal which is to be replaced.
• Deciding the production rule, by which, the non-terminal will be replaced.
To decide which non-terminal to be replaced with production rule, we can have two options.

Left-most Derivation
If the sentential form of an input is scanned and replaced from left to right, it is called left-
most derivation. The sentential form derived by the left-most derivation is called the left-
sentential form.

Right-most Derivation
If we scan and replace the input with production rules, from right to left, it is known as right-
most derivation. The sentential form derived from the right-most derivation is called the
right-sentential form.

Example
Production rules:
E→E+E
E→E-E
E → id
Input string: id + id * id

The left-most derivation is:

E→E-E
E→E+E-E

Page 3 of 37
E → id + E - E
E → id + id - E
E → id + id - id
Notice that the left-most side non-terminal is always processed first.

The right-most derivation is:

E→E+E
E→E+E-E
E → E + E - id
E → E + id - id
E → id + id - id

Parse Tree
A parse tree is a graphical depiction of a derivation. It is convenient to see how strings are
derived from the start symbol. The start symbol of the derivation becomes the root of the
parse tree. For the string id + id – id, to construct two parse trees: Left-Most -Derivation and
Right- Most -Derivation

Figure: Left-Most -Derivation and Right- Most -Derivation

2.3 TOP-DOWN PARSING TECHNIQUIES

There are two types of parsing by which the top-down parsing can be performed.
1. Backtracking
2. Predictive parsing

Page 4 of 37
 Fig: Types of Top-Down Parsing Techniques

Backtracking

Backtracking is a technique in which for expansion for non-terminal symbol we choose one
alternative and if some mismatch occurs then we try another alternative if any.

Example
Consider the grammar G : S → cAd
A→ab|a and the input string w=cad.

The parse tree can be constructed using the following top-down approach :

Step1:
Initially create a tree with single node labeled S. An input pointer points to ‘c’, the first
symbol of w. Expand the tree with the production of S.

Step2:

Page 5 of 37
The leftmost leaf ‘c’ matches the first symbol of w, so advance the input pointer to the second
symbol of w ‘a’ and consider the next leaf ‘A’. Expand A using the first alternative.

Step3:
The second symbol ‘a’ of w also matches with second leaf of tree. So advance the input
pointer to third symbol of w ‘d’.But the third leaf of tree is b which does not match with the
input symbol [Link] discard the chosen production and reset the pointer to
second backtracking.

Step4: Now try the second alternative for A.

Now we can halt and announce the successful completion of parsing.

A backtracking parser will try different production rules to find the match for the input string
by backtracking each time. The backtracking is powerful than predictive parsing. But this
technique is slower and its requires exponential time in general. Hence backtracking is not
preferred for practical compilers.

Predictive parser
As the same name suggests the predictive parser tries to predict the next construction using
one or more lookahead symbols from input string. There are two types of predictive parsers.
Page 6 of 37
 1. Recursive Descent parser
2. LL(1) parser

1.4 PROBLEMS IN TOP-DOWN PARSING

There are certain problems in top-down parsing. In order to implement the parsing we need to
eliminate these problems. The problems are:

1. Ambiguity
2. Back Tracking
3. Left Recursion
4. Left Factoring

Ambiguity

A grammar is said to be ambiguous if there exists more than one leftmost derivation or more
than one rightmost derivative or more than one parse tree for the given input string. If the
grammar is not ambiguous then it is called unambiguous.
Example:
S = aSb | SS
S=∈

For the string aabb, the above grammar generates two parse trees:

Page 7 of 37
If the grammar has ambiguity then it is not good for a compiler construction. No method can
automatically detect and remove the ambiguity but you can remove ambiguity by re-writing
the whole grammar without ambiguity.

Backtracking

Backtracking is a technique in which for expansion for non-terminal symbol we choose one
alternative and if some mismatch occurs then we try another alternative if any.

Example

Consider the grammar G : S → cAd

A→ab|a and the input string w=cad.
The parse tree can be constructed using the following top-down approach :

Step1:
Initially create a tree with single node labeled S. An input pointer points to ‘c’, the first
symbol of w. Expand the tree with the production of S.

Step2:
The leftmost leaf ‘c’ matches the first symbol of w, so advance the input pointer to the second
symbol of w ‘a’ and consider the next leaf ‘A’. Expand A using the first alternative.

Page 8 of 37
Step3:

The second symbol ‘a’ of w also matches with second leaf of tree. So advance the input
pointer to third symbol of w ‘d’.But the third leaf of tree is b which does not match with the
input symbol [Link] discard the chosen production and reset the pointer to
second backtracking.

Step4: Now try the second alternative for A.

Now we can halt and announce the successful completion of parsing.

Left Recursion

There is a formal technique for eliminating left-recursion from productions

Step One: Direct-Recursion

For each rule which contains a left-recursive option,

Page 9 of 37
A --> A |
introduce a new nonterminal A' and rewrite the rule as

A --> A'
A' --> | A'
Thus the production:
E --> E + T | T
is left-recursive with "E" playing the role of "A","+ T" playing the role of , and "T" playing

the role of A'. Introducing the new nonterminal E', the production can be replaced by:
E --> T E'
E' --> | + T E'
Of course, there may be more than one left-recursive part on the right-hand side. The general
rule is to replace:

A --> A | | ... | | | ... |

by

A --> A' | A'| ...| A'

A' --> | A' | A' | ...| A'
Note that this may change the "structure". For the expression above, the original grammar is
left-associative, while the non-left recursive one is now right-associative.

Step Two: Indirect-Recursion

Step one describes a rule to eliminate direct left recursion from a production. To eliminate
left-recursion from an entire grammar may be more difficult because of indirect left-
recursion. For example,
A --> B x y | x
B --> C D
C --> A | c
D --> d
is indirectly recursive because
A ==> B x y ==> C D x y ==> A D x y.
That is, A ==> ... ==> A where is D x y.

Page 10 of 37
To eliminates left-recursion entirely. It contains a "call" to a procedure which eliminates
direct left-recursion (as described in step one).

Left Factoring
Left Factoring is a grammar transformation technique. It consists in "factoring out" prefixes
which are common to two or more productions.
Left factoring is removing the common left factor that appears in two productions of the same
non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-
ahead ,consider this example-
A -> qB | qC

where A,B,C are non-terminals and q is a sentence. In this case, the parser will be confused
as to which of the two productions to choose and it might have to back-trace. After left
factoring, the grammar is converted to-

A -> qD
D -> B | C

In this case, a parser with a look-ahead will always choose the right production.
Left recursion is a case when the left-most non-terminal in a production of a non-terminal is
the non-terminal itself( direct left recursion ) or through some other non-terminal definitions,
rewrites to the non-terminal again(indirect left recursion). Consider these examples -

(1) A -> Aq (direct)

(2) A -> Bq B -> Ar (indirect)

Left recursion has to be removed if the parser performs top-down parsing

2.5 RECURSIVE DESCENT PARSER

A recursive-descent parsing program consists of a set of recursive procedures, one for each
non terminal. Each procedure is responsible for parsing the constructs defined by its non
terminal, Execution begins with the procedure for the start symbol, which halts and
announces success if its procedure body scans the entire input string.

Page 11 of 37
If the given grammar is
E -> TE′
E′-> +TE′ | €
T -> FT′
T′-> *FT′ | €
F -> (E) | id
Reccursive procedures for the recursive descent parser for the given grammar are given
below

procedure E( )
{
if(Lookahead==' $ ')
declare as Success ;
else error;
T( );
E′( );
}
procedure T ( )
{
F( );
T′( );
}
Procedure E′( )
{
if (Lookahead= = '+')
{
match('+');
T ( );
E′( );

}
else if (Lookahead==NULL)
{

Page 12 of 37
 match('NULL') ;
}
else error;
}

procedure T′( )
{
if (Lookahead == '*')
{
match('+');
F ( );
T′( );
}
else if(Lookahead == 'NULL')
{
match(NULL);
}
else error;
}

procedure F( )
{
if (Lookahead== '(' )
{
match( '(' );
E( );
}
if else(Lookahead==' )' )
{
match(' )' );
}
if else(Lookahead==' id ')
{

Page 13 of 37
 match('id');
}
else error;
}

Procedure match( token t)

{
token t = next token;
t= token;
}

Procedure Error ( )
{
printf(" Error!");
}

Procedure NULL( )
{
Printf(" Empty!");
}

2.6 PREDICTIVE LL(1) PARSER

It is possible to build a non- recursive predictive parser by maintaining a stack
explicitly, rather than implicitly via recursive calls. The key problem during predictive
parsing is that of determining the production to be applied for a nonterminal. The
nonrecursive parser in figure looks up the production to be applied in parsing table. In what
follows, we shall see how the table can be constructed directly from certain grammars.

Page 14 of 37
 Fig. Predictive LL(1) parser

A table-driven predictive parser has an input buffer, a stack, a parsing table, and an output
stream. The input buffer contains the string to be parsed, followed by $, a symbol used as a
right end marker to indicate the end of the input string. The stack contains a sequence of
grammar symbols with $ on the bottom, indicating the bottom of the stack. Initially, the stack
contains the start symbol of the grammar on top of $. The parsing table is a two dimensional
array M[A,a] where A is a nonterminal, and a is a terminal or the symbol $. The parser is
controlled by a program that behaves as follows. The program considers X, the symbol on the
top of the stack, and a, the current input symbol. These two symbols determine the action of
the parser. There are three possibilities.
1. If X= a=$, the parser halts and announces successful completion of parsing.
2. If X=a!=$, the parser pops X off the stack and advances the input pointer to the next
input symbol.
3. If X is a nonterminal, the program consults entry M[X,a] of the parsing table M. This
entry will be either an X-production of the grammar or an error entry. If, for example,
M[X,a]={X- >UVW}, the parser replaces X on top of the stack by WVU( with U on
top). As output, we shall assume that the parser just prints the production used; any
other code could be executed here. If M[X,a]=error, the parser calls an error recovery
routine.
Algorithm for predictive LL(1) Parsing.
Input: A string w and a parsing table M for grammar G.
Output: If w is in L(G), a leftmost derivation of w; otherwise, an error indication.

Page 15 of 37
Method: Initially, the parser is in a configuration in which it has $S on the stack with S,
the start symbol of G on top, and w$ in the input buffer. The program that utilizes the
predictive parsing table M to produce a parse for the input is shown in Fig.

Set ip to point to the first symbol of w$. repeat

Let X be the top stack symbol and a the symbol pointed to by ip. if X is a terminal of $
then
if X=a then
pop X from the stack and advance ip else error()
else

if M[X,a]=X->Y1Y2...Yk then begin pop X from the stack;

push Yk,Yk-1...Y1 onto the stack, with Y1 on top; output the production X->
Y1Y2...Yk
end

else error()

until X=$ /* stack is empty */

Predictive LL(1) parsing table construction:

The construction of a predictive parser is aided by two functions associated with a
grammar G :
1. FIRST()
2. FOLLOW()
Rules for FIRST( ):
1. If X is terminal, then FIRST(X) is {X}.
2. If X → ε is a production, then add ε to FIRST(X).
3. If X is non-terminal and X → aα is a production then add a to FIRST(X).
4. If X is non-terminal and X → Y1 Y2…Yk is a production, then place a in
FIRST(X) if for some i, a is in FIRST(Yi), and ε is in all of
FIRST(Y1),…,FIRST(Yi-1);that is, Y1,….Yi-1=> ε. If ε is in FIRST(Yj) for all
j=1,2,..,k, then add ε to FIRST(X).

Page 16 of 37
Rules for FOLLOW( ):
1. If S is a start symbol, then FOLLOW(S) contains $.
2. If there is a production A → αBβ, then everything in FIRST(β) except ε is placed
in follow(B).
3. If there is a production A → αB, or a production A → αBβ where FIRST(β)
contains ε, then everything in FOLLOW(A) is in FOLLOW(B).
Algorithm for construction of predictive LL(1) parsing table:
Input : Grammar G
Output : Parsing table M
Method :
1. For each production A → α of the grammar, do steps 2 and 3.
2. For each terminal a in FIRST(α), add A → α to M[A, a].
3. If ε is in FIRST(α), add A → α to M[A, b] for each terminal b in FOLLOW(A). If ε is
in FIRST(α) and $ is in FOLLOW(A) , add A → α to M[A, $].
4. Make each undefined entry of M be error.

Implementation of predictive parser:

1. Elimination of left recursion, left factoring and ambiguous grammar.
2. Construct FIRST() and FOLLOW() for all non-terminals.
3. Construct predictive parsing table.
4. Parse the given input string using stack and parsing table

Example:
Consider the following grammar:
E→E+T|T
T→T*F|F
F→(E)|id

Solution

After eliminating left-recursion the grammar is

E →TE’
E’ → +TE’ | ε

Page 17 of 37
 T →FT’
T’ → *FT’ | ε
F → (E)|id

First( ) :
FIRST(E) = { ( , id}
FIRST(E’) ={+ , ε }
FIRST(T) = { ( , id}
FIRST(T’) = {*, ε }
FIRST(F) = { ( , id }
Follow( ):
FOLLOW(E) = { $, ) }
FOLLOW(E’) = { $, ) }
FOLLOW(T) = { +, $, ) }
FOLLOW(T’) = { +, $, ) }
FOLLOW(F) = {+, * , $ , ) }
Predictive parsing Table

Stack Implementation

Page 18 of 37
1.4 BOTTOM UP PARSING
Bottom-up parsing starts from the leaf nodes of a tree and works in upward direction till it
reaches the root node. Here, we start from a sentence and then apply production rules in
reverse manner in order to reach the start symbol. The image given below depicts the
bottom-up parsers available.

Page 19 of 37
 Fig: Types of Bottom up Parser

2.7 SHIFT REDUCING PARSER

Shift-reduce parsing uses two unique steps for bottom-up parsing. These steps are known as
shift-step and reduce-step.

• Shift step: The shift step refers to the advancement of the input pointer to the next
input symbol, which is called the shifted symbol. This symbol is pushed onto the
stack. The shifted symbol is treated as a single node of the parse tree.

• Reduce step : When the parser finds a complete grammar rule (RHS) and replaces it
to (LHS), it is known as reduce-step. This occurs when the top of the stack contains a
handle. To reduce, a POP function is performed on the stack which pops off the
handle and replaces it with LHS non-terminal symbol.

Shift Reducing Parser to construct parse free from leaves to root. It works on the same
principle of bottom up parser. A shift reduce parser requires following steps:

1. Input buffer storing the input-string

2. A Stack for storing and accessing the LHS and RHS of rules.

Initial configuration of Shift Reduce Parser

The parser performs following basic operations

Shift: Moving of Symbols from input buffer out to the stack, this action is called shift.

Page 20 of 37
Reduce: If the handle appears on the top of the stack there reduction of if by
appropriate rule is done that means RHS of rule is popped of and LHS is pushed in.

Accept: If the stack contain start symbol only and input buffer is empty at the same time then
that action is called accept.

Example: Consider the grammar

E →E-E
E →E*E
E→ id
Perform shift-reduce parsing of the input string id-id * id

Stack Input buffer Action

$ id-id * id Shift
$ id -id * id Reduced by E → id
$E id * id Shift
$E – id * id Shift
$E – id * id Reduced by E → id
$E – E * id $ Shift
$E – E*id id$ Shift
$E – E*id $ Reduced by E → id
$E – E*E $ Reduced by E → E * E
$E – E $ Reduced by E → E – E
$E $ Accept

2.8 OPERATOR PRECEDENCE PARSING

Operator precedence grammar is kinds of shift reduce parsing method. It is applied to a small
class of operator grammars.

A grammar is said to be operator precedence grammar if it has two properties:

o No R.H.S. of any production has a∈.

Page 21 of 37
 o No two non-terminals are adjacent.

Operator precedence can only established between the terminals of the grammar. It ignores
the non-terminal.

There are the three operator precedence relations:

a ⋗ b means that terminal "a" has the higher precedence than terminal "b".

a ⋖ b means that terminal "a" has the lower precedence than terminal "b".

a ≐ b means that the terminal "a" and "b" both have same precedence.

Precedence table:

2.9 LR PARSERS

LR parsing is one type of bottom up parsing. It is used to parse the large class of grammars.

In the LR parsing, "L" stands for left-to-right scanning of the input.

"R" stands for constructing a right most derivation in reverse.
"K" is the number of input symbols of the look ahead used to make number of parsing
decision.

Page 22 of 37
 Figure: Structure of LR Parser

LR parsing is divided into four parts:

Input
Contains the string to be parsed and pointer
Parsing Table
Contains two parts ACTION and GOTO which is used by the parser program
1. ACTION Part
The ACTION part of the table is a two dimensional array indexed by state and the input
symbol, i.e. ACTION[state][input], An action table entry can have one of following four
kinds of values in it. They are:
1. Shift X, where X is a State number.
2. Reduce X, where X is a Production number.
3. Accept, signifying the completion of a successful parse.

2. GO TO Part
The GO TO part of the table is a two dimensional array indexed by state and a Non terminal,
i.e. GOTO[state][NonTerminal]. A GO TO entry has a state number in the table.

Augment Grammar

Page 23 of 37
The Augment Grammar G`, is G with a new starting symbol S` an additional production
S` ->S. this helps the parser to identify when to stop the parsing and announce the acceptance
of the input. The input string is accepted if and only if the parser is about to reduce by S`-> S.
NOTE: Augment Grammar is simply adding one extra production by preserving the actual
meaning of the given Grammar G.

Stack
Contains string of the form s0X1s1X2…..Xmsm where sm is on the top of the stack. Each Xi
denotes a grammar symbol and si a state. Each state symbol summarizes the information
contained in the stack below it
Parser Program
This determines the state on the sm on the top of the stack and the current input symbol a to
determine the next step

Types LR Parsers
SLR parsing, CLR parsing and LALR parsing.

2.9.1 SLR PARSING

SLR (1) refers to simple LR Parsing. It is same as LR(0) parsing. The only difference is in the
parsing table. To construct SLR (1) parsing table, we use canonical collection of LR (0) item.

In the SLR (1) parsing, we place the reduce move only in the follow of left hand side.
Various steps involved in the SLR (1) Parsing:
o For the given input string write a context free grammar
o Check the ambiguity of the grammar

Page 24 of 37
 o Add Augment production in the given grammar
o Create Canonical collection of LR (0) items
o Draw a data flow diagram (DFA)
o Construct a SLR (1) parsing table

Example : To construct SLR ( 1 ) parser of the given grammar

E→E+T
E→T
T→T*F
T→ F
F →(E)
F → id
Solution:
The canonical collection of SLR(1) items are
Closure
I0:
E’ → .E
E → .E + T
E → .T
T → .T * F
T → .F
F → .( E )
F → .id

I1: GOTO(I0,E)
E’ → E.
E → E.+ T

I2: GOTO(I0,T)
E → T.
T → T .* F

I3: GOTO(I0,F)

Page 25 of 37
T → F.

I4: GOTO(I0,( )
F → (.E)
E→.E+T
E → .T
T → .T * F
T → .F
F → .( E )
F → .id

I5: GOTO(I0,id)
F → id.

I6: GOTO(I1,E)
E → E + .T
T → .T * F
T → .F
F → .( E )
F → .id
I7: GOTO(I2,*)
T → T * .F
F → .( E)
F → .id

I8: GOTO(I4,E)
F → ( E .)
E → E. + T

I9: GOTO(I6,T)
E → E + T.
T → T. * F

Page 26 of 37
I10: GOTO(I7,F)
T → T * F.

I11: GOTO(I8,) )
F → ( E ).

SLR Parsing Table

ACTION GOTO
STATES id + * ( ) $ E T F
0 s5 1 2 3
1 s6 s4 ACC
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 S4 8
5 r6 r6 r6 r6
6 s5 s4 9
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5

2.9.2 CLR PARSING

CLR refers to canonical lookahead. CLR parsing use the canonical collection of LR (1) items
to build the CLR (1) parsing table. CLR (1) parsing table produces the more number of states
as compare to the SLR (1) parsing.

In the CLR (1), we place the reduce node only in the lookahead symbols. Various steps
involved in the CLR (1) Parsing:

o For the given input string write a context free grammar

o Check the ambiguity of the grammar
o Add Augment production in the given grammar

Page 27 of 37
 o Create Canonical collection of LR (0) items
o Draw a data flow diagram (DFA)
o Construct a CLR (1) parsing table

LR (1) item

LR (1) item is a collection of LR (0) items and a look ahead symbol.

LR (1) item = LR (0) item + look ahead

The look ahead is used to determine that where we place the final item.

The look ahead always add $ symbol for the argument production.

Example: To construct CLR Parser of the given grammar

S → AA
A → aA
A→b
Add Augment Production, insert '•' symbol at the first position for every production in G and
also add the lookahead.

S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b

I0 State:

Add Augment production to the I0 State and Compute the Closure

I0 = Closure (S` → •S)

Add all productions starting with S in to I0 State because "." is followed by the non-terminal.
So, the I0 State becomes

Page 28 of 37
I0 = S` → •S, $
S → •AA, $

Add all productions starting with A in modified I0 State because "." is followed by the non-
terminal. So, the I0 State becomes.

I0= S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b

I1= Go to (I0, S) = closure (S` → S•, $) = S` → S•, $

I2= Go to (I0, A) = closure ( S → A•A, $ )

Add all productions starting with A in I2 State because "." is followed by the non-terminal.
So, the I2 State becomes

I2= S → A•A, $
A → •aA, $
A → •b, $

I3= Go to (I0, a) = Closure ( A → a•A, a/b )

Add all productions starting with A in I3 State because "." is followed by the non-terminal.
So, the I3 State becomes

I3= A → a•A, a/b

A → •aA, a/b
A → •b, a/b

Go to (I3, a) = Closure (A → a•A, a/b) = (same as I3)

Go to (I3, b) = Closure (A → b•, a/b) = (same as I4)

Page 29 of 37
I4= Go to (I0, b) = closure ( A → b•, a/b) = A → b•, a/b
I5= Go to (I2, A) = Closure (S → AA•, $) =S → AA•, $
I6= Go to (I2, a) = Closure (A → a•A, $)

Add all productions starting with A in I6 State because "." is followed by the non-terminal.
So, the I6 State becomes

I6 = A → a•A, $
A → •aA, $
A → •b, $

Go to (I6, a) = Closure (A → a•A, $) = (same as I6)

Go to (I6, b) = Closure (A → b•, $) = (same as I7)

I7= Go to (I2, b) = Closure (A → b•, $) = A → b•, $

I8= Go to (I3, A) = Closure (A → aA•, a/b) = A → aA•, a/b
I9= Go to (I6, A) = Closure (A → aA•, $) = A → aA•, $

Drawing DFA:

CLR Parsing table:

2.9.3 LALR PARSING

LALR refers to the lookahead LR. To construct the LALR (1) parsing table, we use the
canonical collection of LR (1) items.

Page 30 of 37
In the LALR (1) parsing, the LR (1) items which have same productions but different look
ahead are combined to form a single set of items
LALR (1) parsing is same as the CLR (1) parsing, only difference in the parsing table.

Example : To construct LALR Parser of the given Grammar

S → AA
A → aA
A→b
Add Augment Production, insert '•' symbol at the first position for every production in G and
also add the look ahead.
S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b

I0 State:

Add Augment production to the I0 State and Compute the ClosureL

I0 = Closure (S` → •S)

Add all productions starting with S in to I0 State because "•" is followed by the non-terminal.
So, the I0 State becomes

I0 = S` → •S, $
S → •AA, $

Add all productions starting with A in modified I0 State because "•" is followed by the non-
terminal. So, the I0 State becomes.

I0= S` → •S, $
S → •AA, $
A → •aA, a/b
A → •b, a/b

I1= Go to (I0, S) = closure (S` → S•, $) = S` → S•, $

I2= Go to (I0, A) = closure ( S → A•A, $ )

Page 31 of 37
Add all productions starting with A in I2 State because "•" is followed by the non-terminal.
So, the I2 State becomes

I2= S → A•A, $
A → •aA, $
A → •b, $

I3= Go to (I0, a) = Closure ( A → a•A, a/b )

Add all productions starting with A in I3 State because "•" is followed by the non-terminal.
So, the I3 State becomes

I3= A → a•A, a/b

A → •aA, a/b
A → •b, a/b

Go to (I3, a) = Closure (A → a•A, a/b) = (same as I3)

Go to (I3, b) = Closure (A → b•, a/b) = (same as I4)

I4= Go to (I0, b) = closure ( A → b•, a/b) = A → b•, a/b

I5= Go to (I2, A) = Closure (S → AA•, $) =S → AA•, $
I6= Go to (I2, a) = Closure (A → a•A, $)

Add all productions starting with A in I6 State because "•" is followed by the non-terminal.
So, the I6 State becomes

I6 = A → a•A, $
A → •aA, $
A → •b, $

Go to (I6, a) = Closure (A → a•A, $) = (same as I6)

Go to (I6, b) = Closure (A → b•, $) = (same as I7)

Page 32 of 37
I7= Go to (I2, b) = Closure (A → b•, $) = A → b•, $
I8= Go to (I3, A) = Closure (A → aA•, a/b) = A → aA•, a/b
I9= Go to (I6, A) = Closure (A → aA•, $) A → aA•, $

If we analyze then LR (0) items of I3 and I6 are same but they differ only in their lookahead.

I3 = { A → a•A, a/b
A → •aA, a/b
A → •b, a/b
}

I6= { A → a•A, $
A → •aA, $
A → •b, $
}

Clearly I3 and I6 are same in their LR (0) items but differ in their lookahead, so we can
combine them and called as I36.

I36 = { A → a•A, a/b/$

A → •aA, a/b/$
A → •b, a/b/$
}

The I4 and I7 are same but they differ only in their look ahead, so we can combine them and
called as I47.

I47 = {A → b•, a/b/$}

The I8 and I9 are same but they differ only in their look ahead, so we can combine them and
called as I89.

I89 = {A → aA•, a/b/$}

Drawing DFA:

Page 33 of 37
LALR Parsing table:

2.10 AUTOMATIC PARSER GENERATOR-YACC

YACC stands for Yet Another Compiler Compiler. This program is available in UNIX OS .
The construction of LR parser requires lot of work for parsing the input string. Hence, the
process must involve automation to achieve efficiency in parsing an input . Basically YACC
is a LALR parser generator that reports conflicts or uncertainties (if at all present) in the form
of error messages. The typical YACC translator can be represented as shown in the image

YACC Specification
The YACC specification file consists of three parts.
Declaration section: In this section, ordinary C declarations are inserted and grammar tokens
are declared. The tokens should be declared between %{ and %}
Translation rule section
It includes the production rules of context free grammar with corresponding actions
Rule-1 action-1
Rule-2 action-2
:
:
Rule n action n
If there is more than one alternative to a single rule then those alternatives are separated by ‘|’
(pipe) character. The actions are typical C statements. If CFG is
LHS: alternative 1 | alternative 2 | …… alternative n
Then
LHS: alternative 1 {action 1}
| alternative 2 {action 1}
:
:
alternative n {action n}

Page 34 of 37
C functions Section: this consists of one main function in which the routine yyparse() is
called. And it also contains required C functions

The specification file comprising these sections can be written as:

%{
/ * declaration section */
%}
/* Translation rule section */
%%
/* Required C functions */

Example:
YACC Specification of a simple desk calculator:
%{
#include <ctype.h>
%}
%token DIGIT
%%
line: expr ‘\n’ { printf(“%d\n”, $1); }
;
expr : expr ‘+’ term { $$ = $1 + $3; }
| term
;
term : term ‘*’ factor { $$ = $1 * $3; }
| factor
;
factor : ‘(‘ expr ‘)’ { $$ = $2; }
| DIGIT
;
%%
yylex() {
int c;
c = getchar();
if(isdigit(c)
{
yylval = c-‘0’;
return DIGIT;
}
return c;
}

2.11 AMBIGUOUS GRAMMARS

Page 35 of 37
YACC declarations resolve shift/reduce and reduce/reduce conflicts using operator
precedence and operator associativity information
YACC has default methods for resolving conflicts. However, it is better to find out what
conflicts arose and how they were resolved using the ‘-v’ option
The declarations provide a way to override YACCs defaults
Productions have the precedence of their rightmost terminal, unless otherwise specified by
“%prec” element

The declaration keywords %left, %right and %nonassoc inform YACC that the following
tokens are to be treated as left-associative (as binary + - * & / commonly are), right-
associative (as exp often is), or non-associative (as binay < & > often are)
The order of declarations informs YACC that the tokens should be accorded increasing
precedence

%left ‘+’ ‘-‘ Effect is that * has higher precedence

%left ‘*’ ‘|’ Than +, so x+y*z is grouped like x+(y*z)

YACC Specification for a more advanced desk calculator:

%{
#include <ctype.h>
#include <stdiio.h>
#define YYSTYPE double /* double type for YACC stack */
%}
%token NUMBER
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
%right UMINUS
%%
lines : lines expr ‘\n’ { printf(“%g\n”, $2); }
| lines ‘\n’
| /* empty */
;
expr : expr ‘+’ expr { $$ = $1 + $3; }
| expr ‘-‘ expr { $$ = $1 - $3; }
| expr ‘*’ expr {$$ = $1 * $3; }
| expr ‘/’ expr {$$ = $1 / $3; }
| ‘(‘ expr ‘)’ {$$ = $2;}
| ‘-‘ expr %prec UMINUS { $$ = -$2; }
| NUMBER
;
Page 36 of 37
%
yylex() {
int c;
while (( c = getchar() ) == ‘ ‘ );
if ((c == ‘.’) || (isdigit(c) ) {
unget(c, stdin);
scanf(“%1f”, &uulval);
return Number;
}
return c;

Page 37 of 37
 UNIT - III

Syntax-Directed Translation: Syntax-Directed Definitions, Evaluation Orders for SDD's,

Applications of Syntax-Directed Translation, Syntax-Directed Translation Schemes,
Implementing L-Attributed SDD's.
Intermediate-Code Generation: Variants of Syntax Trees, Three-Address Code, Types and
Declarations, Type Checking, Control Flow, Switch-Statements, Intermediate Code for
Procedures.

3.1 SYNTAX-DIRECTED DEFINITIONS

Syntax Directed Definition (SDD) is a kind of abstract specification. It is generalization of
context free grammar in which each grammar production X –> a is associated with it a set of
production rules of the form s = f(b1, b2, ……bk) where s is the attribute obtained from function f.
The attribute can be a string, number, type or a memory location. Semantic rules are fragments
of code which are embedded usually at the end of production and enclosed in curly braces ({ }).

• In syntax directed translation, every non-terminal can get one or more than one attribute
or sometimes 0 attribute depending on the type of the attribute. The value of these
attributes is evaluated by the semantic rules associated with the production rule.
• In the semantic rule, attribute is VAL and an attribute may hold anything like a string, a
number, a memory location and a complex record
• In Syntax directed translation, whenever a construct encounters in the programming
language then it is translated according to the semantic rules define in that particular
programming language.
Example:

Production Semantic Rules

E→E+T [Link] := [Link] + [Link]

E→T [Link] := [Link]

Page 1 of 20
 T→T*F [Link] := [Link] + [Link]

T→F [Link] := [Link]

F → (F) [Link] := [Link]

F → num [Link] := [Link]

[Link] is one of the attributes of E.

Types of attributes – There are two types of attributes:

1. Synthesized Attributes – These are those attributes which derive their values from their
children nodes i.e. value of synthesized attribute at node is computed from the values of
attributes at children nodes in parse tree.

Example:
E --> E1 + T { [Link] = [Link] + [Link]}
In this, [Link] derive its values from [Link] and [Link]

• Write the SDD using appropriate semantic rules for each production in given grammar.
• The annotated parse tree is generated and attribute values are computed in bottom up
manner.
• The value obtained at root node is the final output.
Example: Consider the following grammar
S --> E
E --> E1 + T
E --> T
T --> T1 * F
T --> F
F --> digit
The SDD for the above grammar can be written as follow

Page 2 of 20
Let us assume an input string 4 * 5 + 6 for computing synthesized attributes. The annotated parse
tree for the input string is

For computation of attributes we start from leftmost bottom node. The rule F –> digit is used to
reduce digit to F and the value of digit is obtained from lexical analyzer which becomes value of

Page 3 of 20
F i.e. from semantic action [Link] = [Link]. Hence, [Link] = 4 and since T is parent node of F
so, we get [Link] = 4 from semantic action [Link] = [Link]. Then, for T –> T1 * F production, the
corresponding semantic action is [Link] = [Link] * [Link] . Hence, [Link] = 4 * 5 = 20

Similarly, combination of [Link] + [Link] becomes [Link] i.e. [Link] = [Link] + [Link] = 26. Then, the
production S –> E is applied to reduce [Link] = 26 and semantic action associated with it prints
the result [Link] . Hence, the output will be 26.

2. Inherited Attributes – These are the attributes which derive their values from their parent or
sibling nodes i.e. value of inherited attributes are computed by value of parent or sibling nodes.
Example:
A --> BCD { [Link] = [Link], [Link] = [Link] }

Computation of Inherited Attributes –

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

Example: Consider the following grammar

S --> T L
T --> int
T --> float
T --> double
L --> L1, id
L --> id

The SDD for the above grammar can be written as follow

Page 4 of 20
Let us assume an input string int a, c for computing inherited attributes. The annotated parse tree
for the input string is

The value of L nodes is obtained from [Link] (sibling) which is basically lexical value obtained
as int, float or double. Then L node gives type of identifiers a and c. The computation of type is
done in top down manner or preorder traversal. Using function Enter_type the type of identifiers
a and c is inserted in symbol table at corresponding [Link].

Page 5 of 20
3.2 SYNTAX DIRECTED TRANSLATION SCHEME
• The Syntax directed translation scheme is a context -free grammar.
• The syntax directed translation scheme is used to evaluate the order of semantic rules.
• In translation scheme, the semantic rules are embedded within the right side of the
productions.
• The position at which an action is to be executed is shown by enclosed between braces. It
is written within the right side of the production.
Example

Production Semantic Rules

S→E$ { [Link] }

E→E+E {[Link] := [Link] + [Link] }

E→E*E {[Link] := [Link] * [Link] }

E → (E) {[Link] := [Link] }

E→I {[Link] := [Link] }

I → I digit {[Link] := 10 * [Link] + LEXVAL }

I → digit { [Link]:= LEXVAL}

3.3 SYNTAX-DIRECTED TRANSLATION IMPLEMENTATION

Syntax direct translation is implemented by constructing a parse tree and performing the actions
in a left to right depth first order. SDT is implementing by parse the input and produce a parse
tree as a result.
Example

Production Semantic Rules

Page 6 of 20
 S→E$ { [Link] }

E→E+E {[Link] := [Link] + [Link] }

E→E*E {[Link] := [Link] * [Link] }

E → (E) {[Link] := [Link] }

E→I {[Link] := [Link] }

I → I digit {[Link] := 10 * [Link] + LEXVAL }

I → digit { [Link]:= LEXVAL}

Parse tree for SDT:

3.4 INTERMEDIATE-CODE GENERATION

In Intermediate code generation we use syntax directed methods to translate the source program
into an intermediate form programming language constructs such as declarations, assignments
and flow-of-control statements.

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

Advantages of an intermediate language

1. Retargeting is facilitated - Build a compiler for a new machine by attaching a new code
generator to an existing front-end.
2. Optimization - reuse intermediate code optimizers in compilers for different languages
and different machines.

Note: the terms ―intermediate code‖, ―intermediate language‖, and ―intermediate

representation‖ are all used interchangeably.

Types of Intermediate representations / forms: There are three types of intermediate

representation:-
1. Syntax Trees
2. Postfix notation
3. Three Address Code

Syntax tree

Page 8 of 20
When you create a parse tree then it contains more details than actually needed. So, it is very
difficult to compiler to parse the parse tree. Take the following parse tree as an example:

• In the parse tree, most of the leaf nodes are single child to their parent nodes.
• In the syntax tree, we can eliminate this extra information.
• Syntax tree is a variant of parse tree. In the syntax tree, interior nodes are operators and
leaves are operands.
• Syntax tree is usually used when represent a program in a tree structure.
A sentence id + id * id would have the following syntax tree:

Page 9 of 20
Abstract syntax trees are important data structures in a compiler. It contains the least unnecessary
information.
Abstract syntax trees are more compact than a parse tree and can be easily used by a compiler.

Postfix Notation
• Postfix notation is the useful form of intermediate code if the given language is
expressions.
• Postfix notation is also called as 'suffix notation' and 'reverse polish'.
• Postfix notation is a linear representation of a syntax tree.
• In the postfix notation, any expression can be written unambiguously without
parentheses.
• The ordinary (infix) way of writing the sum of x and y is with operator in the middle: x *
y. But in the postfix notation, we place the operator at the right end as xy *.
• In postfix notation, the operator follows the operand.

Example
Production
1. E → E1 op E2
2. E → (E1)
3. E → id

Semantic Rule Program fragment

[Link] = [Link] || [Link] || op print op

Page 10 of 20
[Link] = [Link]

[Link] = id print id

Three address code

• Three-address code is an intermediate code. It is used by the optimizing compilers.
• In three-address code, the given expression is broken down into several separate
instructions. These instructions can easily translate into assembly language.
• Each Three address code instruction has at most three operands. It is a combination of
assignment and a binary operator.
Example
a := (-c * b) + (-c * d)
Three-address code is as follows:
t1 := -c
t2 := b*t1
t3 := -c
t4 := d * t3
t5 := t2 + t4
a := t5
t is used as registers in the target program. The three address code can be represented in two
forms: quadruples and triples.

Quadruples
The quadruples have four fields to implement the three address code. The field of quadruples
contains the name of the operator, the first source operand, the second source operand and the
result respectively.

Example
1. a := -b * c + d
Three-address code is as follows:
t1 := -b

Page 11 of 20
 t2 := c + d
t3 := t1 * t2
a := t3

These statements are represented by quadruples as follows:

Operator Source 1 Source 2 Destination

(0) uminus B - t1

(1) + c d t2

(2) * t1 t2 t3

(3) := t3 - a

Triples
The triples have three fields to implement the three address code. The field of triples contains the
name of the operator, the first source operand and the second source operand.
Example:
a := -b * c + d
Three address code is as follows:
t1 := -b
t2 := c + d
t3 := t1 * t2
a := t3
These statements are represented by triples as follows:

Operator Source 1 Source 2

Page 12 of 20
(0) uminus b -

(1) + c d

(2) * (0) (1)

(3) := (2) -

3.5 TYPES AND DECLARATIONS

As the sequence of declarations in a procedure or block is examined, we can lay out storage for
names local to the procedure. For each local name, we create a symbol-table entry with
information like the type and the relative address of the storage for the name. The relative
address consists of an offset from the base of the static data area or the field for local data in an
activation record.

Declarations in a Procedure:
The syntax of languages such as C, Pascal and Fortran, allows all the declarations in a
single procedure to be processed as a group. In this case, a global variable, say offset, can keep
track of the next available relative address.
In the translation scheme shown below:
• Non-terminal P generates a sequence of declarations of the form id : T.
• Before the first declaration is considered, offset is set to 0. As each new name is seen ,
that name is entered in the symbol table with offset equal to the current value of offset,
and offset is incremented by the width of the data object denoted by that name.
• The procedure enter( name, type, offset ) creates a symbol-table entry for name, gives its
type type and relative address offset in its data area.
• Attribute type represents a type expression constructed from the basic types integer and
real by applying the type constructors pointer and array. If type expressions are
represented by graphs, then attribute type might be a pointer to the node representing a
type expression.

Page 13 of 20
 • The width of an array is obtained by multiplying the width of each element by the
number of elements in the array. The width of each pointer is assumed to be 4.

Computing the types and relative addresses of declared names

3.6 FLOW-OF-CONTROL STATEMENTS

We now consider the translation of boolean expressions into three-address code in the context of
if-then, if-then-else, and while-do statements such as those generated by the following grammar:

In each of these productions, E is the Boolean expression to be translated. In the translation, we

assume that a three-address statement can be symbolically labeled, and that the function
newlabel returns a new symbolic label each time it is called.

Page 14 of 20
 ➢ [Link] is the label to which control flows if E is true, and [Link] is the label to which
control flows if E is false.
➢ The semantic rules for translating a flow-of-control statement S allow control to flow
from the translation [Link] to the three-address instruction immediately following
[Link].
➢ [Link] is a label that is attached to the first three-address instruction to be executed after
the code for S.
Code for if-then , if-then-else, and while-do statements

Syntax-directed definition for flow-of-control statements

Page 15 of 20
Control-Flow Translation of Boolean Expressions:
Syntax-directed definition to produce three-address code for Booleans

Page 16 of 20
3.7 CASE STATEMENTS
The “switch” or “case” statement is available in a variety of languages. The switch-statement
syntax is as shown below :

Syntax-Directed Translation of Case Statements:

Page 17 of 20
Translation of a case statement

3.8 INTERMEDIATE CODE FOR PROCEDURES

The procedure is such an important and frequently used programming construct that it is
imperative for a compiler to generate good code for procedure calls and returns. The run-time
routines that handle procedure argument passing, calls and returns are part of the run-time
support package.
Let us consider a grammar for a simple procedure call statement

Page 18 of 20
Calling Sequences: The translation for a call includes a calling sequence, a sequence of actions
taken on entry to and exit from each procedure. The falling are the actions that take place in a
calling sequence :

1. When a procedure call occurs, space must be allocated for the activation record of the
called procedure.
2. The arguments of the called procedure must be evaluated and made available to the called
procedure in a known place.
3. Environment pointers must be established to enable the called procedure to access data in
enclosing blocks.
4. The state of the calling procedure must be saved so it can resume execution after the call.
5. Also saved in a known place is the return address, the location to which the called,
routine must transfer after it is finished.
6. Finally a jump to the beginning of the code for the called procedure must be generated.

For example, consider the following syntax-directed translation

Page 19 of 20
➢ Here, the code for S is the code for Elist, which evaluates the arguments, followed by a
param p statement for each argument, followed by a call statement.
➢ queue is emptied and then gets a single pointer to the symbol table location for the name
that denotes the value of E.

Page 20 of 20
 UNIT – IV

Run-Time Environments: Stack Allocation of Space, Access to Nonlocal Data on the Stack,
Heap Management, Introduction to Garbage Collection, Introduction to Trace-Based
Collection.
Code Generation: Issues in the Design of a Code Generator, The Target Language, Addresses
in the Target Code, Basic Blocks and Flow Graphs, Optimization of Basic Blocks, A Simple
Code Generator, Peephole Optimization, Register Allocation and Assignment, Dynamic
Programming Code-Generation.

4.1 STACK ALLOCATION OF SPACE

Almost all compilers for languages that use procedures, functions, or methods as units of user-
defined actions manage at least part of their run-time memory as a stack. Each time a
procedure1 is called, space for its local variables is pushed onto a stack, and when the procedure
terminates, that space is popped off the stack. As we shall see, this arrangement not only allows
space to be shared by procedure calls whose durations do not overlap in time, but it allows us
to compile code for a procedure in such a way that the relative addresses of its nonlocal
variables are always the same, regardless of the sequence of procedure calls.
Stack allocation is a procedure in which stack is used to organize the storage. The stack used
in stack allocation is known as control stack. In this type of allocation, creation of data objects
is performed dynamically. In stack allocation, activation records are created for the allocation
of memory. These activation records are pushed onto the stack using Last In First Out (LIFO)
method. Locals are stored in the activation records at run time and memory addressing is done
by using pointers and registers.

• Stack allocation makes data structures and objects dynamically.

While in stack allocation, allocation of data objects is performed at run time.
It supports recursive procedures.
Stack allocation use stack to manage the allocation of memory at run time.

Page 1 of 23
4.2 ACCESS TO NONLOCAL DATA ON THE STACK

The scope of a declaration in a block-structured language is given by the most closely nested
rule: – The scope of a declaration in a block B includes B. – If a name X is not declared in a
block B, then an occurrence of X in B is in the scope of a declaration of X in an enclosing block
B´ such that
● B´ has a declaration of X, and
● B´ is more closely nested around B than any other block with a declaration of X

4.3 HEAP MANAGEMENT

Introduction: Heap used for dynamically allocated memory, its important operations includes
allocation and de-allocation. In C , Pascal, and Java allocation is done via the “new” operator
and C allocation is done via the “malloc” function call. De-allocation is done either
automatically. The heap is the portion of the store that is used for data that lives indefinitely,
or until the program explicitly deletes it.
While local variables typically become inaccessible when their procedures end, many
languages enable us to create objects or other data whose existence is not tied to the procedure
activation that creates them. For example, both C and Java give the programmer new to create
objects that may be passed — or pointers to them may be passed — from procedure to
procedure, so they continue to exist long after the procedure that created them is gone. Such
objects are stored on a heap.
Heap Memory Manager: The memory manager keeps track of all the free space in heap storage
at all times. It performs two basic functions:

• Allocation. When a program requests memory for a variable or object,3 the memory
manager produces a chunk of contiguous heap memory of the requested size. If
possible, it satisfies an allocation request using free space in the heap; if no chunk of
the needed size is available, it seeks to increase the heap storage space by getting
consecutive bytes of virtual memory from the operating system. If space is exhausted,
the memory manager passes that information back to the application program.

• De-allocation. The memory manager returns de-allocated space to the pool of free
space, so it can reuse the space to satisfy other allocation requests.

Memory managers typically do not return memory to the operating system, even if the
program's heap usage drops. Memory management would be simpler if (a) all allocation
requests were for chunks of the same size, and (b) storage were released predictably, say, first-
allocated first-de-allocated. There are some languages, such as Lisp, for which condition (a)

Page 2 of 23
holds; pure Lisp uses only one data element — a two pointer cell — from which all data
structures are built. Condition (b) also holds in some situations, the most common being data
that can be allocated on the run-time stack. However, in most languages, neither (a) nor (b)
holds in general. Rather, data elements of different sizes are allocated, and there is no good
way to predict the lifetimes of all allocated objects.

Here are the properties we desire of memory managers:

Space Efficiency. A memory manager should minimize the total heap space needed by
a program. Doing so allows larger programs to run in a fixed virtual address space.
Space efficiency is achieved by minimizing "fragmentation," discussed in Section
7.4.4.

Program Efficiency. A memory manager should make good use of the memory
subsystem to allow programs to run faster. As the time taken to execute an instruction
can vary widely depending on where objects are placed in memory. Fortunately,
programs tend to exhibit "locality," which refers to the nonrandom clustered way in
which typical programs access memory. By attention to the placement of objects in
memory, the memory manager can make better use of space and, hopefully, make the
program run faster.

Low Overhead. Because memory allocations and de-allocations are frequent operations
in many programs, it is important that these operations be as efficient as possible. That
is, we wish to minimize the overhead — the fraction of execution time spent performing
allocation and de-allocation. Notice that the cost of allocations is dominated by small
requests; the overhead of managing large objects is less important, because it usually
can be amortized over a larger amount of computation.

4.4 INTRODUCTION TO GARBAGE COLLECTION

In computer science, garbage collection is a type of memory management. It automatically

cleans up unused objects and pointers in memory, allowing the resources to be used again.
Some programming languages have built-in garbage collection, while others require custom
functions to manage unused memory.
A common method of garbage collection is called reference counting. This strategy simply
counts how many references there are to each object stored in memory. If an object has zero

Page 3 of 23
references, it is considered unnecessary and can be deleted to free up the space in memory.
Advanced reference counting detects objects that only reference each other, which indicates
the objects are unused by the parent process.
Garbage collection may also be done at compile-time, when a program's source code is
compiled into an executable program. In this method, the compiler determines which resources
in memory will never be accessed after a certain time. It can then add instructions to
automatically deallocate those resources from memory. While this is an effective way to
eliminate unused objects, it must be done conservatively to avoid deleting references required
by the program.
Garbage collection is an important part of software development since it keeps programs from
using up too much RAM. Besides helping programs run more efficiently, it can also prevent
serious bugs, such as memory leaks, that can cause a program to crash.

4.5 INTRODUCTION TO TRACE-BASED COLLECTION

Introduction: Instead of collecting garbage as it is created, trace-based collectors run
periodically to find unreachable objects and reclaim their space. Typically, we run the trace-
based collector whenever the free space is exhausted or its amount drops below some threshold.

We begin this section by introducing the simplest "mark-and-sweep" garbage collection

algorithm. We then describe the variety of trace-based algorithms in terms of four states that
chunks of memory can be put in. This section also contains a number of improvements on the
basic algorithm, including those in which object relocation is a part of the garbage-collection
function.
A Basic Mark-and-Sweep Collector: Mark-and-sweep garbage-collection algorithms are
straightforward, stop-the world algorithms that find all the unreachable objects, and put them
on the list of free space. Following Algorithm visits and "marks" all the reachable objects in
the first tracing step and then "sweeps" the entire heap to free up unreachable objects.

Page 4 of 23
Following Algorithm, which we consider after introducing a general framework for trace-based
algorithms, is an optimization of following Algorithm. By using an additional list to hold all
the allocated objects, it visits the reachable objects only once.
Algorithm: Mark-and-sweep garbage collection.
INPUT: A root set of objects, a heap, and a free list, called Free, with all the unallocated chunks
of the heap. All chunks of space are marked with boundary tags to indicate their free/used status
and size.
OUTPUT: A modified free list after all the garbage has been removed.

METHOD: The algorithm, shown in Fig. 7.21, uses several simple data structures. List Free
holds objects known to be free. A list called Unscanned, holds objects that we have determined
are reached, but whose successors we have not yet considered. That is, we have not scanned
these objects to see what other objects can be reached through them. The Unscanned list is
empty initially.

Additionally, each object includes a bit to indicate whether it has been reached (the reached-
bit). Before the algorithm begins, all allocated objects have the reached-bit set to 0.
In line (1) of Fig. 7.21, we initialize the Unscanned list by placing there all the objects
referenced by the root set. The reached-bit for these objects is also set to 1. Lines (2) through

Page 5 of 23
(7) are a loop, in which we, in turn, examine each object o that is ever placed on the Unscanned
list. The for-loop of lines (4) through (7) implements the scanning of object o.
We examine each object d for which we find a reference within o. If d has already been reached
(its reached-bit is 1), then there is no need to do anything about d; it either has been scanned
previously, or it is on the Unscanned list to be scanned later. However, if d was not reached
already, then we need to set its reached-bit to 1 in line (6) and add d to the Unscanned list in
line (7). Figure 7.22 illustrates this process. It shows an Unscanned list with four objects. The
first object on this list, corresponding to object o in the discussion above, is in the process of
being scanned. The dashed lines correspond to the three kinds of objects that might be reached
from o:
1. A previously scanned object that need not be scanned again.
2. An object currently on the Unscanned list.
3. An item that is reachable, but was previously thought to be unreached.

Lines (8) through (11), the sweeping phase, reclaim the space of all the objects that remain
unreached at the end of the marking phase. Note that these will include any objects that were
on the Free list originally. Because the set of unreached objects cannot be enumerated directly,
the algorithm sweeps through the entire heap. Line (10) puts free and unreached objects on the
Free list, one at a time. Line (11) handles the reachable objects. We set their reached-bit to 0, in
order to maintain the proper preconditions for the next execution of the garbage-collection
algorithm.

4.6 ISSUES IN THE DESIGN OF A CODE GENERATOR

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 code generator should be done in such a way so that it can be easily implemented,
tested and maintained.

Page 6 of 23
The following issue arises during the code generation phase:
1. Input to code generator
The input to 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,
DAG’s, etc. The code generation phase just proceeds on an assumption that the input are free
from all of syntactic and state semantic errors, the necessary type checking has taken place and
the type-conversion operators have been inserted wherever necessary.
2. Target program
The target program is the output of the code generator. The output may be absolute machine
language, relocatable machine language, assembly language.
Absolute machine language as output has advantages that it can be placed in a fixed memory
location and can be immediately executed.

Relocatable machine language as an output allows subprograms and subroutines to be

compiled separately. Relocatable object modules can be linked together and loaded by 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 macro-facilities of assembler in generating code. And we need an
additional assembly step after code generation.
3. 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 name. Then from the symbol table entry, a relative address can be determined for the
name.
4. 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
plays a major role when efficiency is considered. But if we do not care about the efficiency of
the target program then instruction selection is straight-forward.

Page 7 of 23
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. A prior knowledge of instruction cost
is needed in order to design good sequences, but accurate cost information is difficult to predict.
5. 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 are subdivided into two subproblems:
1. During Register allocation – we select only those set of variables that will reside in the
registers at each point in the program.

2. During a subsequent Register assignment phase, the specific register is picked to access the
variable.
As the number of variables increases, the optimal assignment of registers to variables becomes
difficult. Mathematically, this problem becomes NP-complete. Certain machine requires
register pairs consist of an even and next odd-numbered register. For example
M a, b
These types of multiplicative instruction involve register pairs where the multiplicand is an
even register and b, the multiplier is the odd register of the even/odd register pair.
Evaluation order –

Page 8 of 23
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 problem.
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

4.7 BASIC BLOCKS AND FLOW GRAPHS

Basic block is a set of statements that always executes in a sequence one after the other.
The characteristics of basic blocks are-
They do not contain any kind of jump statements in them.

There is no possibility of branching or getting halt in the middle.

All the statements execute in the same order they appear.

They do not lose lose the flow control of the program.

Example Of Basic Block
Three Address Code for the expression a = b + c + d is-

Page 9 of 23
Here,
All the statements execute in a sequence one after the other.

Thus, they form a basic block.

Flow Graphs-
A flow graph is a directed graph with flow control information added to the basic blocks.
The basic blocks serve as nodes of the flow graph.

There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in

the code.

Example:
Compute the basic blocks for the given three address statements-
(1) PROD = 0
(2) I = 1
(3) T2 = addr(A) – 4
(4) T4 = addr(B) – 4
(5) T1 = 4 x I

(6) T3 = T2[T1]

(7) T5 = T4[T1]
(8) T6 = T3 x T5
(9) PROD = PROD + T6
(10) I = I + 1
(11) IF I <=20 GOTO (5)
Solution-

We have-

• PROD = 0 is a leader since first statement of the code is a leader.

• T1 = 4 x I is a leader since target of the conditional goto statement is a leader.

Page 10 of 23
Now, the given code can be partitioned into two basic blocks as-

Page 11 of 23
The required flow graph is-

4.8 OPTIMIZATION OF BASIC BLOCKS

Page 12 of 23
Optimization process can be applied on a basic block. While optimization, we don't need to
change the set of expressions computed by the block.

There are two type of basic block optimization. These are as follows:
1. Structure-Preserving Transformations
2. Algebraic Transformations
1. Structure preserving transformations:
The primary Structure-Preserving Transformation on basic blocks is as follows:

o Common sub-expression elimination

o Dead code elimination

o Renaming of temporary variables

o Interchange of two independent adjacent statements

(a) Common sub-expression elimination:
In the common sub-expression, you don't need to be computed it over and over again. Instead of
this you can compute it once and kept in store from where it's referenced when encountered again.
1. a : = b + c

2. b : = a - d

3. c : = b + c

4. d : = a - d

In the above expression, the second and forth expression computed the same expression. So the
block can be transformed as follows:
1. a : = b + c

2. b : = a - d

3. c : = b + c

4. d : = b

(b) Dead-code elimination

o It is possible that a program contains a large amount of dead code.

Page 13 of 23
o This can be caused when once declared and defined once and forget to remove them in this case

they serve no purpose.

o Suppose the statement x:= y + z appears in a block and x is dead symbol that means it will never

subsequently used. Then without changing the value of the basic block you can safely remove this
statement.
(c) Renaming temporary variables
A statement t:= b + c can be changed to u:= b + c where t is a temporary variable and u is a
new temporary variable. All the instance of t can be replaced with the u without changing the
basic block value.
(d) Interchange of statement
Suppose a block has the following two adjacent statements:
1. t1 : = b + c

2. t2 : = x + y

These two statements can be interchanged without affecting the value of block when value of
t1 does not affect the value of t2.
2. Algebraic transformations:
o In the algebraic transformation, we can change the set of expression into an
algebraically equivalent set. Thus the expression x:= x + 0 or x:= x *1 can be eliminated
from a basic block without changing the set of expression.

o Constant folding is a class of related optimization. Here at compile time, we evaluate

constant expressions and replace the constant expression by their values. Thus the
expression 5*2.7 would be replaced by13.5.

o Sometimes the unexpected common sub expression is generated by the relational

operators like <=, >=, <, >, +, = etc.

o Sometimes associative expression is applied to expose common sub expression

without changing the basic block value. if the source code has the assignments

1. a:= b + c

2. e:= c +d +b
The following intermediate code may be generated:
1. a:= b + c

Page 14 of 23
2. t:= c +d

3. e:= t + b

4.9 A SIMPLE CODE GENERATOR

• A code generator generates target code for a sequence of three- address statements and
effectively uses registers to store operands of the statements.
• For example: consider the three-address statement a := b+c It can have the following
sequence of codes:
ADD Rj, Ri Cost = 1
(or)
ADD c, Ri Cost = 2
(or)
MOV c, Rj Cost = 3
ADD Rj, Ri
Register and Address Descriptors:
• A register descriptor is used to keep track of what is currently in each registers. The register
descriptors show that initially all the registers are empty.
• An address descriptor stores the location where the current value of the name can be found at
run time.
A code-generation algorithm:
The algorithm takes as input a sequence of three-address statements constituting a basic block.
For each three-address statement of the form x : = y op z, perform the following actions:
1. Invoke a function getreg to determine the location L where the result of the computation y
op z should be stored.

2. Consult the address descriptor for y to determine y’, the current location of y. Prefer the
register for y’ if the value of y is currently both in memory and a register. If the value of y is
not already in L, generate the instruction MOV y’ , L to place a copy of y in L.

3. Generate the instruction OP z’ , L where z’ is a current location of z. Prefer a register to a

memory location if z is in both. Update the address descriptor of x to indicate that x is in
location L. If x is in L, update its descriptor and remove x from all other descriptors.

Page 15 of 23
4. If the current values of y or z have no next uses, are not live on exit from the block, and are
in registers, alter the register descriptor to indicate that, after execution of x : = y op z , those
registers will no longer contain y or z
Generating Code for Assignment Statements:
• The assignment d : = (a-b) + (a-c) + (a-c) might be translated into the following three-address
code sequence: Code sequence for the example is:

Generating Code for Indexed Assignments

The table shows the code sequences generated for the indexed assignmen a:= b[ i ] and a[ i ]:=b

Generating Code for Pointer Assignments

The table shows the code sequences generated for the pointer assignments a : = *p and *p := a

Page 16 of 23
if x < 0 goto z ADD z, R0
MOV R0,x
CJ< z

4.10 PEEPHOLE OPTIMIZATION

Peephole optimization is a type of Code Optimization performed on a small part of the code. It
is performed on the very small set of instructions in a segment of code.
The small set of instructions or small part of code on which peephole optimization is performed
is known as peephole or window.
It basically works on the theory of replacement in which a part of code is replaced by shorter
and faster code without change in output.
Peephole is the machine dependent optimization.

Objectives of Peephole Optimization:

The objective of peephole optimization is:
1. To improve performance
2. To reduce memory footprint
3. To reduce code size
Peephole Optimization Techniques:
1. Redundant load and store elimination:
In this technique the redundancy is eliminated.
Initial code:
y = x + 5;
i = y;
z = i;
w = z * 3;

Page 17 of 23
Optimized code:
y = x + 5;
i = y;
w = y * 3;
2. Constant folding:
The code that can be simplified by user itself, is simplified.
Initial code:
x = 2 * 3;
Optimized code:
x = 6;
3. Strength Reduction:
The operators that consume higher execution time are replaced by the operators consuming
less execution time.
Initial code:
y = x * 2;
4. Optimized code:
y = x + x; or y = x << 1;
Initial code:
y = x / 2;
Optimized code:
y = x >> 1;
5. Null sequences:
Useless operations are deleted.
6. Combine operations:
Several operations are replaced by a single equivalent operation.

4.11 REGISTER ALLOCATION AND ASSIGNMENT:

Local register allocation
Register allocation is only within a basic block. It follows top-down approach.
Assign registers to the most heavily used variables
• Traverse the block
• Count uses
• Use count as a priority function
• Assign registers to higher priority variables first

Page 18 of 23
Advantage
Heavily used values reside in registers
Disadvantage
Does not consider non-uniform distribution of uses
Need of global register allocation
Local allocation does not take into account that some instructions (e.g. those in loops) execute
more frequently. It forces us to store/load at basic block endpoints since each block has no
knowledge of the context of others.
To find out the live range(s) of each variable and the area(s) where the variable is used/defined
global allocation is needed. Cost of spilling will depend on frequencies and locations of uses.
Register allocation depends on:
Size of live range
Number of uses/definitions
Frequency of execution
Number of loads/stores needed.
Cost of loads/stores needed.
Register allocation by graph coloring
Global register allocation can be seen as a graph coloring problem.
Basic idea:
1. Identify the live range of each variable

2. Build an interference graph that represents conflicts between live ranges (two nodes are
connected if the variables they represent are live at the same moment)

3. Try to assign as many colors to the nodes of the graph as there are registers so that two
neighbors have different colors

Page 19 of 23
Page 20 of 23
4.12 DYNAMIC PROGRAMMING CODE-GENERATION

Introduction: The dynamic programming algorithm proceeds in three phases :

1. Compute bottom-up for each node n of the expression tree T an array C of costs, in
which the zth component C[i] is the optimal cost of computing the subtree S rooted at n
into a register, assuming i registers are available for the computation, for 1 < i < r.

2. Traverse T, using the cost vectors to determine which subtrees of T must be computed
into memory.

3. Traverse each tree using the cost vectors and associated instructions to generate the
final target code. The code for the subtrees computed into memory locations is generated
first.

Each of these phases can be implemented to run in time linearly proportional to the size of the
expression tree.

The cost of computing a node n includes whatever loads and stores are necessary to evaluate S
in the given number of registers. It also includes the cost of computing the operator at the root
of S. The zeroth component of the cost vector is the optimal cost of computing the subtree S
into memory. The contiguous evaluation property ensures that an optimal program for S can
be generated by considering combinations of optimal programs only for the subtrees of the root
of S. This restriction reduces the number of cases that need to be considered.

In order to compute the costs C[i] at node n, we view the instructions as tree-rewriting rules,
as in Section 8.9. Consider each template E that matches the input tree at node n. By examining
the cost vectors at the corresponding descendants of n, determine the costs of evaluating the
operands at the leaves of E. For those operands of E that are registers, consider all possible
orders in which the corresponding subtrees of T can be evaluated into registers. In each
ordering, the first subtree corresponding to a register operand can be evaluated using i available
registers, the second using i -1 registers, and so on. To account for node n, add in the cost of
the instruction associated with the template E. The value C[i] is then the minimum cost over
all possible orders.

Page 21 of 23
The cost vectors for the entire tree T can be computed bottom up in time linearly proportional
to the number of nodes in T. It is convenient to store at each node the instruction used to achieve
the best cost for C[i] for each value of i. The smallest cost in the vector for the root of T gives
the minimum cost of evaluating T.

Example: Consider a machine having two registers RO and Rl, and the following
instructions, each of unit cost:

In these instructions, Ri is either RO or Rl, and Mi is a memory location. The operator op

corresponds to arithmetic operators.
Let us apply the dynamic programming algorithm to generate optimal code for the syntax tree
in Fig 8.26. In the first phase, we compute the cost vectors shown at each node. To illustrate
this cost computation, consider the cost vector at the leaf a. C[0], the cost of computing a into
memory, is 0 since it is already there. C[l], the cost of computing a into a register, is 1 since
we can load it into a register with the instruction LD RO, a. C[2], the cost of loading a into a
register with two registers available, is the same as that with one register available. The cost
vector at leaf a is therefore (0,1,1).

Consider the cost vector at the root. We first determine the minimum cost of computing the
root with one and two registers available. The machine instruction ADD RO, RO, M matches
the root, because the root is labeled with the operator . Using this instruction, the minimum
cost of evaluating the root with one register available is the minimum cost of computing its
right subtree into memory, plus the minimum cost of computing its left subtree into the
register, plus 1 for the instruction. No other way exists. The cost vectors at the right and left

Page 22 of 23
children of the root show that the minimum cost of computing the root with one register
available is 5 2 1 = 8.
Now consider the minimum cost of evaluating the root with two registers available. Three cases
arise depending on which instruction is used to compute the root and in what order the left and
right subtrees of the root are evaluated.

Dynamic programming techniques have been used in a number of compilers, including the
second version of the portable C compiler, PCC2. The technique facilitates retargeting because
of the applicability of the dynamic programming technique to a broad class of machines.

Page 23 of 23
 UNIT – V

Machine-Independent Optimization: The Principal Sources of Optimization, Introduction to

Data-Flow Analysis, Foundations of Data-Flow Analysis, Constant Propagation, Partial-
Redundancy Elimination, Loops in Flow Graphs.

5.1 THE PRINCIPAL SOURCES OF OPTIMIZATION:

• A transformation of a program is called local if it can be performed by looking only at the

statements in a basic block; otherwise, it is called global.

• Many transformations can be performed at both the local and global levels. Local
transformations are usually performed first.
Function-Preserving Transformations
• There are a number of ways in which a compiler can improve a program without
changing the function it computes.

➢ Common sub expression elimination

➢ Copy propagation

➢ Dead-code elimination, and

➢ Constant folding

Common Sub expressions elimination

An occurrence of an expression E is called a common sub-expression if E was previously
computed, and the values of variables in E have not changed since the previous computation.
We can avoid recomputing the expression if we can use the previously computed value.
For example
t1: = 4*i
t2: = a [t1]
t3: = 4*j
t4: = 4*i
t5: = n
t6: = b [t4] +t5

Page 1 of 11
The above code can be optimized using the common sub-expression elimination as
t1: = 4*i
t2: = a [t1]
t3: = 4*j
t5: = n
t6: = b [t1] +t5
The common sub expression t4: =4*i is eliminated as its computation is already in t1. And
value of i is not been changed from definition to use.
Copy Propagation
Assignments of the form f : = g called copy statements, or copies for short. The idea behind the
copy-propagation transformation is to use g for f, whenever possible after the copy statement
f: = g. Copy propagation means use of one variable instead of another. This may not appear to
be an improvement, but as we shall see it gives us an opportunity to eliminate x.
For example:
x=Pi;
……
A=x*r*r;
The optimization using copy propagation can be done as follows:
A=Pi*r*r;
Here the variable x is eliminated
Dead-Code Eliminations:
A variable is live at a point in a program if its value can be used subsequently; otherwise, it is
dead at that point. A related idea is dead or useless code, statements that compute values that
never get used. While the programmer is unlikely to introduce any dead code intentionally, it
may appear as the result of previous transformations. An optimization can be done by
eliminating dead code.
For example:
i=0;
if(i=1)
{
a=b+5;
}
Here, ‘if’ statement is dead code because this condition will never get satisfied.

Page 2 of 11
Constant folding:
We can eliminate both the test and printing from the object code. More generally, deducing at
compile time that the value of an expression is a constant and using the constant instead is
known as constant folding. One advantage of copy propagation is that it often turns the copy
statement into dead code.
For example:
a=3.14157/2 can be replaced by
a=1.570 thereby eliminating a division operation.
Loop Optimizations:
We now give a brief introduction to a very important place for optimizations, namely loops,
especially the inner loops where programs tend to spend the bulk of their time. The running
time of a program may be improved if we decrease the number of instructions in an inner loop,
even if we increase the amount of code outside that loop.
Three techniques are important for loop optimization:
➢ Code motion, which moves code outside a loop;

➢ Induction-variable elimination, which we apply to replace variables from inner loop.

➢ Reduction in strength, which replaces and expensive operation by a cheaper one, such as
a multiplication by an addition.

Code Motion:
An important modification that decreases the amount of code in a loop is code motion. This
transformation takes an expression that yields the same result independent of the number of
times a loop is executed ( a loop-invariant computation) and places the expression before the
loop. Note that the notion “before the loop” assumes the existence of an entry for the loop.
For example:
Evaluation of limit-2 is a loop-invariant computation in the following while-statement:
while (i <= limit-2) /* statement does not change limit*/
Code motion will result in the equivalent of
t= limit-2;
while (i<=t) /* statement does not change limit or t */

Page 3 of 11
Induction Variables :
Loops are usually processed inside out. For example consider the loop around B3. Note that
the values of j and t4 remain in lock-step; every time the value of j decreases by 1, that of t4
decreases by 4 because 4*j is assigned to t4. Such identifiers are called induction variables.

When there are two or more induction variables in a loop, it may be possible to get rid of all
but one, by the process of induction-variable elimination. For the inner loop around B3 in Fig.
we cannot get rid of either j or t4 completely; t4 is used in B3 and j in B4. However, we can
illustrate reduction in strength and illustrate a part of the process of induction-variable
elimination. Eventually j will be eliminated when the outer loop of B2 - B5 is considered.
Example:
As the relationship t4:=4*j surely holds after such an assignment to t4 in Fig. and t4 is
not changed elsewhere in the inner loop around B3, it follows that just after the statement j:=j-
1 the relationship t4:= 4*j-4 must hold. We may therefore replace the assignment t4:= 4*j by
t4:= t4-4. The only problem is that t4 does not have a value when we enter block B3 for the
first time. Since we must maintain the relationship t4=4*j on entry to the block B3, we place
an initializations of t4 at the end of the block where j itself is..

Page 4 of 11
The replacement of a multiplication by a subtraction will speed up the object code if
multiplication takes more time than addition or subtraction, as is the case on many machines.
Reduction In Strength:
Reduction in strength replaces expensive operations by equivalent cheaper ones on the target
machine. Certain machine instructions are considerably cheaper than others and can often be
used as special cases of more expensive operators. For example, x² is invariably cheaper to
implement as x*x than as a call to an exponentiation routine. Fixed-point multiplication or
division by a power of two is cheaper to implement as a shift. Floating-point division by a
constant can be implemented as multiplication by a constant, which may be cheaper.

5.2 INTRODUCTION TO DATA-FLOW ANALYSIS:

In order to do code optimization and a good job of code generation , compiler needs to collect
information about the program as a whole and to distribute this information to each block in
the flow graph. A compiler could take advantage of “reaching definitions” , such as knowing
where a variable like debug was last defined before reaching a given block, in order to perform
transformations are just a few examples of data-flow information that an optimizing compiler
collects by a process known as data-flow analysis. Data-flow information can be collected by
setting up and solving systems of equations of the form :

out [S] = gen [S] U ( in [S] – kill [S] )

This equation can be read as “ the information at the end of a statement is either generated
within the statement , or enters at the beginning and is not killed as control flows through the
statement.”

• The notions of generating and killing depend on the desired information, i.e., on the
data flow analysis problem to be solved. Moreover, for some problems, instead of
proceeding along with flow of control and defining out[s] in terms of in[s], we need
to proceed backwards and define in[s] in terms of out[s].

• Since data flows along control paths, data-flow analysis is affected by the constructs
in a program. In fact, when we write out[s] we implicitly assume that there is unique
end point where control leaves the statement; in general, equations are set up at the
level of basic blocks rather than statements, because blocks do have unique end
points.

Page 5 of 11
• There are subtleties that go along with such statements as procedure calls,
assignments through pointer variables, and even assignments to array variables.

5.3 CONSTANT PROPAGATION

Constants assigned to a variable can be propagated through the flow graph and substituted at
the use of the variable.
Example:
In the code fragment below, the value of x can be propagated to the use of x.
x = 3;
y = x + 4;
Below is the code fragment after constant propagation and constant folding.
x = 3;
y = 7;
Notes:
Some compilers perform constant propagation within basic blocks; some compilers perform
constant propagation in more complex control flow.
Some compilers perform constant propagation for integer constants, but not floating-point
constants.
Few compilers perform constant propagation through bitfield assignments.
Few compilers perform constant propagation for address constants through pointer
assignments.
5.4 LOOPS IN FLOW GRAPHS
A graph representation of three-address statements, called a flow graph, is useful for
understanding code-generation algorithms, even if the graph is not explicitly constructed by a
code-generation algorithm. Nodes in the flow graph represent computations, and the edges
represent the flow of control.
Dominators:
In a flow graph, a node d dominates node n, if every path from initial node of the flow graph
to n goes through d. This will be denoted by d dom n. Every initial node dominates all the
remaining nodes in the flow graph and the entry of a loop dominates all nodes in the loop.
Similarly every node dominates itself.

Page 6 of 11
Example:
❖ In the flow graph below,
❖ Initial node,node1 dominates every node. *node 2 dominates itself
❖ node 3 dominates all but 1 and 2. *node 4 dominates all but 1,2 and 3.
❖ node 5 and 6 dominates only themselves,since flow of control can skip around either by
goin through the other.
❖ node 7 dominates 7,8 ,9 and 10. *node 8 dominates 8,9 and 10.
❖ node 9 and 10 dominates only themselves.

Fig. 5.3(a) Flow graph (b) Dominator tree

The way of presenting dominator information is in a tree, called the dominator tree, in which
• The initial node is the root.
• The parent of each other node is its immediate dominator.
• Each node d dominates only its descendents in the tree.

The existence of dominator tree follows from a property of dominators; each node has a unique
immediate dominator in that is the last dominator of n on any path from the initial node to n.
In terms of the dom relation, the immediate dominator m has the property is d=!n and d dom
n, then d dom m.
D(1)={1}
D(2)={1,2}
D(3)={1,3}
D(4)={1,3,4}
D(5)={1,3,4,5}
Page 7 of 11
D(6)={1,3,4,6}
D(7)={1,3,4,7}
D(8)={1,3,4,7,8}
D(9)={1,3,4,7,8,9}
D(10)={1,3,4,7,8,10}
Natural Loops:
One application of dominator information is in determining the loops of a flow graph suitable
for improvement. There are two essential properties of loops:

❖ A loop must have a single entrypoint, called the header. This entry point-dominates
all nodes in the loop, or it would not be the sole entry to the loop.

❖ There must be at least one way to iterate the loop(i.e.)at least one path back to the
headerOne way to find all the loops in a flow graph is to search for edges in the flow
graph whose heads dominate their tails. If a→b is an edge, b is the head and a is the
tail. These types of

❖ edges are called as back edges.

Example:
In the above graph,
7→4 4 DOM 7
10 →7 7 DOM 10
4→3
8→3
9 →1
The above edges will form loop in flow graph. Given a back edge n → d, we define the natural
loop of the edge to be d plus the set of nodes that can reach n without going through d. Node d
is the header of the loop.
Algorithm: Constructing the natural loop of a back edge.
Input: A flow graph G and a back edge n→d.
Output: The set loop consisting of all nodes in the natural loop n→d.
Method: Beginning with node n, we consider each node m*d that we know is in loop, to make
sure that m’s predecessors are also placed in loop. Each node in loop, except for d, is placed
once

Page 8 of 11
on stack, so its predecessors will be examined. Note that because d is put in the loop initially,
we never examine its predecessors, and thus find only those nodes that reach n without going
through d.
Procedure insert(m):
if m is not in loop then begin loop := loop U {m};
push m onto stack end;
stack : = empty;
loop : = {d}; insert(n);
while stack is not empty do begin
pop m, the first element of stack, off stack;
for each predecessor p of m do insert(p)
end
Inner loops:
If we use the natural loops as “the loops”, then we have the useful property that unless two
loops have the same header, they are either disjointed or one is entirely contained in the
other. Thus, neglecting loops with the same header for the moment, we have a natural notion
of inner loop: one that contains no other loop.

When two natural loops have the same header, but neither is nested within the other, they are
combined and treated as a single loop.
Pre-Headers:
Several transformations require us to move statements “before the header”. Therefore begin
treatment of a loop L by creating a new block, called the preheader. The pre-header has only
the header as successor, and all edges which formerly entered the header of L from outside L
instead enter the pre-header. Edges from inside loop L to the header are not changed. Initially
the pre-header is empty, but transformations on L may place statements in it.

Page 9 of 11
 Fig. 5.4 Two loops with the same header

Fig. 5.5 Introduction of the preheader

Reducible flow graphs:

Reducible flow graphs are special flow graphs, for which several code optimization
transformations are especially easy to perform, loops are unambiguously defined, dominators
can be easily calculated, data flow analysis problems can also be solved efficiently. Exclusive
use of structured flow-of-control statements such as if-then-else, while-do, continue, and break
statements produces programs whose flow graphs are always reducible.

The most important properties of reducible flow graphs are that

1. There are no umps into the middle of loops from outside;
2. The only entry to a loop is through its header

Definition:
A flow graph G is reducible if and only if we can partition the edges into two disjoint groups,
forward edges and back edges, with the following properties.

Page 10 of 11
1. The forward edges from an acyclic graph in which every node can be reached from initial
node of G.
2. The back edges consist only of edges where heads dominate theirs tails.

Example:

The above flow graph is reducible. If we know the relation DOM for a flow graph, we can find
and remove all the back edges. The remaining edges are forward edges. If the forward edges
form an acyclic graph, then we can say the flow graph reducible. In the above example remove
the five back edges 4→3, 7→4, 8→3, 9→1 and 10→7 whose heads dominate their tails, the
remaining graph is acyclic.

Page 11 of 11