Compiler Design (CD)

GTU # 3170701

Unit – 1
Overview of the Compiler
&
it’s Structure

Prof. Dixita B. Kagathara

Computer Engineering Department
Darshan Institute of Engineering & Technology, Rajkot
dixita.kagathara@darshan.ac.in
+91 - 97277 47317 (CE Department)
 Topics to be covered
 Looping
• Language Processor
• Translator
• Analysis synthesis model of compilation
• Phases of compiler
• Grouping of the Phases
• Difference between compiler & interpreter
• Context of compiler (Cousins of compiler)
• Pass structure
• Types of compiler
• The Science of building a compiler
What do you see?
10101001 00000000 10101001 00000000
10101001 00000000 10101001 00000000
10000101 0000000 110101001 00000000 Binary
10101001 00000010 10101001 00000010 program
10000101 00000010 10101001 00000010
10100000 00000000 10101001 00000010
10101001 0000000 110101001 00000010 What does it
10010001 00000001 10000101 00000000 mean????

10000101 00000001 10101001 00000010

10101001 00000010 10101001 00000010
10101001 00000010 10101001 00000010

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 3
What do you see?

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 4
Semantic gap

10101001 00000000 10101001 00000000

10101001 00000000 10101001 00000000
10000101 0000000 110101001 00000000
10101001 00000010 10101001 00000010
Semantic
10000101 00000010 10101001 00000010 Low level Gap High level
10100000 00000000 10101001 00000010
10101001 0000000 110101001 00000010
10010001 00000001 10000101 00000000

Actual Data Human perception

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 5
Language processor
 Language processor is a software which bridges semantic gap.
 A language processor is a software program designed or used to perform tasks such as
processing program code to machine code. 

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 6
 હે લ્લો

Translator
Translator
 A translator is a program that takes one form of program as input and converts it into another
form.
 Types of translators are:
1. Compiler
2. Interpreter
3. Assembler

Source Translator Target

Program Program

Error
Messages (If any)
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 8
Compiler
 A compiler is a program that reads a program written in source language and translates it into
an equivalent program in target language.

void main() 0000 1100 0010

{ 0100
Source
int a=1,b=2,c; 0111 1000 0001
Target
Compiler
c=a+b; Program 1111 0101 1110
Program
printf(“%d”,c); 1100 0000 1000
} 1011

Source Error Target

Program Messages (If any) Program

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 9
Interpreter
 Interpreter is also program that reads a program written in source language and translates it
into an equivalent program in target language line by line.

Void main() 0000 1100 0010

{ 0000
int a=1,b=2,c; Interpreter 1111 1100 0010
c=a+b;
1010 1100 0010
printf(“%d”,c);
0011 1100 0010
} 1111
Error
Source Target
Messages (If any)
Program Program

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 10
Assembler
 Assembler is a translator which takes the assembly code as an input and generates the
machine code as an output.

MOV id3, R1 0000 1100 0010

MUL #2.0, R1 0100
MOV id2, R2 0111 1000 0001
MUL R2, R1 Assembler 1111 0101 1110
MOV id1, R2 1100 0000 1000
ADD R2, R1 1011
MOV R1, id1 1100 0000 1000
Error
Assembly Code Messages (If any) Machine Code

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 11
Analysis Synthesis model of
compilation
Analysis synthesis model of compilation
 There are two parts of compilation.

1. Analysis Phase
2. Synthesis Phase

void main() Analysis Synthesis

{ Phase Phase 0000 1100
int a=1,b=2,c; 0111 1000
c=a+b; 0001
printf(“%d”,c); Intermediate 1111 0101
} Representation 1000
1011
Source Code Target Code

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 13
Analysis phase & Synthesis phase
Analysis Phase Synthesis Phase
 Analysis part breaks up the source  The synthesis part constructs the desired
program into constituent pieces and target program from the intermediate
creates an intermediate representation of representation.
the source program.
 Synthesis phase consist of the following sub
 Analysis phase consists of three sub phases:
phases:
1. Code optimization
1. Lexical analysis
2. Code generation
2. Syntax analysis
3. Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 14
Phases of compiler
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 16
Lexical analysis
 Lexical Analysis is also called linear analysis or scanning.
 Lexical Analyzer divides the given source statement into the Position = initial + rate*60
tokens.
 Ex: Position = initial + rate * 60 would be grouped into the
