Baze University

Compilers
Mubaraka Sani Ibrahim

January 12, 2019

1 / ??
Overview

2 / ??
Evaluation

■ Mid Term 30%

■ Exam 70%
■ Attendance is required

3 / ??
Books

■ A. Aho, R. Sethi and J. Ullman, Compilers: Principles,

Techniques and Tools (The Dragon Book), Addison Wesley

4 / ??
Today’s Objectives

■ Understand programming languages

■ What language processors do
■ Understand theory behind compiler
■ Understand theory behind interpreter

5 / ??
Introduction

6 / ??
Introduction To Programming Language

■ Computers are fast at performing tasks

7 / ??
Introduction To Programming Language

■ Computers are fast at performing tasks

■ How do we control the computer?

7 / ??
Introduction To Programming Language

■ Computers are fast at performing tasks

■ How do we control the computer?
■ A program tells the computer what to do

7 / ??
Introduction To Programming Language

■ Computers are fast at performing tasks

■ How do we control the computer?
■ A program tells the computer what to do
■ Program, software and application will be used
interchangeably in this course.

7 / ??
Introduction To Programming Language

■ Computers are fast at performing tasks

■ How do we control the computer?
■ A program tells the computer what to do
■ Program, software and application will be used
interchangeably in this course.

7 / ??
Natural Language

■ Natural Language is:

8 / ??
Natural Language

■ Natural Language is:

◆ Powerful
◆ Expressive
◆ But ambiguous(same statement different meanings)

8 / ??
Why High Level Language

■ Natural language is concise

■ Natural language is precise

9 / ??
Why High Level Language

■ Natural language is concise

■ Natural language is precise
■ But unambiguous

9 / ??
Machine language

■ CPU understands machine language or code

10 / ??
Machine language

■ CPU understands machine language or code

■ Number of binary digits(0, or 1)

10 / ??
Machine language

■ CPU understands machine language or code

■ Number of binary digits(0, or 1)
■ Complex

10 / ??
Assembly Language

■ Machine language is hard to program

11 / ??
Assembly Language

■ Machine language is hard to program

■ Each instruction is identified by symbolic names(rather than
bits) and variables are identified by names rather than
number

11 / ??
Assembly Language

■ Machine language is hard to program

■ Each instruction is identified by symbolic names(rather than
bits) and variables are identified by names rather than
number
■ Program called assembler is used to translate op-codes and
operands into machine instruction

11 / ??
Assembly Language

■ Machine language is hard to program

■ Each instruction is identified by symbolic names(rather than
bits) and variables are identified by names rather than
number
■ Program called assembler is used to translate op-codes and
operands into machine instruction
■ Direct translation of machine instruction

11 / ??
Machine Instructions

12 / ??
Properties Of High Level Language

■ Programming language instructs computers

■ High level of abstraction to low level implementation details
■ Portable

13 / ??
High level of abstraction to low level implementation
details

Figure 2: Korea University

14 / ??
High Level Language Portability

15 / ??
How to instruct a computer

■ Program written in high level language

■ Compiler translates to a target program
■ Processor executes the target program

16 / ??
Why Study Compiler

■ Compiler allows programming at a high level instead of

machine instructions
■ Compiler performs error detection

17 / ??
How Compiler Works

18 / ??
Examples Of Compiled Languages

■ C, C++, Java, Lisp

19 / ??
Examples Of Compiled Languages

■ C, C++, Java, Lisp

◆ Source code translated into target program

19 / ??
Examples Of Both Interpreted and Compiled
Languages

■ Python, Java, C,

20 / ??
Examples Of Both Interpreted and Compiled
Languages

■ Python, Java, C,
◆ Source code translated into target program

20 / ??
Examples Of Both Interpreted and Compiled
Languages

■ Python, Java, C,
◆ Source code translated into target program
■ Target program could be intermediate form (byte
code)

20 / ??
Examples Of Both Interpreted and Compiled
Languages

■ Python, Java, C,
◆ Source code translated into target program
■ Target program could be intermediate form (byte
code)
◆ The bytecode is interpreted by virtual machine

20 / ??
Example of input and output to a compiler

21 / ??
Input to a compiler

■ Standard high level language

◆ Variables
◆ Constants
◆ Control Statements
◆ Procedure

22 / ??
Output of a compiler

■ Register file
■ Machine code:
◆ Load/Store Instructions

23 / ??
Output of a compiler

■ Register file
■ Machine code:
◆ Load/Store Instructions
◆ Arithmetic and logical operations on registers

23 / ??
Output of a compiler

■ Register file
■ Machine code:
◆ Load/Store Instructions
◆ Arithmetic and logical operations on registers
◆ Branch Instructions

23 / ??
Interpreter

■ Takes source program as input

24 / ??
Interpreter

■ Takes source program as input

■ Executes statement line by line

24 / ??
Interpreter

■ Takes source program as input

■ Executes statement line by line
■ Better error diagnostic

24 / ??
Interpreter

■ Takes source program as input

■ Executes statement line by line
■ Better error diagnostic
■ Speed

24 / ??
How Interpreter Works

25 / ??
Structure Of Compiler

26 / ??
Objective

■ Understand general structure of the compiler

◆ Understand lexical analysis
◆ Understand syntax analysis
◆ Understand semantic analysis
◆ Understand IC generator
◆ Understand code optimization
◆ Understand code generator

27 / ??
Compiler Architecture

28 / ??
Compiler

■ Compilation process involves two parts:

29 / ??
Compiler

■ Compilation process involves two parts:

◆ Analysis

29 / ??
Compiler

■ Compilation process involves two parts:

◆ Analysis
◆ Synthesis

29 / ??
Lexical Analysis

■ Also scanner
■ Reads characters as input

30 / ??
Lexical Analysis

■ Also scanner
■ Reads characters as input
■ Recognise words(group characters into tokens)
■ Info about token is stored in Symbol Table

30 / ??
Lexical Analysis

■ Example:
◆ Ist his ase nte nce

31 / ??
Lexical Analysis

■ Example:
◆ Ist his ase nte nce
◆ Is this a sentence

31 / ??
Scanner

32 / ??
Syntax Analysis

■ Also Parser
■ Uses tokens to create a tree-like structure
■ Determines the grammatical structure of each token
■ Output syntax tree

33 / ??
Parser

34 / ??
Semantic Analysis

■ Handles error check using syntax tree and symbolic table

■ Handles type checking
■ Handles type conversion(operands with int and float)

35 / ??
Semantic Analyser

36 / ??
Analysis

37 / ??
Intermediate Code Generation

■ Translating source program into target code

■ Compiler constructs one or more machine-like intermediate
representation.
■ Intermediate representation is easy to translate into target
code.

38 / ??
Example

■ Using the output of semantic analyser

■ id1 = id2 + id3 * 60
■ Each operand acts as a register
t1 = int to float(60)
t2 = id3 * 60
t3 = id2 + t2
id1 = t3
■ Compiler constructs one or more machine-like intermediate
representation.
■ Intermediate representation is easy to translate into target
code.

