Introduction Compilation insight Bibliography
Programming Languages Design and
Implementation
M. T. Bennani
Assistant Professor, FST - El Manar University, URAPOP-FST
-Academic Year 2020-2021-
M. T. Bennani Assistant Professor, FST - El Manar University, URAPOP-FST
Chapter I. Introduction
Introduction Compilation insight Bibliography
Why Is Compilers Interesting?
I Understand how programming languages operate
I Learn how to develop programming languages
I Discover the basic concepts of the languages design
I Create ambitious software or libraries.
2 / 12
Introduction Compilation insight Bibliography
How Compilers Work
3 / 12
Introduction Compilation insight Bibliography
From the description to the implementation
I Lexical Analysis (Scanning): Identify the logical pieces of a
given description.
I Syntactic Analysis (Parsing): Distinguish how the elements
relate to each other.
I Semantic Analysis: Recognize the meaning of the entire
structure.
I Generate the intermediate representation: Design a possible
structure (composition).
I Optimize the intermediate representation: Simplify the
produced composition.
I Code Generation: Generate a low layer program.
I Optimization: Improve the previous output.
4 / 12
Introduction Compilation insight Bibliography
1. Lexical Analysis
Output T Assign
T While T Identifier a
T ParLeft T Plus
Source File
T Identifier y T Identifier b
while ( y z ){ T Lessthan T Semicolon
i n t x = a+b ; T ParLeft T Identifier y
y += x ; T Identifier z T PlusAssign
} T ParRight T Identifier x
T BracOpen T Semicolon
T Int T BracClose
T Identifier x
5 / 12
Introduction Compilation insight Bibliography
2. Syntactic Analysis
Input
The set of tokens generated by the lexical analyzer
Output
Abstract syntax tree
6 / 12
Introduction Compilation insight Bibliography
3. Semantic Analysis
Input
The abstract syntax tree generated by the syntactic analyzer
Output
Enhanced Abstract syntax tree
7 / 12
Introduction Compilation insight Bibliography
4. Generation of the intermediate representation
Input
The enhanced abstract syntax tree generated by the semantic
analyzer
Output
Intermediate representation:
1 Loop : x = a + b
2 y = x + y
t1 = y < z
4 i f t 1 goto Loop
8 / 12
Introduction Compilation insight Bibliography
5. Optimization of the intermediate representation
Input
The intermediate representation generated by the IR generator
Output
Optimized Intermediate representation:
1 x = a + b
2 Loop : y = x + y
t1 = y < z
4 i f t 1 goto Loop
9 / 12
Introduction Compilation insight Bibliography
6. Low Level Code Generation
Input
The enhanced intermediate representation generated by the IR
optimizer
Output
Low level code:
1 add $1 , $2 , $3
2 Loop : add $4 , $1 , $4
slt $6 , $1 , $5
4 beq $6 , loop
slt: Set on less than. If $1 is less than $5, $6 is set to one. It gets zero otherwise.
beq: Branch on equal. Branches if the two registers are equal.
10 / 12
Introduction Compilation insight Bibliography
7. Code Optimization
Input
Low Level Code generated by the LLC Generator
Output
Optimized Low level code:
1 add $1 , $2 , $3
2 Loop : add $4 , $1 , $4
b l t $1 , $5 , l o o p
blt: Branch on lower than. Branches if the two registers are equal.
11 / 12
Introduction Compilation insight Bibliography
References
I Compilers: Principles, Techniques, and Tools (Second
Edition), Alfred Aho, Monica Lam, Ravi Sethi, and Jeffrey
Ullman. Addison-Wesley, Published August 2006.
I Modern Compilers Implementation in Java (Second
Edition), Andrew Appel and Jens Palsberg. Cambridge
University Press, Published October 2002.
I Engineering: A Compiler (Second Edition), Keith Cooper
and Linda Torczon. Morgan Kaufmann Editions, Published
February 2011.
12 / 12