Lexical analysis
following tokens:
Position (identifier) id1 = id2 + id3 * 60
= (Assignment symbol)
initial (identifier)
+ (Plus symbol)
rate (identifier)
* (Multiplication symbol)
60 (Number)

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 17
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 18
Syntax analysis
 Syntax Analysis is also called Parsing or Hierarchical Position = initial + rate*60
Analysis.
 The syntax analyzer checks each line of the code and Lexical analysis
spots every tiny mistake.
id1 = id2 + id3 * 60
 If code is error free then syntax analyzer generates the
tree.
Syntax analysis

id1 +

id2 *
id3 60

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 19
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 20
Semantic analysis
 Semantic analyzer determines the meaning of a source =
string.
id1 +
 It performs following operations:
1. matching of parenthesis in the expression. id2 * int to
real
2. Matching of if..else statement. id3 60
3. Performing arithmetic operation that are type
compatible. Semantic analysis
4. Checking the scope of operation. =
*Note: Consider id1, id2 and id3 are real
id1 +

id2 *
id3 inttoreal

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

60
Prof. Dixita B Kagathara 21
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 22
Intermediate code generator
 Two important properties of intermediate code : =
1. It should be easy to produce.
id1 +
2. Easy to translate into target program.
id2 *
 Intermediate form can be represented using “three
address code”. t3 id3 inttoreal
t2 t1
 Three address code consist of a sequence of instruction, 60
each of which has at most three operands. Intermediate code

t1= int to real(60)

t2= id3 * t1
t3= t2 + id2
id1= t3

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 23
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 24
Code optimization
 It improves the intermediate code.
 This is necessary to have a faster execution of code Intermediate code
or less consumption of memory.
t1= int to real(60)
t2= id3 * t1
t3= t2 + id2
id1= t3

Code optimization

t1= id3 * 60.0

id1 = id2 + t1

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 25
Phases of compiler

Compiler

Analysis phase Synthesis phase

Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation

Code generation
Semantic analysis

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 26
Code generation
 The intermediate code instructions are translated into
sequence of machine instruction. Code optimization

t1= id3 * 60.0

id1 = id2 + t1

Code generation

MOV id3, R2
MUL #60.0, R2
MOV id2, R1
ADD R2,R1
MOV R1, id1

Id3R2
Id2R1
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 27
Phases of compiler
Source program

Analysis Phase
Lexical analysis

Syntax analysis

Semantic analysis
Symbol table Error detection
and recovery
Intermediate code

Variable Type Address Code optimization

Name
Position Float 0001 Code generation Synthesis Phase
Initial Float 0005
Target Program
Rate Float 0009
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 28
Exercise
 Write output of all the phases of compiler for following statements:
1. x = b-c*2
2. I=p*n*r/100

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 29
Grouping of Phases
Front end & back end (Grouping of phases)
Front end
 Depends primarily on source language and largely independent of the target machine.
 It includes following phases:
1. Lexical analysis
2. Syntax analysis
3. Semantic analysis
4. Intermediate code generation
5. Creation of symbol table & Error handling
Back end
 Depends on target machine and do not depends on source program.
 It includes following phases:
1. Code optimization
2. Code generation phase
3. Error handling and symbol table operation
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 31
Difference between compiler & interpreter

Compiler Interpreter
Scans the entire program and translates it It translates program’s one statement at a
as a whole into machine code. time.
It generates intermediate code. It does not generate intermediate code.
An error is displayed after entire program is An error is displayed for every instruction
checked. interpreted if any.
Memory requirement is more. Memory requirement is less.
Example: C compiler  Example: Basic, Python, Ruby 

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 32
Context of Compiler
(Cousins of compiler)
Context of compiler (Cousins of compiler)
Skeletal Source Program
 In addition to compiler, many other system programs
are required to generate absolute machine code. Preprocessor
 These system programs are:
Source Program

Compiler
 Preprocessor
 Assembler Target Assembly
Program
 Linker
Assembler
 Loader
Relocatable Object
Code
Libraries & Linker / Loader
Object Files

Absolute Machine
Code
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 34
Context of compiler (Cousins of compiler)
Skeletal Source Program
Preprocessor
 Some of the task performed by preprocessor: Preprocessor

1. Macro processing: Allows user to define macros. Ex: #define Source Program
PI 3.14159265358979323846
Compiler
2. File inclusion: A preprocessor may include the header file
into the program. Ex: #include<stdio.h> Target Assembly
3. Rational preprocessor: It provides built in macro for Program
construct like while statement or if statement. Assembler
4. Language extensions: Add capabilities to the language by Relocatable Object
using built-in macros. Code
 Ex: the language equal is a database query language Libraries & Linker / Loader