39 / ??
Intermediate Code Generation

■ Translating source program into target code

■ Compiler constructs one or more machine-like intermediate
representation.
■ Intermediate representation is easy to translate into target
code.

40 / ??
Code Optimization

■ Improves intermediate code to get better target code

■ Result in efficient code
Example
t1 = id3 * 60.0
id1 = id2 + t1

41 / ??
Code Generation

■ Input as intermediste representation

■ Generates target code
■ Register are used to represent variables
■ Intermediate instructions translated to machine instructions
LDF R2 , id3
MULT R2, R2 , #60.0
LDF R1 , id2
ADDF R1, R1 , R2
STF id1 R1

42 / ??
Synthesis

43 / ??
Issues

■ Language design
■ Debugging
■ Feedback
■ Speed

44 / ??
Automata Theory

45 / ??
Automata Theory

■ Automata theory deals with logic of computation with

respect to simple machines automata
■ Four families of automaton:
1. Finite -state machines
2. Pushdown automata
3. Linear-bounded automata
4. Turing Machine

46 / ??
Automata Theory

■ Automata theory deals with logic of computation with

respect to simple machines automata
■ Automatons are abstract models of machines that perform
computation on an input through a series of state.
■ Computation reaches an output
1. Accept
2. Reject

47 / ??
Example 1

48 / ??
Example 2

0 1
1
0,1
start 0111
0
0
1

49 / ??
Example 2

0 111 1
1
0,1
start 0111
0
0
1

■ The machine M1 accepts a string if the process ends in a

final state

50 / ??
Example 1

51 / ??
Definitions

■ An Alphabet Σ is a set of finite symbols. Examples of

symbols are letters and digits. (in example 2: Σ = 0,1)
■ A string is a sequence of elements of Σ. (example 011)
■ A language is a countable set of symbols over Σ. A set of
strings consisting of sequences of symbols in Σ.

52 / ??
Definitions

■ If Σ is an Alphabet
■ Σ∗ is a set of all alphabets over Σ
■ A language L over Σ is a subsubset of Σ∗ .

53 / ??
Definitions

In Example 1:
Σ = {P ush}
Σ∗ = { λ,
Push,
Push Push,
Push Push Push,
Push Push Push Push...}
L= {P ushn |n is odd }

54 / ??
55 / ??
Deterministic Finite Automata(DFA)

56 / ??
57 / ??
58 / ??
Definitions

A finite automaton is a five-tuple

M = (Q,Σ, δ, q0 ,F)
Q is the set of states
Σ is the alphabet
δ is the transition function
δ: Q × Σ → Q
q0 ∈ Q is the start state
F ⊆ Q is the set final state
L(M) = language of the machine i.e the set of strings
accepted by the machine

59 / ??
Example 1

0
0

start 1

1 0

■ Input 11000 accepted

■ Input 110001 rejected

60 / ??
Example 2

0 0 0
1
start q1 q2 q3
0 1

■ Question: What kind of bit strings are accepted?

61 / ??
Example 2

0 0 0
1
start q1 q2 q3
0 1

■ Question: What kind of bit strings are accepted?

■ Answer: L(M) = {w|w has odd number of 1s }

61 / ??
Example 3

0 0
1

start q1 q2

■ Input: 0
■ Input: 01
■ Input: 011

62 / ??
Example 3

0 1 0

start q1 q2

■ Question: What kind of bit strings are accepted?

63 / ??
Example 3

1
0 0

start q1 q2

■ Question: What kind of bit strings are accepted?

■ Answer: Even number of 1’s

63 / ??
Exercise 3

0 0 0,1
1
q q0 0 q00 1 q000
start
0

■ Question: What kind of bit strings are accepted?

64 / ??
Exercise 3

0 0 0,1
1
q q0 0 q00 1 q000
start
0

■ Question: What kind of bit strings are accepted?

■ Answer: Accepts string that contain 001

64 / ??
Regular Expression RE

65 / ??
Regular Expression

■ Regular expression specifies pattern for a finite string of

symbols for languages
■ Uses notations to specify pattern
■ If r is a regular expression that denotes the language L(r)

Operation Notation Language

Alternation r1 +r2 L(r1 )UL(r2 )
Concatenation r1 • r2 L(r1 ) • L(r2 )
Kleen−∗ r∗ L(r∗ )
Kleen−+ r+ L(r+ )
Exponentiation rn L(rn )

66 / ??
Regular Expression

A regular expression is built up using rules:

Empty set ∅ : A regular expression formed by empty set.
Lambda λ: A regular expression formed by empty string.
Symbol a: A regular expression formed by the symbol a.
Alternation M|N : A regular expression formed by M or N
Concatenation M˙N : A regular expression formed by M followed
by N
Repetition M ∗ : A regular expression formed by zero or more
repetition of M

67 / ??
Regular Expression

Example

If the alphabet Σ is {a,b}

■ a + b RE denotes the set {a}U{b}
■ a∗ RE denotes the set {a}∗ = {λ,a,aa,aaa...}
a•b∗ RE denotes the set {a}•b∗
i.e {a,ab,abb,abbb...}

68 / ??
Regular Expression

Operator precedence from left to right * • +

Parenthesis can be omitted.
For example RE (((a∗ )+b)) can be written as a∗ +b

69 / ??
Non Deterministic Finite Automata(NFA)

70 / ??
71 / ??
Non Deterministic Finite Automata (NFA)

72 / ??
Exercise

■ a∗
a

start q0

73 / ??
Non Deterministic Finite Automata (NFA)

■ (aU b)∗
a

start q0

74 / ??
Non Deterministic Finite Automata (NFA)

■ Write an NFA for the language (aU b)∗ bb over Σ { a,b }

a

q0 b q1 b q2
start

75 / ??
Non Deterministic Finite Automata (NFA)

■ Write the language is accepted by this NFA?

a a

q0 b q1 b q2
start

b b

76 / ??
Non Deterministic Finite Automata (NFA)

■ λ denotes empty string

■ NFA has empty transition rules

λ
q1 q2

77 / ??
Non Deterministic Finite Automata (NFA)

■ λ denotes empty string

start q1
a
b

q2 λ q3

a,b
a

78 / ??
Lex

79 / ??
Scanner

80 / ??
Lexical analyser

■ The parser implements a call (getNextToken) that causes the

lexical analyser to read characters from its input to identify
and return the next lexeme to the parser.
■ Lexical analyser removes comments and white space
(newline,tab,blank space).
■ Lexical analysers match up the errors found by the compiler
with the source program.

81 / ??
How to write a scanner(lexical analyser)

■ The construction of a scanner is done automatically by a tool

such as Lex
■ Lex is a Unix program
■ A source program is used to write a lex program and stored
in a file named lex.l.
■ The unix program lex compiles lex.l to generate the C
program called [Link].c
■ Compiling and linking the [Link].c file generates the scanner.
■ Lexical analyser takes a stream of input characters and
produce a stream of tokens.

