Похожие презентации:
Эпизод III: Свой язык программирования
1.
Эпизод III:Свой язык
программирования
2.
ЛитератураDragon book
3.
Компилятор – это трансляторHigh level
language
compiler
Low level
language
A compiler translates high-level programs to low-level program
4.
Компилятор – это трансляторC
gcc
x86
GCC translates C programs to object code for X86 (and other architectures
5.
Компилятор – это трансляторJava
javac
JVM
bytecode
A Java compiler translates Java programs to bytecode instructions for Java Virtual Machine
6.
Архитектура: многопроходный компиляторJava
Parse
Type check
Optimize
Code Gen
JVM
bytecode
A Java compiler translates Java programs to bytecode instructions for Java Virtual Machine
7.
Промежуточные представленияJava
code
Parse
Abstract
syntax
tree
Type
check
Annotated
AST
Optimize
Transformed
AST
Code
Gen
JVM
bytecode
A compiler is a composition of a series of translations between intermediate languages
8.
Компоненты компилятораJava
code
Parse
Abstract
syntax
tree
Type
check
Annotated
AST
Optimize
Transformed
AST
Parser (Lexical analyzer + Syntax analyzer)
• Reads in program text
• Checks that it complies with the syntactic rules of the language
• Produces an abstract syntax tree
• Represents the underlying (syntactic) structure of the program
Code
Gen
JVM
bytecode
9.
Компоненты компилятораJava
code
Parse
Abstract
syntax
tree
Type
check
Annotated
AST
Optimize
Transformed
AST
Code
Gen
JVM
bytecode
Type checker (Semantic analyzer)
• Consumes an abstract syntax tree
• Checks that the program complies with the static semantic rules of the language
• Performs name analysis, relating uses of names to declarations of names
• Checks that the types of arguments of operations are consistent with their
specification
10.
Компоненты компилятораJava
code
Parse
Abstract
syntax
tree
Type
check
Annotated
AST
Optimize
Transformed
AST
Code
Gen
Optimizer
• Consumes a (typed) abstract syntax tree
• Applies transformations that improve the program in various dimensions
• execution time
• memory consumption
• energy consumption
JVM
bytecode
11.
Компоненты компилятораJava
code
Parse
Abstract
syntax
tree
Type
check
Annotated
AST
Optimize
Transformed
AST
Code
Gen
Code generator
• Transforms abstract syntax tree to instructions for a particular computer
architecture
• aka instruction selection
JVM
bytecode
12.
Компилятор = front-end + back-endBack-end
Front-end
Java
code
Parse
Type
check
Annotated
AST
Optimize
Code
Gen
JVM
bytecode
A compiler can typically be divided in a front-end (analysis) and a back-end (synthesis)
13.
Компилятор = front-end + back-endBack-end
Front-end
C
Parse
Type
check
LLVM IR
Optimize
Code
Gen
x86
A compiler can typically be divided in a front-end (analysis) and a back-end (synthesis)
14.
Компилятор = front-end + back-endFront-end
C
Parse
Back-end
Type
check
Optimize
Code
Gen
x86
Code
Gen
Arm
LLVM IR
Front-end
C++
Parse
Type
check
Back-end
Optimize
Repurposing: reuse a back-end for a different source language
Retargeting: compile to different hardware architecture
15.
Типы компиляторов (1)Compiler
• translates high-level programs to machine code for a computer
Bytecode compiler
• generates code for a virtual machine
Just-in-time compiler
• defers (some aspects of) compilation to run time
Source-to-source compiler (transpiler)
• translate between high-level languages
Cross-compiler
• runs on different architecture than target architecture
16.
Типы компиляторов (2)Interpreter
• directly executes a program (although prior to execution program is typically
transformed)
Hardware compiler
• generate configuration for FPGA or integrated circuit
De-compiler
• translates from low-level language to high-level language
17.
Lexing & Parsing18.
Лексический и синтаксический анализ программыText
Lexer
Tokens
Parsing
AST
19.
Пример контекстно-свободной грамматики20.
Лексический и синтаксический анализ программы21.
Пример для арифметических выражений22.
Вывод23.
Дерево разбора24.
Пример для арифметических выраженийid * id + id
+
*
id
id + id + id
id
id
25.
Semantic analysis26.
А нам точно нужен семантический анализ?27.
Name analysis28.
Validity29.
Visibility30.
Qualification31.
Multiple namespaces32.
Symbol table33.
Граф потока управленияentry
void foo() {
int x = source();
if (x < MAX) {
int x = call (“source”)
int y = 2 * x;
sink(y);
}
x < MAX
true
}
int y = 2 * x
false
call (“sink”, y)
exit
34.
Code property graphentry
void foo() {
int x = source();
if (x < MAX) {
int x = call (“source”)
int y = 2 * x;
sink(y);
}
x < MAX
true
}
int y = 2 * x
false
call (“sink”, y)
exit
35.
Семантический анализsource
def
entry
void foo() {
int x = source();
if (x < MAX) {
int x = call (“source”)
int y = 2 * x;
sink(y);
}
x < MAX
true
}
int y = 2 * x
false
call (“sink”, y)
exit
sink
def