COMPILER DESIGN (KCS-502)

COMPILER DESIGN (KCS-502)

 INTRODUCTION TO COMPILER
Compiler is a program that can read a program in one
language “SOURCE language” and translate it into an
equivalent program in another language “TARGET
language”

SOURCE TARGET
LANGUAGE COMPILER LANGUAGE

ERROR
MESSAGE
 INTRODUCTION TO INTERPRETER
Interpreter is another common kind of language
processor. It reads the program in one language “SOURCE
program” as input and interpret line by line and produce
a “TARGET program”

SOURCE TARGET
PROGRAM INTERPRETER PROGRAM
LANGUAGE PROCESSING SYSTEM

Source program

PREPROCESSOR
Modified source
program

COMPILER
Target
assembly
language
ASSEMBLER
Relocatable
machine
code
Library files
Linker/Loader relocatable
object files
Target machine
code
 DIFFERENCE BETWEEN
COMPILER AND INTERPRETER
 PHASES OF COMPILER (Cont…)

Analysis of the Source

Program

Synthesis of the Object

Program
PHASES OF COMPILER
 CATEGORIES OF COMPILERS
1. Native Compiler :
Native compiler are compilers that generates code for the
same Platform on which it runs. It converts high language into
computer’s native language. For example Turbo C or GCC
compiler

2. Cross compiler :
A Cross compiler is a compiler that generates executable code
for a platform other than one on which the compiler is
running. For example a compiler that running on Linux/x86
box is building a program which will run on a separate
Arduino/ARM.
 CATEGORIES OF COMPILERS
Difference between Native and Cross Compiler

NATIVE COMPILER CROSS COMPILER

Translates program for same Translates program for different

hardware/platform/machine on it is hardware/platform/machine other than
running. the platform which it is running.

It is dependent on System/machine It is independent of System/machine

and OS and OS

It can generate executable file like It can generate raw code .hex
.exe
TurboC or GCC is native Compiler. Keil is a cross compiler.
 PASSES
The number of iteration in which the entire phases
of compiler are done are termed as PASS. It has two
categories:
•Single pass compiler (Pascal)
•Two Pass/Multi pass compiler (Java)
•Pass1 also known as : Front End, Analytic Part, Platform
Independent
•Pass2 also known as : Back End, Synthesis Part, Platform
Dependent
 SINGLE-PASS COMPILER
In a Single (One) pass compiler the entire
phases performs its function in a single pass.
Advantage:-
•It takes less time to execute.
Disadvantage:-
•In this we go in a sequence and can’t go back to
handle the error.
•In this more space is occupied.
 TWO/MULTI-PASS COMPILER
A Two pass/multi-pass Compiler is a type
of compiler that processes the source
code or abstract syntax tree of a program
multiple times. In multipass Compiler we
divide phases in two pass as:
Advantage:-
•It occupies less memory space.
•Errors can be removed in every pass to make
error free.

Disadvantage:-
•It takes more time to convert source code
into target code.
 TWO/MULTI-PASS COMPILER
It helps to solve two main problem:
1.If we want to design compiler for different programming
language for same machine.
 TWO/MULTI-PASS COMPILER
It helps to solve two main problem:
2. If we want to design compiler of same
programming language for different machines.
 DIFFERENCE B/W SINGLE AND
MULTIPASS
PARAMETER SINGLE PASS MULTIPASS

SPEED FAST SLOW

MEMORY MORE LESS

TIME LESS MORE

PORTABILITY NO YES
 BOOTSTRAPPING
Bootstrapping is widely used in the compilation development.
• It is used to produce a self-hosting compiler.
•Self-hosting compiler is a type of compiler that can compile its own source
code.
•It is used to compile the compiler and then you can use this compiled
compiler to compile everything else as well as future versions of itself.
For bootstrapping purpose, a compiler is characterized by three
languages:
•Source language S that compiler compiles
•Target language T that it generate codes
•The Implementation language I the compiler is written
Notation: represents a compiler for Source S, Target T,
implemented in I. The T-diagram shown above is also used to
depict the same compiler.
BOOTSTRAPPING
 FINITE AUTOMATON
An automaton with a finite number of states is called a Finite
Automaton (FA) or Finite State Machine (FSM).
An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where
−
Q is a finite set of states.
∑ is a finite set of symbols, called the alphabet of the automaton.
δ is the transition function.
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q.
 FINITE AUTOMATA