82 / ??
Lex

In addition to compilers and interpreters, Lex can be used for:

(1) PCC(Portable C Compiler) used with many Unix systems.
(2) GCC(GNU C Compiler) used with many Unix systems.
(3) Menu compiler
(4) SQL database language syntax checker.

83 / ??
Structure of Lex program

A lex program consist of three parts:

declarations part
%%
translation rules
%%
auxillary functions
The declarations part include variables, constants and statements

84 / ??
Structure of Lex program

The translation rules are of the form:

pattern1 { action1 }
pattern2 { action2 }
pattern3 { action3 }
pattern4 { action4 }
.
.
.
patternn { actionn }

85 / ??
Structure of Lex program

where each patterni is a regular expression and each actioni is a

code fragment that describes the action lexical analyser will
when the lexemes match any pattern. For example patterni
could be an if statement and the corresponding actioni could be
{ return(IF) }

86 / ??
Example 1

Write a lex program for the tokens of the grammar.

Verb → is | am | was | do | does | has | have

87 / ??
Example 2

88 / ??
Lexical Analyser

■ Lexical analyser reads it’s input one character at a time and

finds the longest prefix that matches the pattern.
■ InstallID() is used to place lexemes in the symbol table.
■ InstallNum() is used to place numbers in the table.
■ Lexical analyser returns token names to the parser.
■ yylval variable is used to pass additional information about
the token.

89 / ??
How to write & compile a Lex program

■ Use a word processor to write lex program and save it under

a file name with a .l extension for example myfirstlex.l
■ Use a Unix lex command to compile the program which will
generate the C program under the name [Link]
lex file name
% lex myfirstlex.l
% cc [Link].c -o first -II

90 / ??
Token

What is token?
Smallest meaningful sequence of characters in programming
language.
Programming language keywords, operators, character literals,
string literals, numerical literals and punctuation symbols are
examples of tokens.

91 / ??
Token

Example of tokens are:

■ Operators +, -, %, * etc
■ if, else, while, int, double
■ Identifiers such as initial in initial + rate * 60
■ Numerical literals such as 4, 3.142, 3.76e10
■ Character literals ’a’ ’z’
■ String literals ”str”, ”boy”
■ Punctuation symbols such as semicolon, comma, colon etc

92 / ??
Token

Example of non-tokens are:

■ White space space( ) tab (\ t) end-of-line(\ n)
■ Comments /*this is not a token*/

93 / ??
Tokens

■ Attribute for Tokens?

An attribute is a pointer to the Symbol table containing
additional information about the token
An attribute is written as:
<token, attribute>

94 / ??
Tokens

For example: Consider the statement position = initial + rate *

60
It’s attribute can be written as:
<id1, pointer to the entry table for position>
<id2, pointer to the entry table for initial>
<id3, pointer to the entry table for rate>
<addition operation, >
<multiplication operation, >
<number, real value for 60.0>

95 / ??
How a scanner recognises tokens

1. Use regular expression E to build Deterministic finite

automaton (DFA)
2. Use DFA to to determine if a string belongs to the language
L(E)
3. DFA is constructed using a tool such as lex

96 / ??
Regular Expressions

A regular expression is built up using rules:

Empty set ∅ : A regular expression formed by empty set.
Lambda λ: A regular expression formed by empty string.
Symbol a: A regular expression formed by the symbol a.
Alternation M|N : A regular expression formed by M or N
Concatenation M˙N : A regular expression formed by M followed
by N
Repetition M : A regular expression formed by zero or more
repetition of M

97 / ??
Regular Expressions

Operator precedence: () * ˙ |

Language: The language defined by a regular expression r will be

denoted by L(r)
Regular expressions allows the definition of tokens of
programming language.

98 / ??
Regular Definitions

Notations:
1. The + symbol denotes one or more instance
2. The ? symbol denotes zero or one instance
3. The [ ] symbol denotes character classes

99 / ??
Regular Expression Notation

■ Notation example:

100 / ??
Regular Expression For Some Tokens

101 / ??
Building Finite Automata For lexical Tokens

if {return IF;}

102 / ??
Building Finite Automata For lexical Tokens

103 / ??
Building Finite Automata For lexical Tokens

104 / ??
Building Finite Automata For lexical Tokens

105 / ??
Syntax Analysis

106 / ??
Definitions

syntax: the way in which words are put together to form phrases,
clauses, or sentences. The rules governing the formation of
statements in a programming language.
syntax analysis: the task concerned with fitting a sequence of
tokens into a specified syntax.
parsing: To break a sentence down into its component parts of
speech with an explanation of the form, function, and syntactical
relationship of each part.

107 / ??
Parse tree

Parse tree(derivation tree) is a graphical representation of a

derivation sequence of a sentential form.
Tree nodes represent symbols of the grammar (nonterminals or
terminals) and tree edges represent derivation steps.

108 / ??
Syntax Analysis

109 / ??
Grammar

110 / ??
Definition of Context Free Grammar

A context-free Grammar (G) is a defined as

G = { T, V, P, S } where
■ T:Set of terminals. (scanner tokens)Small letters are used for
terminals(e.g a,b,c,...)
■ V:Set of [Link] set of variables or non
terminals generated by production rules. Capital letters are
used for non terminals(e.g A,B,C,S...)
■
■ S: Start symbol
S∈N

111 / ??
Grammar

■ P: Finite set of production rules/substitution rules.

Rules:
α→β
α ∈ (V U T )+
β ∈ (V U T )∗
■ Grammar (G) defines a language L(G) which is a set of string
T ∗ (Σ∗ ) that G can generate from S.
■ A sequence of substitution to obtain a string is called
derivation
■ Rules for the same left-hand side variable like S→0S and S→
A can be written as S|0S|A

112 / ??
Grammar

■ Given a Grammar (G) = G = { V, T, P, S }

Given a string w = axb
Given the production rule x → t
We can have a string c = atb
In general:
If w1 → w2 → w3
then w1 →+ w3
If w1 → w2 → w3 →...wn
then w1 →∗ wn

113 / ??
Grammar

A Grammar (G) = G = { V, T, P, S } called

left linear Grammar if every derivation is of the form:
A → xB, or A → x
where A,B ∈ V and x ∈ T ∗
Example: Given the production rules:
x → x0 | y1
y → x0 | z1
z → x0 | z1| λ

114 / ??
Grammar

A Grammar (G) = G = { V, T, P, S } called

right linear Grammar if every derivation is of the form:
A → Bx, or A → x
where A,B ∈ V and x ∈ T ∗
Example: Given the production rules:
x → 0x | 1y
y → 0x | 1z
z → 0x | 1z | λ

115 / ??
Regular Grammar

A Grammar (G) = G = { V, T, P, S } called

Regular Grammar if it is either left-linear or right-linear.

116 / ??
Context-free Grammar

A Grammar (G) is a defined as

