1
Compiler Design
BCSE307L
Introduction to Compiler 2
Language Translator
User writes a program in high-level language.
The compiler, compiles the program and translates it to assembly program (low-
level language).
An assembler then translates the assembly program into machine code (Binary).
A linker tool is used to link all the parts of the program together for execution
(executable machine code).
A loader loads all of them into memory and then the program is executed.
3
Phases and Passes
• Pass : A pass refers to the traversal of a compiler through the entire program.
• Phase : A phase of a compiler is a distinguishable stage, which takes input from
the previous stage, processes and yields output that can be used as input for the
next stage. A pass can have more than one phase.
Phases of Compiler (Analysis + Synthesis) 4
Source
Program
Analysis Phase Lexical Analyzer
Tokens or
Lexemes
Symbol Syntax Analyzer Error
Table Handler
Abstract Parse
Tree
Semantic Analyzer
Attributed Parse
tree
Phases of Compiler (Analysis + Synthesis) 5
Attributed Parse
tree
Synthesis Phase Intermediate Code
Generator
Three address
Code
Symbol Error
Table Code Optimizer Handler
Optimal Code or
DAG
Object Code
Generator
Target Machine
Interpreters 6
An Interpreter is a special program that takes a single statement written in a Language
(Source Language) and then convert into machine language.
- Less memory .
- Execution of conditional control statements are slower.
- Debugging is easier in an interpreter
Phases of a compiler 7
The compiler process is complex, so it is divided into six sub processes (Phases)
Lexical analyzer 8
Lexical analyzer reads the source program character by character at a time.
Unites them into a stream.
Token (Lexeme) is a group of character which represents keywords, operators and
identifiers.
It makes entries of each identifier into the symbol table.
It is also known as Lexer, Tokenizer or Scanner.
Lexical analyzer 9
C = A * B + 75
Lexical Analyzer or Tokenizer or
Lexer
C Identifier
= Assignment Operator
A Identifier
+ Add Operator
B Identifier
* Multiplication Operator
75 Constant
10
11
Consider the following program and find the
number of tokens:
int main()
{
int a, b;
a = 10;
return 0;
}
12
13
14
Syntax analyzer 15
It is the second and important phase of a compiler.
It receives the tokens from the output of a lexical analyzer as an input .
It checks the tokens are valid or not based on the specified grammar of source
language.
It generates a parse tree according to the given grammar to the source
language.
Syntax analyzer C Identifier
= Assignment Operator 16
A Identifier
* Multiplication Operator
B Identifier
S + Add Operator
75 Constant
C = T
3
id T
+ T Syntax Analyzer or Parser
1 2
* 75 Parse Tree
A B
id id
17
Semantic analyzer 18
The parse tree is generated by a syntax analyzer and passed as an input to the
semantic analyzer.
It computes the additional information related to the recognized tokens, such as
operator, operand, expression or statement, and inserts that information into the
symbol table.
During the semantic analysis, the type of identifier is checked .
If required, the semantic analyzer will perform an implicit type conversion.
Semantic S
Float
19
analyzer Float Float
S
C = T
3
Syntax directed Tree
or ????
Attributed Syntax id Float T + T
C = T
3 Tree 1 2
Float
id T
+ T Float *
Float 75
2 A B
1
* 75 id id
A B
Semantic Analyzer or Type Checker
id id Parse Tree
Intermediate Code generator 20
It takes Syntax Directed Tree is an input produced by a semantic analyzer and
produces an intermediate code.
The intermediate code thus generated has mainly two properties:
- It should be easy to produce.
- Easy to translate into target program.
One of the forms is Three Address Code.
Intermediate code generator 21
Syntax directed Tree
Float or
S Attributed Syntax
Tree
Float Intermediate Code Generator
Float
C = T
3
Three Address Code
id Float T + T
1 2
Float T1 = A * B
Float *Float 75
A B T3 = T1 + 75
C = T3
id id
Code optimization 22
This phase is to reduce the size of the code and improve the performance of the
code generated by an intermediate code phase.
- Minimize the amount of time taken by the code to execute.
- Minimize the amount of memory used by the code.
T1 = A * B
Code Optimization
T1 = A * B
T3 = T1 + 75 C = T1 + 75
Three Address Code Optimized Code
C = T3
Target Code 23
The target code is the final phase of the compiler which normally converts the input
obtained from the code optimization phase into low level language code or machine
code or assembly code.
MOV R1, A
MOV R2, B
T1 = A * B
Target Code MUL R1,
C = T1 + 75
R2
Optimized Code Object Code
ADD R1, 75
STORE C, R1
24
25
Thank you….