CS406-Compiler Construction
Lecture 1: Introduction
Waheed Noor
Computer Science and Information Technology,
University of Balochistan,
Quetta, Pakistan
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 1 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 2 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 3 / 26
Compiler Construction 3(3-0)
Objective
This course begins with basic understandings of overall structure of a
compiler, and then digs into the details of a number of important
techniques commonly used in compiler construction. Students will also
learn major techniques that are used to translate code from high-level
language to machine language.
In this Course:
You will learn how the compiler works.
Learn about compiler structure & types, lexical analyzer, syntax
analyzer, semantic analyzer and other major components in
compiler construction.
Assignments after each unit. (Late assignments will not be
accepted.)
Plagiarism is an academic offense, zero marks will be given if
found in your assignments.
Random Quiz any day any time during class.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 4 / 26
Books & Materials
Compilers: Principles, Techniques, and Tools, A. V. Aho, R. Sethi
and J. D. Ullman, 2nd Edition, Addison-Wesley, 2006.
Modern Compiler Design, Dick Grune, Henri E. Bal, Ceriel J. H.
Jacobs and Koen G. Langendoen, John Wiley, 2000.
The Art of Compiler Design: Theory and Practice, T. Pittman, J.
Peters and J. Peters, Prentice Hall, 1991.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 5 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 6 / 26
The Compiler
Definition
It is a program that reads a program written in one language (the
source language) and translates it in an equivalent program in another
language (the target language). Compiler also needs to report any
error to the users in the source program occurred during translation.
Source Program Target Program
Error Messages
Figure : A Compiler
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 7 / 26
The Compiler
The Source Language Program
There are thousands of programming languages that are source to
compilers ranging from classical Fortran, C, to modern languages such
as Java, C#.
Target Program
The target program that is the output of a compiler can also be in a
variety of form such as another programming language, relocatable
object program, assembly language and machine language of a
microprocessor.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 8 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 9 / 26
History of Compilers
Not exactly known date but early 1950s is assumed to be start of
appearance of compilers.
Mainly used for translating arithmetic formulas into machine
language.
In 1957, first FORTRAN compiler launched that is considered to
be started in 1954.
Since, then systematic techniques have been discovered for
handling many of the important tasks occurring during
compilation.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 10 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 11 / 26
Analysis Part
There are two basic parts of compilation, analysis and synthesis.
Definition
The analysis part breaks up the source program into constituent pieces
and creates an intermediate representation of the source program.
During analysis, the operations implied by the source program are
determined and recorded in a hierarchical structure called a tree, a
special kind of tree called a syntax tree is used, In which each node
represents an operation and the children of a node represent the
arguments of the operation.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 12 / 26
Synthesis Part
Definition
The synthesis part constructs the desired target program from the
intermediate representation.
This part synthesis the target program depending on the goal of the
compilation. For example, a compiler may first generate and
intermediate code after analysis, and then generate the target code
that can be assembly language code or machine code.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 13 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 14 / 26
What else Compilers can Do! I
Compilers can be used for following purposes in which case the
analysis part will remain same.
Text Formatters: A text formatter takes input a stream of characters,
most of which is text to be typeset, but some of which includes
commands to indicate paragraphs, figures. or mathematical
structures/equations. E.g., TEXand LATEX.
Silicon Compilers: A silicon compiler has a source language that is
similar or identical to a conventional programming language. However,
the variables of the language represent, not locations in memory, but,
logical signals (0 or 1) or groups of signals in a switching circuit. The
output is a circuit design in an appropriate language. E.g., Queens
University Interactive Silicon Compiler (QUISC).
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 15 / 26
What else Compilers can Do! II
Query Interpreters: A query interpreter translates a predicate
containing relational and boolean operators into commands to search
a database for records satisfying that predicate. E.g., SQL interpreters
for different DBMS.
Readings & Homework
You should read about software programs called Mathematica and
Matlab and discuss the input and output of their compilers.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 16 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 17 / 26
The Goals of Compilers
To develop the compiler as small as possible.
To create a compiler that possesses the better ability of diagnosis
and recovery from failures.
To produce the compiler that will compile flexible and efficient
object programs.
1 The time spent by the compiler to translate the source program is
the least, i.e., translation efficiency.
2 The object program which the compiler generates is most efficient,
i.e., time efficiency.
3 The size of the object program which the compiler generates
should be smaller, i.e., space efficiency.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 18 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 19 / 26
Many Programming Languages
Needs are different
Scientific Computing
Business Applications
System Programming
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 20 / 26
Qualities of Good Programming Languages
No universally accepted metric for language design, following may be
considered when designing a programming language
Well-defined Syntactic and semantic description
Determinism of program structure
Fast translation
Reliability
Machine Independent
Generality
Extensibility
Consistency
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 21 / 26
Outline
1 Course Description
2 What is a Compiler
3 Historical Overview
4 Analysis-Synthesis Model of Compilation
5 Other Uses of Compilers
6 Goals of Compilers
7 Economy of Programming Languages
8 The Context of a Compiler
References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 22 / 26
The Context of a Compiler
In addition to a compiler, we may need several other programs to
generate an executable target program:
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 23 / 26
The Context of Compilers
Preprocessor
The source program may divided into different modules stored into
different files, then it is the task of the program called preprocessor to
collect the source program. The macros are also incorporated into the
source program by the preprocess.
Assembler
Assembler translates the generated assembly language code
generated by the compiler into the machine code.
Loader and Link Editor
Loader loads the relocatable machine codes into machine memory by
altering the addresses to appropriate memory locations. While the link
editor link allow us to use relocatable machine code stored in different
files by linking them into a single program. They are useful for different
libraries written for different purposes.
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 24 / 26
Phases of a Compiler
Typically a compiler consist of phases shown bellow in the Figure.
Figure : Phases of a Compiler
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 25 / 26
References I
*References
Waheed Noor (CS&IT, UoB, Quetta) CS406-Compiler Construction November 2013 26 / 26
