Compiler Design

Lecture 01

Md. Hashibur Rahman Kwoshik

Lecturer
Dept. of CSE, BAUET

Reference Books

1. Compilers – Principles, Techniques, & Tools (2nd Edition ), Alfred V. Aho, Monica S. Lam, Ravi Sethi,
Jeffrey D. Ullman
2. Engineering a Compiler (2nd Edition), Keith D. Cooper & Lindra Torczon

2
What is a Compiler?
A compiler is program that reads a program written in one language
(source language) and translates it into an equivalent program in
another language (target language)

source program Compiler target program

error messages

If the target program is an executable machine-language program, it

can then be called by the user to process inputs and produce outputs

input Target Program output

4
Interpreter
An interpreter is another common kind of language processor. Instead
of producing a target program as a translation, an interpreter appears
to directly execute the operations specified in the source program on
inputs supplied by the user.

source program
Interpreter output
input

Hybrid Compiler
Java language processors combine compilation and interpretation. A
Java source program may first be compiled into an intermediate form
called bytecodes. The bytecodes are then interpreted by a virtual
machine. A benefit of this arrangement is that bytecodes compiled on
one machine can be interpreted on another machine, perhaps across a
network.
some Java compilers translate the bytecodes into machine language
immediately before they run the intermediate program to process the
input called just-in-time compilers.

6
Hybrid Compiler
source program

Translator

intermediate
program Virtual
output
Machine
input

A Language Processing System

source program

Preprocessor
modified source program

Compiler
target assembly program

Assembler
relocatable machine code

Linker/Loader Library files

Relocatable object files

target machine code

8
The Structure of a Compiler
▪Analysis
▪ ▪ Front end
Using a grammatical structure to create

▪ an intermediate representation
Collecting information about the source
program in a symbol table

The Structure of a Compiler

▪Synthesis
▪▪ Back end
Constructing the target program from the
intermediate representation and the
symbol table

10
Phases of a Compiler

Symbol Table

11

Lexical Analysis (Scanning)

1st phase of Compiler, also known as Scanner. It verifies that input character
sequence is lexically valid. Group characters into meaningful sequence of
lexemes. For each lexeme, the lexical analyzer produces as output a token of the
form:
(token-name, attribute-value)

E.g.
◦ position = initial + rate * 60
◦ <id,1> <=> <id,2> <+> <id,3> <*> <60>

12
Lexical Analysis...
◦ Example
position = initial + rate * 60

➢ Lexemes mapped into Tokens

Position (id,1)
= (=)
initial (id,2)
+ (+)
rate (id,3)
* (*)
60 (60)

After lexical analysis (id,1) (=) (id,2) (+) (id,3) (*) (60)

13

Translation of (Ex) Assignment Statement

14
Syntax Analysis (Parsing)
Creating a tree-like (e.g. syntax tree) intermediate representation that depicts the
grammatical structure of the token streams
◦ E.g.
◦ <id,1> <=> <id,2> <+> <id,3> <*> <60>

<id, 1> +

<id, 2> *

<id, 3> 60

15

Semantic Analysis
Type checking
Type conversions or coercions
E.g.
◦ =

<id, 1> +

<id, 2> *

<id, 3> int2float

60

16
Intermediate Code Generation
Generating a low-level intermediate representation
◦ It should be easy to produce
◦ It should be easy to translate into the target machine
◦ E.g. three-address code
t1 = int2float(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

17

Code Optimization
Attempts to improve the intermediate code
◦ Better: faster, shorter code, or code that consumes less power (Chap. 8 -)
◦ E.g.
◦ t1 = id3 * 60.0
id1 = id2 + t1

18
Code Generation
Mapping intermediate representation of the source program into the target
language (Chap. 8)
◦ Machine code: register/memory location assignments
◦ E.g.
◦ LDF R2, id3
MULF R2, R2, #60.0
LDF R1, id2
ADDF R1, R1, R2
STF id1, R1

19

Symbol Table Management

To record the variable names and collect information about various attributes of
each name
◦ Storage, type, scope
◦ Number and types of arguments, method of argument passing, and the type
returned

20
Grouping of Phases into Passes
Front-end pass
◦ Lexical analysis, syntax analysis, semantic analysis, intermediate code
generation
(Optional) Code optimization pass
Back-end pass
◦ Code generation

21

Compiler Construction Tools

The compiler programmer can use modern software development
environments containing tools such as language editors, debuggers, version
managers , and so on including some specialized tools.

The most successful tools are those that hide the details of the generation
algorithm and produce components that can be easily integrated into the
remainder of the compiler.

22
Compiler Construction Tools..
Some common tools are:

1. Parser generators automatically produce syntax analyzers from a

grammatical description of a programming language.

2. Scanner generators produce lexical analyzers from a regular-

expression description of the tokens of a language.

3. Syntax-directed translation engines produce collections of routines

for walking a parse tree and generating intermediate code.

23

Compiler Construction Tools...

4. Code-generators produce a code from a collection of rules for translating each
operation of the intermediate language into the machine language for a target
machine.

5. Data-flow analysis engines facilitate the gathering of information about how

values are transmitted from one part of a program to each other part.

6. Compiler- construction toolkits provide an integrated set of routines for

constructing various phases of a compiler.

24
Thank You