Object Files
embedded in C. Statement beginning with ## are taken by
preprocessor to be database access statement unrelated
to C and translated into procedure call on routines that Absolute Machine
Code
perform the database access.
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 35
Context of compiler (Cousins of compiler)
Skeletal Source Program
Compiler
 A compiler is a program that reads a program Preprocessor

written in source language and translates it into an Source Program

equivalent program in target language.
Compiler

Target Assembly
Program
Assembler

Relocatable Object
Code
Libraries & Linker / Loader
Object Files

Absolute Machine
Code
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 36
Context of compiler (Cousins of compiler)
Skeletal Source Program
Assembler
 Assembler is a translator which takes the assembly Preprocessor

program (mnemonic) as an input and generates the Source Program

machine code as an output.
Compiler

Target Assembly
Program
Assembler

Relocatable Object
Code
Libraries & Linker / Loader
Object Files

Absolute Machine
Code
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 37
Context of compiler (Cousins of compiler)
Skeletal Source Program
Linker
 Linker makes a single program from a several files Preprocessor

of relocatable machine code. Source Program

 These files may have been the result of several
Compiler
different compilation, and one or more library files.
Target Assembly
Loader Program
Assembler
 The process of loading consists of:
 Taking relocatable machine code Relocatable Object
Code
 Altering the relocatable address Libraries & Linker / Loader
 Placing the altered instructions and data in Object Files
memory at the proper location.
Absolute Machine
Code
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita B Kagathara 38
Pass structure
Pass structure
 One complete scan of a source program is called pass.
 Pass includes reading an input file and writing to the output file.
 In a single pass compiler analysis of source statement is immediately followed by synthesis of
equivalent target statement.
 While in a two pass compiler intermediate code is generated between analysis and synthesis
phase.
 It is difficult to compile the source program into single pass due to: forward reference

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 40
Pass structure
Forward reference: A forward reference of a program entity is a reference to the entity which
precedes its definition in the program.
 This problem can be solved by postponing the generation of target code until more information
concerning the entity becomes available.
 It leads to multi pass model of compilation.

Pass I:

 Perform analysis of the source program and note relevant information.

Pass II:

 In Pass II: Generate target code using information noted in pass I.

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 41
Effect of reducing the number of passes
 It is desirable to have a few passes, because it takes time to read and write intermediate file.
 If we group several phases into one pass then memory requirement may be large.

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita B Kagathara 42
Types of compiler
Types of compiler
1. One pass compiler
 It is a type of compiler that compiles whole process in one-pass.
2. Two pass compiler
 It is a type of compiler that compiles whole process in two-pass.
 It generates intermediate code.
3. Incremental compiler
 The compiler which compiles only the changed line from the source code and update the object
code.
4. Native code compiler
 The compiler used to compile a source code for a same type of platform only.
5. Cross compiler
 The compiler used to compile a source code for a different kinds platform.

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 44
Science of building Compilers
Science of building Compilers
 The main job of compiler is to accept the source program and convert it into suitable target
program.
 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.
 Compiler study mainly focused on study of how to design the correct mathematical model and
choose correct algorithm.
 In compiler design, term “Code Optimization” indicates the attempts made by a compiler to
produce a code which is more efficient then a previous code.
 The code should be faster than any other code that performs the same task.
 The objectives to be fulfilled by the compiler optimization include:
1. The meaning of the compiled program must be preserved.
2. Optimization should improve programs performance.
3. Time required for compilation should be reasonable.
#3170701 (CD)  Unit 1– Overview of the Compiler & it’s
Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 46
Science of building Compilers
 Just theory is not sufficient to build a compiler, People involved in the design of compiler
should be able to formulate the right problem to solve.
 In, order to do this the first step in through understanding of the behavior of programs.

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 47
References
Books:
1. Compilers Principles, Techniques and Tools, PEARSON Education (Second Edition)
Authors: Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman
2. Compiler Design, PEARSON (for Gujarat Technological University)
Authors: Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman

#3170701 (CD)  Unit 1– Overview of the Compiler & it’s

Prof. Dixita
Jay R Dhamsaniya
B Kagathara #3130006 (PS)  Unit 1 – Basic Probability 48
Thank You