Compiler Design (CD)
GTU # 3170701
Unit – 1
Overview of the
Compiler
&
it’s Structure
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
What do you see?
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
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.
હેલ્લો
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)
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
Interpreter
Interpreter is also program that reads a program written in source language and translates it
into an equivalent program in target languageline 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
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
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
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
Phases of compiler
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
Lexical analysis
Lexical Analysis is also called linear analysis or scanning.
Lexical Analyzer divides the given source statement into Position = initial + rate*60
the 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)
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
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 *
If code is error free then syntax analyzer generates the 60
tree.
Syntax analysis
id1 +
id2 *
id3 60
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
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
60
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
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 60
instruction, each of which has at most three operands. Intermediate code
t1= int to real(60)
t2= id3 * t1
t3= t2 + id2
id1= t3
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
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
Phases of compiler
Compiler
Analysis phase Synthesis phase
Lexical analysis
Intermediate Code
code optimization
Syntax analysis generation
Code
Semantic analysis generation
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
Id3R2
Id2R1
Phases of compiler
Source
program
Analysis
Lexical analysis Phase
Syntax analysis
Semantic
analysis Error
Symbol
table detection
Intermediate
and recovery
code
Variable Type Address Code
Name optimization
Position Float 0001
Code Synthesis
Initial Float 0005 generation Phase
Rate Float 0009 Target
Program
Exercise
Write output of all the phases of compiler for following statements:
1. x = b-c*2
2. I=p*n*r/100
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
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 An error is displayed for every instruction
is checked. interpreted if any.
Memory requirement is more. Memory requirement is less.
Example: C compiler Example: Basic, Python, Ruby
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 Preprocessor
machine code.
Source
These system programs are:
Program
Compiler
Preprocessor Target Assembly
Assembler Program
Linker Assembler
Loader Relocatable Object
Code
Libraries & Linker / Loader
Object Files
Absolute Machine
Code
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: Source
#define PI 3.14159265358979323846 Program
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 Absolute Machine
Code
routines that perform the database access.
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
equivalent program in target language. Program
Compiler
Target Assembly
Program
Assembler
Relocatable Object
Code
Libraries & Linker / Loader
Object Files
Absolute Machine
Code
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 Source
the machine code as an output. Program
Compiler
Target Assembly
Program
Assembler
Relocatable Object
Code
Libraries & Linker / Loader
Object Files
Absolute Machine
Code
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
These files may have been the result of several Program
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
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
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.
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.
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.
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.
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.
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
Thank You