G = { V, T, P, S } where
V: Finite set of variables or non terminals.
P: Finite set of production rules/substitution rules.
Rules:
α→β
α ∈ (V U T )+
β ∈ (V U T )∗
S: Start symbol

117 / ??
Grammar

■ Given a Grammar (G) = G = { V, T, P, S }

118 / ??
Example

Can you make Context-free Grammar for the following language:

(i) { 0n 1n :n≥0 }

119 / ??
Example

Can you make Context-free Grammar for the following language:

(i) { 0n 1n :n≥0 }
S→0S1| λ

119 / ??
Example

Can you make Context-free Grammar for the following language:

(ii) Arithmetic formula like a+b ×c

120 / ??
Example

Can you make Context-free Grammar for the following language:

(ii) Arithmetic formula like a+b ×c
S→ a | b | c | S+S | S× S

120 / ??
Example

Consider the language:

L(G) = {an bm an | n ≥ 0 and m ≥ 0 }

121 / ??
Example

Consider the language:

L(G) = {an bm an | n ≥ 0 and m ≥ 0 }
CFG to G is:
S → aSa | B
B → bB | λ

121 / ??
Parsing

■ Parsing determines the meaning of program

■ Given a CFG G and a string w, a parse tree is one
representation used to determine if a string belongs to the
language L(G).
■ A parse tree is a pictorial representation of string derivation
■ Nodes of tree represents terminals and non-terminals
while the tree edges represent the derivation process.

122 / ??
Parser

■ Parser is a program that determines the derivation of a

string by constructing a derivation or parse tree.
■ Top down parsers determines a string by constructing a
derivation tree from the root to the leaves.
■ Bottom up parsers determines a string by constructing a
derivation tree from the leaves to the root.

123 / ??
Example

124 / ??
Example

125 / ??
Example

126 / ??
Grammar Ambiguity

Definition: a string is derived ambiguously in a context-free

grammar if it has two or more different parse trees
Definition: a grammar is ambiguous if it generates some string
ambiguously

127 / ??
Grammar Ambiguity

128 / ??
Grammar Ambiguity

129 / ??
Grammar Ambiguity

130 / ??
Grammar Ambiguity

131 / ??
Left Recursion

132 / ??
Left Recursion

133 / ??
Left Recursion

134 / ??
Left Factoring

■ Some grammar cannot be parsed by Predictive parser.

■ Left factoring is used to eliminate multiple production rules
that begin with the same token
For example:
Given a grammar with two production rules
stmt → if expr then stmt else stmt
| if expr then stmt
■ The above grammar has two production rule that begins
with the token if.
■ The grammar cannot be parsed by a preditive parser that
looks one element ahead.

135 / ??
Left Factoring

Therefore grammar
stmt → if expr then stmt else stmt
| if expr then stmt
can be re-written as:
′
stmt → if expr then stmt stmt
′
stmt → else stmt | λ
■ Left factoring can be defined as re-writing grammar to
eliminate multiple production rules that begin with the same
token

136 / ??
Left Factoring

In general:
1. Let A → α β 1 | α β 2 be two production rules for the non
terminal symbol A
2. if the input begins with a non empty string derived from α
3. and we do not know whether to expand A to α β 1 or α β 2
′
4. then we may defer the decision by expanding A to α A
′
5. after seeing the input derived from α, we expand A to β 1 or
to β 2
6. this means, left-factored, the original productions become
′
A→ α A
A→ α β 1 | β 2

137 / ??
Syntax Analysis/Parsing

138 / ??
Some Compiler Functions

The compiler performs three basic functions:

■ Lexical analysis: deals with the task of analysing source
statements, recognising and grouping tokens. The scanner
is responsible for performing this function.
■ Syntax analysis: each program statement must follow certain
rules recognised by programming constructs. This process
is called syntax analysis or parsing.
■ The last step in the compilation process is the generation of
target code

139 / ??
Syntax Analysis

■ During syntax analysis/Parsing the source statements of

the programming language are recognised as constructs
defined by Grammar.
■ Parsing techniques are divided into two classes: top down
parsing and bottom up parsing
■ Top down parsing: starts constructing the parse tree at the
top (root) of the tree and move down towards the leaves.
Example: predictive parsers.
■ Bottom up parsing: starts constructing the parse tree at the
bottom (leaves) of the tree and move up towards the root.

140 / ??
Top down parser

■ Top down parser creates a parse tree for an input string

from the root to the leaves of the tree.
■ Top down parsing is a left-most derivation for an input
string.
■ The idea is to determine the production rule to apply for a
non-terminal symbol of an input string.
■ For input string, production rules are chosen whose
non-terminals match left-hand side of production rule.

141 / ??
Top down parsing

Example:
Given the following Grammar G for the input id+id*id. Use top
down parsing to determine a sequence of parse trees for the
input string.
′
E → TE
′ ′
E → + TE | ǫ
′
T → FT
′ ′
T → *FT | ǫ
F → (E) | id

142 / ??
Top down parsing

143 / ??
Recursive descent parser

■ Recursive descent parsing is a form of Top down parsing.

■ Recursive-descent parsing is a program that is made up of
procedure for each non-terminal.
■ Parser scans the input string from the start symbol and halts
when the the input string is scanned.
■ Recursive descent parsing backtracks when necessary which
means repeated scan over the input string.

144 / ??
Recursive descent parsing

■ Backtracking involves trying several production rules to

scan an input string.
■ Failure to complete scan requires the need to return to
production rule(1) and try substitution again.
■ A local variable reset the input pointer to return to the
production rule(1).
■ Input error is declared if their is no production rule to try
again

145 / ??
Recursive descent parsing

Example:
Given the Grammar:
S→cAd
A → ab | a
To construct a parse tree for the input string w = cad
1. Tree begins with a single node labelled S
2. S has a production rule thus the first tree is constructed.
3. The input pointer moves to the first element of the input
string a.
4. The left-most leaf c matches the first symbol of the input
string, so the pointer moves to the second element a.
5. There is a production rule for A so it’s expanded to ab.
6. Second symbol a has a match so we proceed to the third
symbol d.
7. But d does not match b so the pointer is reset to position 2.

146 / ??
Recursive descent parser

■ The second expansion for a produces the tree.

147 / ??
FIRST and FOLLOW

We need to build a FIRST set and a FOLLOW set for each

symbol in the grammar.
■ The elements of FIRST and FOLLOW are terminal symbols.
■ FIRST(α) is the set of terminal symbols that can begin any
string derived from α.
■ FOLLOW(α) is the set of terminal symbols that can follow
α:
■ t FOLLOW(α) ↔ ∃ derivation containing αt

148 / ??
Rules to Create FIRST

149 / ??
Rules to Create FOLLOW

150 / ??
Rules to Create FOLLOW

151 / ??
Rules to Create FOLLOW

152 / ??
Rules to Create FOLLOW

153 / ??
Bottom up parsing

■ starts constructing the parse tree for an input string at the

bottom (leaves) of the tree and move up towards the root.
■ Shift reduce parsing is a form of bottom up parsing.
■ Shift reduce parsers are built using a class of grammars
called LR-Grammars.