(cont….)
Related Terminologies

• Alphabet
Definition − An alphabet is any finite set of symbols.
Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and ‘d’ are symbols.

• String
Definition − A string is a finite sequence of symbols taken from ∑.
Example − ‘cabcad’ is a valid string on the alphabet set ∑ = {a, b, c, d}

• Length of a String
Definition − It is the number of symbols present in a string. (Denoted by |S|).
Examples −
If S = ‘cabcad’, |S|= 6
If |S|= 0, it is called an empty string (Denoted by λ or ε)
 FINITE AUTOMATA
(cont….)
Related Terminologies

• Kleene Star
Definition − The Kleene star, ∑*, is a unary operator on a set of symbols or strings, ∑, that gives the
infinite set of all possible strings of all possible lengths over ∑ including λ.
Representation − ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. where ∑p is the set of all possible strings of length p.
Example − If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..}

• Kleene Closure / Plus

Definition − The set ∑+ is the infinite set of all possible strings of all possible lengths over ∑ excluding λ.
Representation − ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪…….
∑+ = ∑* − { λ }
Example − If ∑ = { a, b } , ∑+ = { a, b, aa, ab, ba, bb,………..}

• Language
Definition − A language is a subset of ∑* for some alphabet ∑. It can be finite or infinite.
Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, bb, ba, bb}
 FINITE AUTOMATA
(cont….)
Finite Automaton can be classified into two types −
•Deterministic Finite Automaton (DFA)
•Non-deterministic Finite Automaton (NDFA / NFA)

Deterministic Finite Automaton (DFA)

In DFA, for each input symbol, one can determine the state to which the machine
will move. Hence, it is called Deterministic Automaton. As it has a finite number of
states, the machine is called Deterministic Finite Machine or Deterministic Finite
Automaton.
Formal Definition of a DFA
A DFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −
Q is a finite set of states.
∑ is a finite set of symbols called the alphabet.
δ is the transition function where δ: Q × ∑ → Q
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
 FINITE AUTOMATA
(cont….)
Example
Let a deterministic finite automaton be →
Q = {a, b, c},
∑ = {0, 1},
q0 = {a},
F = {c}, and
Transition function δ as shown by the following table −
 FINITE AUTOMATA
(cont….)
Non-Deterministic Finite Automaton (NDFA/NFA)
In NDFA, for a particular input symbol, the machine can move to any combination
of the states in the machine. In other words, the exact state to which the machine
moves cannot be determined. Hence, it is called Non-deterministic Automaton. As
it has finite number of states, the machine is called Non-deterministic Finite
Machine or Non-deterministic Finite Automaton.

Formal Definition of an NDFA

An NDFA can be represented by a 5-tuple (Q, ∑, δ, q0, F) where −

Q is a finite set of states.
∑ is a finite set of symbols called the alphabets.
δ is the transition function where δ: Q × ∑ → 2Q
(Here the power set of Q (2Q) has been taken because in case of NDFA, from a
state, transition can occur to any combination of Q states)
q0 is the initial state from where any input is processed (q0 ∈ Q).
F is a set of final state/states of Q (F ⊆ Q).
 FINITE AUTOMATA
(cont….)
Example
Let a non-deterministic finite automaton be →
Q = {a, b, c}
∑ = {0, 1}
q0 = {a}
F = {c}
The transition function δ as shown below −
 REGULAR EXPRESSION
Regular expression is an important notation for specifying patterns. Each pattern
matches a set of strings, so regular expressions serve as names for a set of strings.
Programming language tokens can be described by regular languages.

A Regular Expression can be recursively defined as follows −

• ε is a Regular Expression indicates the language containing an empty string. (L (ε)

= {ε})
. φ is a Regular Expression denoting an empty language. (L (φ) = { })
. x is a Regular Expression where L = {x}

If X is a Regular Expression denoting the language L(X) and Y is a Regular

Expression denoting the language L(Y), then
. X + Y is a Regular Expression corresponding to the language L(X) ∪ L(Y) where L(X+Y) =
L(X) ∪ L(Y).
. X . Y is a Regular Expression corresponding to the language L(X) . L(Y) where L(X.Y) =
L(X) . L(Y)
. R* is a Regular Expression corresponding to the language L(R*)where L(R*) = (L(R))*
REGULAR EXPRESSION
RE TO NFA CONVERSION
 GRAMMAR
