Compilers
Introduction
1
2
Agenda
Why Study Compilers?
The Structure of a Compiler.
3
Compilers
Main Book
Principles, Techniques, & Tools
Second Edition
Authors:
Alfred V. Aho
Monica S. Lam
Ravi Sethi
Jeffrey D. Ullman
4
Why Study Compilers?
Learn how programming languages work.
Learn how to build programming languages.
Learn tradeoffs in language design.
Build a large software system.
5
Language Processors
A compiler is a program that can read a
program in one language ( the source
language) and translate it into an
equivalent program in another language
(the target language)
An interpreter directly execute the
operations specified in the source
program on inputs supplied by the user,
6
Language Processors
Java language processors combine compilation and
interpretation (Hybrid)
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
7
A language-processing system
8
preprocessor
A language-processing system
•A source program may be divided into modules stored in separate
files.
•It’s task is to collect the source program, a responsibility sometimes
entrusted to a separate program.
Compiler
•The modified source program is then fed to a compiler.
•The compiler may produce an assembly-language program as its
output,
•because assembly language is easier to produce as output and is
easier to debug.
Assembler
•The assembly language is then processed by a program called an
assembler
•Assembler produces relocatable machine code as its output.
Linker / Loader
• Large programs are often compiled in pieces
• the relocatable machine code may have to be linked together with other
relocatable object files and library les into the code that runs on the machine.
• The linker resolves external memory addresses, where the code in one file may
refer to a location in another file.
• The loader then puts together all of the executable object les into memory for
execution
9
The Structure of a
Compiler
10
The Structure of a Compiler:
Two Major Parts
1. Analysis (Front-End)
Input: Source program.
Task: Breaks down the source code, checks syntax and
semantics, and builds an intermediate representation (IR).
Language-Specific. Must understand the rules of the source
language.
Output: IR + Symbol Table (information about the source
program).
2. Synthesis (Back-End)
Input: IR from the front-end.
Task: Generates the target program from the IR.
Machine-Specific. Must optimize for and understand the target
machine/architecture.
Output: Target program (e.g., executable, assembly).
11
Phases of a Compiler
12
From Description to
Implementation
Lexical analysis: Identify logical pieces of description.
Syntax analysis: Identify how those pieces relate to
each other.
Semantic analysis: Identify the meaning of those
relations.
IR Generation: Generate an intermediate code
(three address code).
IR Optimization: Simplify the intermediate code.
Code Generation: Generate the assembly code.
Optimization: Improve the resulting assembly.
13
The Structure of a Modern
Compiler
14
Lexical Analysis
while (y < z) {
int x = a + b;
y += x; }
15
Lexemes vs Tokens
Input Stream:
while (y < z) {
int x = a + b;
y += x; }
Output Stream (Tokens):
T_While T_LeftParen T_Identifier y T_Less T_Identifier z
T_RightParen T_OpenBrace T_Int T_Identifier x T_Assign
T_Identifier a T_Plus T_Identifier b T_Semicolon
T_Identifier y T_PlusAssign T_Identifier x T_Semicolon
T_CloseBrace
16
Syntax Analysis
Parse Tree:
17
Semantic Analysis
18
IR Generation
while (y < z) {
int x = a + b;
y += x; }
Loop: x = a + b
y =x+y
_t1 = y < z
if _t1 goto Loop
19
IR Optimization
while (y < z) {
int x = a + b;
y += x; }
x =a+b
Loop: y = x + y
_t1 = y < z
if _t1 goto Loop
20
Code Generation
while (y < z) {
int x = a + b;
y += x; }
add $1, $2, $3
Loop: add $4, $1, $4
slt $6, $4, $5
bne $6, $zero, loop
21
Optimization
while (y < z) {
int x = a + b;
y += x; }
add $1, $2, $3
Loop: add $4, $1, $4
blt $4, $5, loop