154 / ??
Example

■ Bottom up parse for id * id

155 / ??
Bottom up parsing

■ Bottom up parsing reduces a string to the start symbol of

production rule.
■ A symbol that matches a production rule is replaced by the
non-terminal at the L.H.S of the rule.
■ Bottom up parsing is a derivation in reverse.

156 / ??
Shift reduce parsing

■ Shift-reduce parsing is a form of bottom up parsing

■ Shift-reduce parsing consist of a stack that holds the
grammar symbols and the buffer that holds the input
symbols.
■ The parser shifts zero or more input symbols to the top of
the stack.
■ The parser shifts the input symbols to the top of the stack
until it is ready to be reduced to the head of the appropriate
production.

157 / ??
Shift reduce parsing

■ If the stack contains the start symbol and the input buffer
is empty then the parser halts and announces successful
parsing
■ Otherwise the parser might encounter an error.
■ The shift-reduce parser has four operations: (1) Shift (2)
Reduce (3) Accept (4) Error
(1) Shift: Shift the next input symbol on top of the stack.
(2) Reduce: Replace the string within the stack with a
nonterminal at the head of the appropriate production rule.
(3) Accept: Announce successful completion of parsing.
(4) Error: Discovers syntax error while parsing.

158 / ??
Shift reduce parsing

159 / ??
LR-Parsing

■ In LR-parsing Items are kept in which each item is a

hypothesis about the token.
■ For instance the LR item N → α • β is example of a
possible handle. The position of a dot between two
grammar symbols means α has already been recognised.
■ When the • reaches the end of α β , it means α β can be
reduced to N while parsing.

160 / ??
LR-Parsing

■ There are various LR-parsing methods that differ based on

the LR items.
■ LR(0)items SLR(1) items, LR(1) items and LALR(1)
items.
■ LR items are used to do bottom up parsing.

161 / ??
Example 1

■ A simple grammar to demonstrate bottom up parsing

162 / ??
Example 1

■ An abbreviated form of the grammar.

■ Eof(end of input token) is represented by $.
■ Z stands for input.
■ i stands for IDENTIFIER

163 / ??
Example 1

■ Assume we have input symbols i + i$.

■ First we build a initial item set s0

164 / ??
Example 1

■ the initial item set is positioned before the first input

symbol.

165 / ??
Example 1

■ Each input symbol is scanned by moving the dot over the

symbol.
■ There is only on item in s0 in which the dot can be moved
over the symbol i:T → i •.
■ This gives us the initial contents of the new item set s1 : { T
→i•}
■ After reducing T → i we have the input as below.

166 / ??
Example 1

■ The next step is to reduce E → T, the input is shown below

■ The next input token is a +, there is only one item in s1
that has a dot in front of + E → E • + T.
Z→E•$
E → E•+T

167 / ??
Example 1

■ The next input token is a +, there is only one item in s1

that has a dot in front of +
E → E • + T.
We now get a different initial value for s1 Z → E • $
E → E•+T

168 / ??
Example 1

■ We have initial set for s2 :

E → E+•T
T → •i
T → •(E)

169 / ??
Example 1

■ There is only one item in s2 with a dot after +:E → E + •

T
■ This yields a new handle E → E + T • reduced to E

170 / ??
Example 1

■ The next input in the token is $ moving a dot over it yields

s2 : { Z → E$ • }

171 / ??
Yacc

■ LALR parser(Look-ahead, left to right rightmost derivation)

is used to analyse a token based on the set of production
rules specified by a grammar.
■ LALR parser generator Yacc can be used to construct the
front end of the compiler.
■ Yacc stands for yet another compiler compiler.
■ The first version of Yacc was created in 1970’s by S.C
Johnson

172 / ??
How to write LR Parser

■ The construction is done automatically by a tool such as

yacc.
■ Yacc is a Unix program.
■ Using the source program to write a simple yacc
program(yacc specification using language grammar) and
save it in a file named name.y.
■ The Unix command translates name.y resulting in a C
(parser) program named [Link].c.
■ Compiling and linking the C program [Link].c in a normal way
resulting the required parser.

173 / ??
Declaration Part

■ There are two sections in the declaration part of the Yacc

program.
■ In the first section we have C declarations delimited by {
% and % }.
■ In the declaration part, declarations used by the second
section and third section for procedures or translations.
■ Also contains the declaration of grammar token.

174 / ??
Translation Rules

■ In the Yacc specification after the first %% we have the

translation rules.
■ The section consist of grammar rules and the associated
action corresponding to each rule.

175 / ??
Yacc

■ In Yacc production, unquoted string of text not declared as

token is determined to be a non-terminal
■ The third part of the yacc program consist supporting C
procedure.

176 / ??
Yacc

■ A set of grammar production rules to be written in yacc

177 / ??
Yacc

■ In yacc production unquoted strings not declared to be

token are taken to nonterminals.

178 / ??
Yacc

■ A yacc semantic action is a sequence of C statements.

■ $$ refers to the value of the nonterminal of the head
■ $$i refers to the value of the ith grammar symbol of the
terminal or nonterminal of the body.
Example:
In Yacc specification :
E→E+T|T
We have the semantic action as follows:
expr : expr ’+’ term { $$ = $1 + $3; }
|term
;

179 / ??
Yacc

180 / ??
Yacc

181 / ??
Yacc

182 / ??
Yacc

183 / ??
Yacc

184 / ??
Yacc

185 / ??
Semantic Analysis

186 / ??
Symbol Table

■ Symbol table (or name list) is a mapping from an

identifier onto an associated record which contains collected
information about the identifier.
■ Symbol table is derived from the fact that identifiers are
once called ”symbols”.
■ It is a primary data structure in a compiler.
■ Stores information about the symbols in the input program.

187 / ??
Symbol Table

■ Symbol table is used in all phases of the compiler.

■ A parser creates a symbol table because with it’s syntactic
structure of the program it is in a better position to
distinguish different declaration of the variable.
■ In some cases a lexical analyser can create symbol table
entry as it reads characters that make up a token(lexeme).
■ The lexical analyser returns the token for example id and a
pointer to the lexeme.

188 / ??
Symbol Table Object

Symbol table functions are called during parsing:

■ Insert(x) A new symbol is defined.
■ Delete(x) The lifetime of a symbol ends.
■ Lookup(x) A symbol is used.
■ EnterScope(s) A new scope is entered.
■ ExitScope(s) A scope is left.

189 / ??
Symbol Table Implementation

■ Different structures are used to implement symbol table.

For example hash table, arrays, list, trees, heaps....
■ Different structures may be used for local tables versus tables
representing scope.
■ However hash tables are used to implement symbol table

190 / ??
Symbol Table Implementation

■ The general interface of a symbol table is as follows:

function Identify (IdfName)
returning a pointer to IdfInfo;
When called with arbitrary String name IdfName it returns a
pointer to o a record of type IdfInfo.
The compiler chooses the record type IdfInfo to store all
information that needs to be collected for an identifier.

