Compiler Construction
CS-4207
Instructor Name: Atif Ishaq
Lecture 1 & 2
Today’s Lecture
Introduction (Course Objective)
Language Processor
Structure of Compiler
Phases of Compiler
2
Introduction
Course Objective
The course is intended to teach the students the basic techniques that underlie the
practice of Compiler Construction.
The course will introduce the theory and tools that can be standarly employed in
order to perform syntax-directed translation of a high-level programming
language into an executable code.
3
Introduction
Recommended Books
The Recommended book for this course
Compilers – Principles, Techniques and Tools by Aho, Sethi and Ullman
Other Material
Slides + handout [if required]
4
Introduction
Marks Distribution
Mid Exam 20% (Min 2 Assignments)
Quiz 10% (Min. 2 Quiz)
Assignment & Class participation 10% (0 marks < 75%)
Final Examination 60% (MCQ, Logical,Theory)
5
Introduction
What is Compiler?
Programming Languages are notation for describing computation for both human
and machines
All software are written in some programming language
A Program first needs to be translated into a form in which it can be executed by
computer
The Software System that does this translation is called Compilers
6
Language Processors
What is 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)
An important role of compiler is to report any errors in source program that it
detects during the translation process. 7
Language Processors
What is Interpreter?
An interpreter directly execute the operations specified in the source program on
inputs specified by the user
Source Code
Interpreter Outputs
Inputs
An Interpreter does not generates any target program.
8
Language Processors
Compiler Vs Interpreter
Target Program generated by compiler is much faster that Interpreter
Error Diagnostics of Interpreter is better than compiler due to statement by
statement execution
9
Why Study Compiler Construction?
Many applications use components of compilers, e.g. analysis and translation.
The study of compilers clarifies many deep issues in programming languages and
their execution, e.g. recursion, multithreading, object orientation. It may help you
design your own mini-language.
Underlying compilers construction are many Computer Science seminal concepts
such as syntax vs. Semantics, Generator vs. Recognizer and Syntax Directed
Translation.
Understanding a compiler and its Optimization mechanisms enable us to write
more efficient programs
For example
10
Why Study Compiler Construction?
Maximal Expressibility and Maximal Efficiency
Compiler plays an important role to bridge between maximal expressibility and
maximal efficiency. The current trend
Development of more expressive (and user-friendly) high level programming
languages
Development of more advanced (and parallel) architectures that enable more
efficient execution
The compiler should be able to reconcile these two (sometimes conflicting) trends.
11
Why Study Compiler Construction?
Fields and Disciplines
There are different fields and disciplines that grew out of studies of compilers
Semantics of programming languages
Formal Languages and theory of parsing.
Type theory and its logics
Theory of abstract interpretation and program analysis
12
Structure of Compiler
A Compiler is mapped into two parts : analysis and synthesis
The analysis part breaks up the source program into constituent pieces and
impose a grammatical structure on them. The analysis part also collects
information about the source program and stores it in a data structure called
symbol table which is passed along with intermediate representation to the
synthesis part.
The synthesis part constructs the desired target program from the
intermediate representation and the information in the symbol table.
The analysis part is often called the front end of the compiler and the
synthesis part called the back end of compiler.
13
Context of a Compiler
A Compiler is often applied as a stage within a sequence of transformations
14
Phases of a Compiler
15
Analysis of Source Program
Analysis can be partitioned into three phases
Linear (Lexical) Analysis : Stream of characters is read left-to-right
and partitioned into tokens
Hierarchical (Syntax) Analysis Tokens are grouped hierarchically
into nested collections
Semantic Analysis : Checking global consistency. Often does not
comply with hierarchical structure. Type Checking is an instance
of such analysis.
16
Example Illustration (1/4)
Suppose a source program contains the assignment statement
position = initial + rate * 60
• position is a lexeme that would be mapped into token (id,1), where id is
abstract symbol standing for identifier and 1 stands for symbol table
entry for position
• the assignment symbol is lexeme that is mapped into token (=)
• initial is lexeme that is mapped into token (id,2)
• + is lexeme that is mapped into the token (+)
• rate is the lexeme that is mapped into token(id,3)
• * is lexeme that is mapped into the token (*)
17
• 60 is lexeme that is mapped into the token (60)
Lexical Analysis
The first phase of a Compiler is Lexical Analysis or scanning
Reads streams of characters and groups the characters into
meaningful sequence called lexemes
For each lexeme produces as output a token of the form
(token-name , attribute-value)
token-name is abstract symbol used during syntax analysis
attribute-value points to an entry in the symbol table.
Token is passed to subsequent phase , syntax analysis
18
Example Illustration (2/4)
19
Example Illustration (3/4)
20
Example Illustration (4/4)
21
Syntax Analysis
The second phase of a Compiler is Syntax Analysis or parsing
Use first component of tokens to create a tree like intermediate
representation – represents the grammatical structure of the token
stream
syntax tree is typical representation – interior node represents an
operation ( * ) - children of the node represents the arguments of
the operation (id3 and 60 )
22
Semantic Analysis
The semantic analyzer uses syntax tree and information in symbol
table to check the source program for semantic consistency with
the language definition
Gather type information and save it either in syntax tree or symbol
table for further use in intermediate code generation.
An important part of Semantic Analysis – type checking - each
operator has matching operand (Example of Index of Array)
Some languages permits type Conversion – called coercions. For
example evaluation of arithmetic expression
intofloat(60) in above example converts integer into float 23
Intermediate Code Generation
Many compilers generate an explicit low level or machine-like
intermediate representation
The intermediate representation should have two important
properties
i. It should be easy to produce
ii. It should be easy to translate into target machine
Example of intermediate form is three-address code, which
consists of sequence of assembly like instructions with three
operands per instruction
24
Code Optimization
Improve the intermediate code to have better target code
Faster means better
Other objectives may be desired like shorter code or target code
that consumes less power
Code may be optimized by eliminating repetitive operation and
instruction like intofloat() and temp3 variable in out case
25
Code Generation
Code generation maps intermediate representation of source
program to target program
First operand specifies the destination
F specifies that operation is performed on floating value
26
Symbol Table Management
Symbol table record variable name and collects information about
various attributes
In case of function, it records number and type of argument, call
type and returned value
A symbol table data structure is very significant as it must allow
compiler to perform operations quickly
27
Lecture Outcome
Difference between Compiler and Interpreter
The reasons to study compiler construction
Structure of Compiler (Analysis & Synthesis) – Two Pass
Compiler
Phases of Compiler with brief overview
Phases of Compiler with program example
28
29