Grammars are used to describe the syntax of a programming
language. It specifies the structure of expression and statements.
Definition
A context free grammar G is defined by four tuples as,
G=(V,T,P,S)
where,
G - Grammar
V - Set of variables
T - Set of Terminals
P - Set of productions
S - Start symbol
Terminals are represented by small letters
Variables are represented by capital letters
 GRAMMAR
According to Chomsky hierarchy, grammars are divided of 4 types:
 TYPE of Grammar
• Type 0: Unrestricted Grammar:
Type-0 grammars include all formal grammars. Type 0
grammar language are recognized by turing machine.
These languages are also known as the Recursively
Enumerable languages.
• Grammar Production in the form of:
 TYPE of Grammar
• Type 1: (Context Sensitive Grammar)
Type-1 grammars generate the context-sensitive languages. The
language generated by the grammar are recognized by the Linear
Bound Automata.
• In Type 1
I. First of all Type 1 grammar should be Type 0.
II. Grammar Production in the form of
 TYPE of Grammar
• Type 2: Context Free Grammar:

Type-2 grammars generate the context-free languages. The language

generated by the grammar is recognized by a Pushdown automata.
Type-2 grammars generate the context-free languages.

In Type 2

1. First of all it should be Type 1.

2. Left hand side of production can have only one variable.
 TYPE of Grammar
• Type 3: Regular Grammar:
Type-3 grammars generate regular languages. These
languages are exactly all languages that can be accepted by a
finite state automaton.
• Type 3 is most restricted form of grammar.

• Type 3 should be in the given form only :

TYPE of Grammar
 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.
 DERIVATION (Cont…)
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.
 DERIVATION Example
Example The left-most derivation The right-most derivation
is: is:
Production rules: E→E+E E→E-E
E→E-E+E E→E-E+E
E→E+E E → id - E + E E → E - E + id
E → id - id + E E → E - id + id
E→E-E E → id - id + id E → id - id + id

E → id

Input string:
Id - id + id
 AMBIGUITY

A grammar G is said to ambiguous if it has more than one

parse tree (Left or Right derivation)

The left-most derivation The right-most derivation

is: is:
E→E+E E→E-E
E→E-E+E E→E-E+E
Example E → id - E + E E → E - E + id
E → id - id + E E → E - id + id
Production rules:
E → id - id + id E → id - id + id
E→E+E
E→E-E
E → id

Input string:
Id - id + id
 LEX and YACC
LEX generates C code for a lexical analyzer, or scanner.
It uses patterns that match strings in the input and converts the
strings to tokens.
Tokens are numerical representations of strings, and simplify
processing.

YACC (Yet Another Compiler Compiler) generates C code for a

syntax analyzer, or parser.
Yacc uses grammar rules that allow it to analyze tokens from lex
and create a syntax tree.
A syntax tree imposes a hierarchical structure on tokens.
LEX and YACC
 LEX and YACC
Input to Lex is divided into three sections, with %% dividing the
sections.

Optional

Pattern Action Code

RE

Optional
 LEX and YACC
Input to YACC is divided into three sections, with %% dividing the
sections.

Optional

Production Action Code

Rule CFG

Optional
 LEX and YACC
To run :

% lex bas.l
% cc lex.yy.c –ll
% a.out
-------
------
-------
%
 COMPILER CONSTRUCTION TOOLS…….
•Scanner Generator:- These automatically generate lexical analyzers
normally from a specification based on regular expression.
•Parser Generator:- These produce syntax analyzer, normally from I/P
that is based on a context free grammar.
•Syntax-directed translation engines:- These produce
collection of routines that walk the parse tree.
•Code-generator generators:- Such a tool takes a collection of
rules that defines the translation of each operation of the intermediate language
into the machine language for the target machine.
•Dataflow analysis engines:- Much of the information needed to
perform good code optimization involves “data flow analysis”. The gathering of
information about how values are transmitted from one part of a program to
other part.
Q1. Generate the Token and Parse tree for the following:

If (MAX==5) GOTO 100

Q2. Generate the Token and Parse tree for the following:

While A>B do
A=A+B
Q3. Generate the Token and Parse tree for the following:

While A>=B & A=2*5 do

A=A*B