191 / ??
Symbol Table Implementation

■ In C a symbol table act just like an array of records.

■ Symbol table when used in C could contain pointer to a
certain piece of information about.
■ For example a list of type, variable and function
definition.
■ macro definition.
■ keyword definition.

192 / ??
Symbol Table

■ A macro definition defines an identifier or token as a

macro.
■ A macro can specify a formal parameter which can be
substituted by an actual parameter.
An example in C is:
# define is capital(ch) ( A ≤ (ch) && (ch) ≤ Z)
This definition specifies that is capital(ch) must be substituted
by (A ≤ (ch) && (ch) ≤ Z) with the proper substitution for
ch.
A call of this macro:
is capital ( txt [ i ])
which supplies the actual parameter txt[i] , is to be replaced
by
( A ≤ ( txt [ i ]) && (txt [ i ]) ≤ Z)

193 / ??
Example

Figure 69:
194 / ??
Example

Figure 70:
195 / ??
Example

Figure 71: 196 / ??

Example

Figure 72:

197 / ??
Example

Figure 73:

198 / ??
Type Checking

■ A compiler assigns a expression to a component of a

program.
■ The compiler determines if expression conforms to certain
rules.
■ Type checking deals with catching error in programs.
■ Type checking allows code to be checked for errors before
imported to avoid malicious behaviour.

199 / ??
Type rules

The rules are:

■ which types can be combined with certain operator.
■ assignment of expression to variable.
■ formal and actual parameters of a method call
A type checker is a function that maps an AST that represents
an expression into its type.

200 / ??
Type checking

■ Checking whether the use of names is consistent with their

declaration in the program

Figure 74:

■ Statically typed languages : done at compile time, not at run

time

201 / ??
Example

Example:
a+b
a is of type integer and b is of type float.
The compiler converts one of the operands before the addition.
For example the integer 2 is converted to float in the calculation
of 2 * 3.142
t1 = (float)2
t2 = t1 * t2

202 / ??
Type Conversion

■ Type conversions vary from language to language.

■ Java deals with widening and narrowing conversion.
■ Widening conversion deals with retaining information for
example conversion of integer to float in float and integer
operation.
■ Narrowing conversion leads to loss of information.

203 / ??
Type Conversion

■ Type conversion is either explicit or implicit.

■ Implicit conversion is done automatically by the compiler.
Many languages carry out widening conversion.
■ Implicit conversions are also called coersion.
■ Explicit conversion is specified by the programmer.
■ Explicit conversions are also called casting.

204 / ??
Type checking: Implementation

■ Single traversal over AST

■ Types passed up the tree
■ Type environment passed down the tree

205 / ??
Type System

■ Type is a set of values and associated operations.

■ A type system is a collection of rules for assigning type
expressions to various parts of the program.
■ Type system enforce constraint that allows correctness.
■ Type system tailor computation to type thereby improving
efficiency.

206 / ??
Type Checking

Figure 75:

207 / ??
Processing Declaration

Figure 76:

208 / ??
Example

Figure 77:

209 / ??
Example

Figure 78:

210 / ??
Example

Figure 79:

211 / ??
Example

Figure 80:

212 / ??
Scope & Binding

■ Scope of a variable is that part of a program where the

variable is visible.
■ Scope is that part of a program where the variable can be
accessed.

213 / ??
Scope

■ In most languages, a program can have a different scopes for

the same variable name.
■ Different languages have different scope rules.
■ Language uses static scope or dynamic scope.

214 / ??
Scope

■ In static scope the scope of the declaration is determined by

the program structure. The scope is determined by where
the declaration appears in the program.
■ Languages such as C use static scope.

215 / ??
Static Scope

■ A C program is used to demonstrate static scope

■ C program consist of top level declaration of variables and
functions
■ A function consist of local variables and parameters
■ The scope of local variable is limited to the function it
appears

216 / ??
Static Scope

■ The program below has four blocks

■ Each block is delimited by opening and closing brace
■ The scope of variable a is throughout B1 except in other
nested blocks that have a declaration for a
■ B2 and B4 nested within B1 have no declaration for a but
B3 does have a declaration for a.
■ The output statement in B4 prints the value 4 referencing
the declaration of b in B4 and prints the value of a in B1
since B2 has no declaration of a.

217 / ??
Static Scope

Figure 81:

218 / ??
Dynamic Scope

■ Dynamic scope is based on calling sequences of program

unit.
■ In Dynamic scope references to variables are connected to
declarations by searching the chain of subprogram calls
(runtime stack) that forced execution to this point
■ In a dynamic-scoped language, the referencing environment
is the local variables plus all visible variables in all active
subprograms.

219 / ??
Environment & State

■ Variables refer to location in memory

■ Names are associated with locations in memory
■ Environment is defined as mapping from name to location
■ State is a mapping from locations in store to their values

220 / ??
Environment & State

Figure 82:

221 / ??
Example

Figure 83:

222 / ??
Example

■ Integer i is declared as a global variable

■ Integer i is also defined as variable local function f
■ When f is executing the environment adjust so that name i
refers to the location that is reserved for the local variable i
■ Local variable i is placed on the run time stack.

223 / ??
Binding Names to Locations

■ Binding names to locations can be either static or dynamic

■ Most binding of name to location is dynamic

224 / ??
Binding Locations to Values

■ Binding locations to values can be either static or dynamic

■ Most binding of location to values is dynamic
■ The value in the location is determined at runtime.

225 / ??
Memory Management

226 / ??
Memory Management

■ Memory management is the process of mapping names in

the source program to addresses of data objects in
run-time memory.
■ All compilers use dynamically sized data.
■ The size of such data is not known in advance and room for
it must be found at run time.
■ Examples of data are symbol table, string.

227 / ??
Memory Management

■ The allocation of fixed memory to data leads to an error or

truncate the data if the memory is exceeded.
■ With better memory sizes, programming techniques.
Dynamic memory management is important of compilers.
■ Most operating systems allocate atleast one of the following
memories to data: code segment, stack segment and the
data segment.

228 / ??
Memory Management

■ Code segment: which contains the program code and

which is usually read- only or execute-only; it is addressed by
the program counter and is next to invisible to the program
code itself
■ Stack segment: which contains the stack and which may
come with an overflow and underflow detection mechanism.
It is addressed by stack pointers, which are most of the time
manipulated automatically by machine instructions
■ Data segment: which is a single contiguous block of
memory locations, totally at the disposition of the program
for the purpose of storing data

229 / ??
Data Allocation

There are generally two types of data allocation:

(1) Explicit allocation
(2) Implicit allocation (garbage collection.)

230 / ??
Explicit allocation

■ Explicit allocation is mostly concerned with a routine that

finds a block of unused memory marks it as used and
returns a pointer to the block(segment of memory).
■ If no such block is available, the result varies: a null pointer
may be returned or an error routine may be invoked, or the
program may be aborted.
■ The requested size is given as a parameter to the routine.
The marking prevents the block from being handed out more
than once.

231 / ??
Basic Memory Allocation

■ A memory allocation request ofN bytes supplies the user

with a pointer to the first byte of a block of N free bytes.
■ Memory fragments are called blocks if they are in the hands
of the user.
■ Memory fragments are called chunks if they are in the hands
of the memory allocator.
■ A chunk contains a block and some additional information
such as the length of the chunk.

232 / ??
Chunks

■ Pointers that reside inside a block are under user control and
will point to the start of blocks.
■ Pointers inside the allocation administration are under the
control of the allocator and will point to chunks.
■ Chunk size field and there are bits in each chunk for
administration purposes
■ One of the bits is a free bit, which indicates if a chunk is
free.

233 / ??
Memory Structure: Used by Malloc

Figure 84:

234 / ??
Memory Structure: Used by Malloc

The implementation of a routine Malloc(BlockSize)

■ To allocate a block B of the required BlockSize, Malloc
steps through the chunks until it finds a chunk C marked
free that is large enough to accommodate B.
■ The chunk C is then broken into two chunks C1 and C2,
such that C1 has the proper size for the block B unless of
course the block happens to fit exactly, in which case no
chunk C2 is created.
■ The size fields of C1 and C2 are set to their new values, the
free bit of C1 is turned off, that of C2 is turned on.
■ A pointer to the block in C1 is returned to the requester.

235 / ??
Data allocation with implicit deallocation

■ Implicit deallocation is also called garbage collection.

■ Is the automatic reclamation of memory that is no longer in
use by the application program.
■ Programmers reclaim memory manually by using an explicit
free() primitive.
■ Garbage collection relieve the error-prone task of relieving
memory.

236 / ??
Data allocation with implicit deallocation

■ Garbage collection is an important feature of modern

programming.
■ Different kinds of programming languages provide garbage
allocation
■ Object-oriented languages like Java and Smalltalk.
■ Functional languages like ML and Haskell.
■ Logic languages like Prolog, and scripting language Perl.

237 / ??
Basic Garbage Collection Algorithm

■ Garbage collection reclaims the set of memory chunks that

are no longer be used by the program.
■ Such memory chunks are called garbage set.
Garbage set usually consist of:
[Link] set of all chunks to which there are no pointers.
[Link] set of all chunks that are not reachable from the
non-heap-allocated program data.

238 / ??
Basic Garbage Collection Algorithm

■ The no-pointers criterion leads to a technique called

reference counting
■ The not-reachable criterion leads to two techniques, mark
and scan and two-space copying.

239 / ??
Reference Counting

■ Reference counting identifies set memory chunks to which

there are no pointers.
■ Reference counting directly identifies garbage chunks with
missed pointers.
■ It is simple and reasonably efficient algorithm.
■ The major draw back is that all pointer actions to be
monitored during program execution and may not recover all
garbage chunks.
■ Algorithm may not recover all chunks

240 / ??
Reference Counting

■ Reference counting is a garbage collection algorithm that

records in each chunk the number of pointers that point to it
■ The number drops to zero the chunk can be declared
garbage
■ The reference count is updated in several actions on the
chunk.
■ Whenever a reference to the chunk is duplicated, its
reference count is increased by one.
■ If the reference count drops to 0, the chunk can be freed
because it is no longer reachable

241 / ??
Example

■ What happens if a chunk that reference another chunk

becomes zero?

Figure 85:
242 / ??
Example

■ Returning a chunk with zero reference count is not enough to

reclaim all garbage since it may contain a non zero reference.

Figure 86:
243 / ??
Mark & Scan

■ Mark and scan identifies all reachable chunks used by the

program.
■ Mark and scan identifies reachable chunks and concludes
that the rest is garbage.
■ It is efficient algorithm as it requires no pointer monitoring.
■ The major drawback is it is fairly complicated.
■ It is the only algorithm that recover all chunks.

244 / ??
Mark & Scan

■ Mark and Scan is also called mark and sweep.

■ each chunk the number of pointers that point to it
■ Mark and scan has two phases:
■ The first phase or the marking phase, marks all chunks
that are still reachable
■ The scan phase, scans the allocated memory and considers
as free chunks all chunks that are not marked reachable and
makes them available again
■ If the reference count drops to 0, the chunk can be freed
because it is no longer reachable

245 / ??
Two Space Copying

■ Two-space copying is not concerned with garbage

■ It deals with copying data
■ It copies the reachable chunks from a memory region called
from-space to a memory region called to-space
■ The remaining space in to-space is a single free chunk
■ It is very efficient as it does not require pointer monitoring
■ It is moderately complicated but wastes half of the memory.

246 / ??
Basic Garbage Collection Algorithm

■ Garbage collection reclaims the set of memory chunks that

are no longer be used by the program.
■ Such memory chunks are called garbage set.
Garbage set usually consist of:
[Link] set of all chunks to which there are no pointers.
[Link] set of all chunks that are not reachable from the
non-heap-allocated program data.

247 / ??
Garbage Chunks

■ Garbage chunks identified by these techniques must be

turned into free memory space to be useful.
■ Garbage chunks found by reference counting or mark and
scan must be returned to the free list by the algorithm.
■ Two-space copying automatically creates a fresh free list
consisting of a single large chunk that includes all of free
memory.
■ Locating all free chunks and adding them to the free list
sometimes leaves the free memory fragmented in a number
of free chunks separated by chunks in use leading to
memory fragmentation.

248 / ??
Compaction

■ To obtain the free memory from list of fragmented memories

separated by used chunks, a single free chunk is used.
■ Compaction moves the used chunks to one side, thereby
moving the free chunks to the other side to create a single
large free chunk.
■ Compaction is more complicated and time-consuming than
just freeing the garbage chunk.
■ Compaction is the best way to recover unused memory.

249 / ??
Role Of Compiler In Garbage Collection

■ The compiler has to provide information about the pointer

layout of each chunk to the garbage collector.
■ The pointer layout of a chunk C describes the position of
each pointer P in the chunk.
■ It also determines the type of the chunk that P points to.
■ The compiler also has to make sure that all reachable
pointers, both in the program data area and in the heap, are
valid when the garbage collector is activated.

250 / ??
Intermediate Code Generation

251 / ??
Intermediate Representation(IR)

■ The semantic analysis phase of a compiler translates abstract

syntax into abstract machine code.
■ An intermediate representation (IR) is a kind of abstract
machine language that can express the target-machine
operations without expressing too much machine specific
detail.
■ The role of the front end of the compiler is lexical analysis,
parsing, semantic analysis, and translation to intermediate
representation.
■ The role of the back end of the compiler is optimization of
the intermediate representation and translation to machine
language.

252 / ??
Intermediate Representation

■ An intermediate representation (IR) allows portability and

modularity.
■ The role of the front end of the compiler is lexical analysis,
parsing, semantic analysis, and translation to intermediate
representation.
■ The role of the back end of the compiler is optimization of
the intermediate representation and translation to machine
language.

253 / ??
Example

■ Suppose we want compilers for N different source languages,

targeted to M different machines. The implementation of
N•M is a large task.
■ IR allows better implementation of N front ends and M back
endsd.
Example: Compilers for five languages and four target machines
with or without IR.

254 / ??
Figure 87:
Intermediate Code Generation

■ The output of the front end of the compiler is the

intermediate code.
■ Front end is responsible for checking syntactic and
semantic rules of the source program.
■ Intermediate code generation allows the back end of the
compiler to be changed without developing a whole new
compiler.
■ Code modifications can easily be applied to intermediate
code to improve performance.

255 / ??
Types Of Intermediate Representation

■ Graphical Intermediate Representation:

■ Linear Intermediate Representation:

256 / ??
Types Of Intermediate Representation

■ Graphical Intermediate Representation:

◆ Abstract Syntax trees(AST)
◆ Direct Acyclic Graph(DAG)
◆ Control Flow Graphs
■ Linear Intermediate Representation:
◆ Stack based (postfix)
◆ Three-address code

256 / ??
Abstract Syntax Trees Construction

■ Syntax tree can be constructed for any source program

construct.
■ Abstract syntax tree(AST) retains essential features of the
parse tree eliminating unnecessary nodes.
■ DAG(Direct Acyclic Graph) compacts similar nodes of
AST to avoid duplication.

257 / ??
Example

■ AST and DAG construction for a =b*-c + b*-c

Figure 88:
258 / ??
Linear intermediate representation(Linear IR)

■ Linear IR consist of linear sequence of low-level instructions.

■ Reflect instruction sets of the target machine
■ Implemented as three-address code or stack-machine code.

259 / ??
Stack-Machine Code

■ Implemented using stack as an operand

■ Also called one address code
■ Operations take operands from the stack and push results
back onto the stack
■ Requires special operation such as swap to swap operands in
the stack.
■ Used as IR in Java and Smalltalk

260 / ??
Example

■ Stack-machine code for x 2 * y

Figure 89:

261 / ??
Three-Address Code

■ Three-address code is a sequence of instructions of the form

x = y op z
■ op stands for operator and x,y,z are names, constants.
■ Three-address code manipulates one result and at most two
operands.

262 / ??
Three-Address Code

■ Three-address code is a sequence of instructions of the form

x = y op z
■ op stands for operator and x,y,z are names, constants.
■ Three-address code manipulates one result and at most two
operands.
◆ Arithmetic operations: x := y op z | x := op y
◆ Data movement: x := y [ z ] | x[z] := y | x := y
◆ Control flow: if y op z goto x | goto x

262 / ??
Example

■ Three-address code for x - 2 * y

Figure 90:

263 / ??
Storing Three-Address Code

■ All instructions are stored in a quadruple table.

■ The table has four fields
■ Every instruction has four fields: op, arg1, arg2, result

264 / ??
Storing Three-Address Code

■ Three-address code for x - 2 * y

Figure 91:

265 / ??
Example

■ Example for a=b*-c + b*-c

Figure 92:
266 / ??
Example

■ Example for a=b*-c + b*-c

Figure 93:

267 / ??
Example

■ Example for a=b*-c + b*-c

Figure 94:
268 / ??
Example

■ Example for a=b*-c + b*-c

Figure 95:

269 / ??
Example

■ Example for a=b*-c + b*-c

Figure 96:
270 / ??
Example

■ Example for a=b*-c + b*-c

Figure 97:
271 / ??
Example

■ Example for a=b*-c + b*-c

Figure 98: 272 / ??

Example

■ Example for a=b*-c + b*-c

273 / ??
Example

■ Example for a=b*-c + b*-c

Figure 100:

274 / ??
Code Generation

275 / ??
Code Generation

■ The last phase of the compilation process is the code

generator
■ The final output of the front end of the compiler is the
intermediate representation(IR).
■ The code generator takes the IR as input to produce the
target program.
■ The ultimate goal is to produce a target program that
preserves the meaning of the the source program.

276 / ??
Code Generator

Figure 101:

277 / ??
Code Generation

■ The code generation problem is the task of mapping

intermediate code to machine code.

278 / ??
Code Generation

■ The code generation problem is the task of mapping

intermediate code to machine code.
◆ Issues driving code generator design:
◆ 1. Correctness: The generated code should be correct.
◆ 2. Efficiency: To produce efficient code the optimization
phase should occur prior to code generation. The code
optimizer maps the IR to more optimized IR in order to
generate efficient code.

278 / ??
Code Generator

The code generator has three major task.

1. Instruction selection.
2. Register allocation and assignment.
3. Instruction ordering.

279 / ??
Code Generator

■ The input to the code generator is the IR and the symbol

table.
■ Instruction set architecture has an impact on the design of
the code generator.
■ Most common target machine instruction set architecture are
RISC (reduced instruction set computer), CISC (complex
instruction set computer), and stack based.
■ RISC has many registers typically three address code.
■ CISC has fewer registers(two address code.)

280 / ??
Instruction Selection

■ Instruction selection involves choosing target-machine

instructions to implement the IR statements.
■ The complexity of code generator is determined by the level
of the IR, the instruction-set architecture and the quality of
the generated code.
■ Low-level IR is used by the the code generator to produce
more efficient code sequences whereas if the IR is high level,
the code generator may translate each IR statement into a
sequence of machine instructions using code templates.

281 / ??
Register Allocation and Assignment

■ Register allocation and assignment involves deciding what

values to keep in which registers.
■ Values are usually held in registers or memory.
■ Registers are the fastest storage units.
■ Instructions involving register operands are invariably shorter
and faster than those involving operands in memory.

282 / ??
Register Allocation and Assignment

■ Register allocation involves the selection of set variables that

will reside in registers at each point in the program.
■ Register assignment involves choosing a register to store a
variable.

283 / ??
Instruction Ordering

■ Instruction ordering involves deciding in what order to

schedule the execution of instructions.

284 / ??
Target Machine

MOV s, d (move source to destination)

ADD s, d (add source to destination)
SUB s, d (subtract source from destination)
MUL s, d (multiply source to destination)
DIV s, d (divide source by destination)

285 / ??
Target Machine

Storing values: Examples of storing the contents of registers into

memory locations can be as follows.
MOV R0, m (stores the contents or register R0 into memory
location m)
MOV 4(R0), m (stores the value contents(4+contents(R0)) into
memory location m)
MOV *4(R0), m (stores the value
contents(contents(4+contents(R0))) into memory location m)
MOV #n, R0 (Loads the constant number n into register R0)

286 / ??
References

A. Aho, R. Sethi and J. Ullman, Compilers: Principles,

Techniques and Tools(The Dragon Book), Addison Wesley
Andrew W. Appel : Modern Compiler Implementation in ML
Dick Grune et. al :Modern Compiler Design, Second edition
Prof. Mohamed Hamada(2017). Compilers. The University of
Aizu, Japan.

287 / ??