image/svg+xml
Flavien Breuvart
Français
Cours
Compilation
CPU
Frontend
CPU
Backend
CPU
Exécution
Machine Virtuelle
Compilation
a
v
a
J
CPU
CPU
Bytcode
Interpretation
Représentation interne
Analyse lexicale
Analyse Syntaxique
Analyse sémantique
Analyse de portée
Typagestatique
Liagestatique
StreamdeTokens
Arbre syntaxique abstrait(AST)
Lexeur
Parseur
Reconnaissancedes Lexems
Création des tokens
Maximum-munch
Pippline : une fois un lexem reconnu, on le tokenise et on passe au suivant
Sans mémoire :chaque lexem estindépendant
Lexeur-Parseur :Certains outils, fornissent un lexeur-parseur qui permet une reconnaissance de lexems qui soit contextuelle lorsqu'il y un mixte de deux langages (ex : html / PHP)
if (2 + 2 == 4.0 )then print "toto"
IF,ParG,Int(2),Plus,Int(2),Eg,Reel(4.0),ParD,THEN,Id(print),Str(toto)
IfThen
==
+
Int
Int
2
2
Reel
4.
app
Id
Str
print
toto
Certains langages compilés ne sont pas statiquement typés
Quelle est la portée de chaque déclaration de variable et fonction
Pour chaque appel de fonction, si on sait statiquement quelle fonction est appellée, on y fait directement référence.
ex : métodes statiques mais pas les métodes d'instances
IfThen
==f
+i
Int
Int
2
2
Reel
4.
app
Id
Str
print
toto
decl(toto)
string
float
int
int
int
bool
1
1
3
1
Cast
float
4
6
1
1
5
12
Construction de l'arbresyntaxique
Simplification/ abstraction
<com>
==
+
Int
2
Reel
Id
Str
"print"
"toto"
Int
)
if
then
<exp>
(
<exp>
<exp>
<exp>
<com>
<or>
<exp>
<exp>
2
4.0
(
)
<exp>
Deux types de parseurs
LL:"devine" le noeudque l'on va lire
LR :"devine" le noeud que l'on a lu
Interpretation
Comment faire un lexeur ?
à la main...
à l'aide d'un générateur de lexeur :
Comment faire un parseur ?
à la main...
à l'aide d'un générateur de parseur:
Pourquoi uncours deCompilation ?
Pour optimiser mon code
Un bon développeur est généralement spécialisé dans quelques languages spécifiques, ils doit en connaitre la syntaxe, les bibliothèque, mais aussi son compilateur/interpreteur ! Certaines optimisation du compilateur demandent à l'utilisateur de metre le code sous une forme spécifique (ex : récurtion terminale) Pour optimiser certains code de manière très fine, il faut quelquesfois introduire de l'assembleur, ou intervenir directement sur la machine virtuelle."
Apprendre de nouveaux langages
Certaines features des langages sont dirigées par des problématiques de compilation, savoir ce qu'il y a derière permet de mieux les comprendreex : GC, clotures, prototypes de JS... Comprendre la différence entre erreurs lexicales, syntaxiques, de typage, de scope, ect... Savoir lire la documentation formelle d'un langage(grammaire, sémentique) "
Pour faire son propre compilateur ?
C'est un bon exercice (et on va le faire !), mais soyons honnête :Vous n'aurez jamais plus l'occasion de le faire... Par contre un développeur devra régulièrement réimplémenter certaines parties(lecture de scripte, optimisation, manipulation du langage/framework) "
Découvrir un gros projet
Un compilateur est un exemple de programme complèxe, versionné et structuré ! Une bonne partie du code du compilateur est généré par des outils annexes La structure n-tier est à la fois simple et très modulaire
Les automates dans la pratique
On va voir que le frontend utilise des algos avancés sur des automates. Il s'agit algorithmes théoriques "dégradés" pour une utilisation concrète. Il s'agit d'une situation classique : la théorie est rarement utilisable directement, mais fournie des bases solides pour construir autour.
Et encore beaucoup plus
On va devoir utiliser des structures de données complèxes (ADTs, environement...). Pour le GC, il va faloir revoir les algos de graphes.(uniquement survolé par manque de temps...) Il faut implémenter et utiliser des machines Turing-complètes (assembleurs). Il faut aussi types, spécifier, vérifier, parcourir, reconnaitre...etc...
Code àcompiler
.c/.py...
.class /.jsm
CPU
ProgrammeExécuté
Exécution del'Interpreteur
Code à interpréter
.py
Interpreteur assemblé
.exe
Sortie
Entrée
CPU
Sortie
Entrée
CPU
CPU
Code assembleur
.asm
ProgrammeExécuté
Execution duCompilateur
Code à compiler
.c
Compilateur assemblé
.exe
Entrée
Sortie
Sortie
Entrée
CPU
Sortie
Entrée
Code assembleur
.asm
Plus Tard
CPU
CPU
Execution duCompilateur
Code à compiler
.java
Compilateur assemblé
.asm
Sortie
Entrée
CPU
Sortie
Entrée
Code assembleurvirtuel
.class
Plus Tard
ProgrammeExécuté
Execution dela machinevirtuelle
Interpreteur assemblé
.asm
Sortie
Entrée
CPU
Sortie
Entrée
Code assembleurvirtuel
.class
CPU
Génnérateur de lexeur
Expressionsregulières
.l / .mll
Code dulexeur
.c / .ml
.exe
Lex /CamlLex
Sortie
Entrée
CPU
Sortie
Entrée
CPU
Grammaire du langage
.y / .mly
Code duparseur
.c / .ml
Génnérateur de parseur
.exe
Bizon / Camlyacc
Sortie
Entrée
CPU
Sortie
Entrée
Dans les interprèteurs (et dans le projet) :Uniquement le "hoisting" ex : "Var" vs "Let" en JS
Pas dans le projet
Pas dans le projet
Lire et Décrypter le code textuel.
Optimiser et traduire vers de l'assembleur
Compilation dans les années 90's
assembleur/ binaire
.asm/.exe
Dans ce cours, on ne fera pas de diférence entre le binaire et l'assembleur
Elimination du sucre syntaxique
Bibliothèques
Bibliothèques
compiléesséparément
GarbageCollector
GarbageCollector
Choix des instructions
Choix des instructions
Optimisations Diverses
Ce sont les notations qui ne sont là que pour alléger votre code En réalité elles sont exactementéquivalente à un code plus lourd maissans ces syntaxes spéciales.
ajoutées pour l'optimisation global
Optimisations haut niveau
Optimisations bas niveau
GetVar g1StrCalGetVar g1StrCalGetVar g2StrCalGetVar g2StrCalCsteNb 10SetArgCallSetArgCallSetArgCallSetArgCallHalt
#code fDecVar yDecVar gNewClo 6DecArg zSetVar gGetVar xSetVar yGetVar gReturn#code gGetVar yGetVar zAddiNbSetVar yGetVar yReturn
DecVar fNewClo 32DecArg xSerVar f#tete finGetVar fSrtCalCsteNb 1SetArgCallSetVar g1GetVar fSrtCalCsteNb 0SetArgCallSetVar g2
CsteNb 12SetVar xCsteNb 12CstRe 3AddiNbGetVar xCsteNb 2MultReLowEqRConJmp 13CsteNb 30SetVar yGetVar yGetVar xCsteNb 3SubsNbGrStNbConJmp 5GetVar yGetVar xSubsNbSetVar yJump -17Halt
PC
Code
Pile
Contexts
12
x
foo
True
y
42.5
CC
0
z
b
clot(w)
a
Calcul
12.5
x
bar
clot(w)
y
objet
12
continuation
30
Objets
d
objet
a
clot(w)
42
c
b
clot(w)
a
obj
d
clot(w)
a
obj
clot(x,y)
d
clot(w)
a
obj
42
c
b
clot(w)
a
obj
objet
False
ceux-ci sont des exemples,il peut y avoir beaucoup d'autres analyses sémentiques
(
(
limites floues entreanalyse sem. et backend
if_then_else
=
e
CondJmp
c1
Jump
c2
c2
c2
e
compiléesséparément
ou
et d'autresdepuis
CPU
CPU
ProgrammeExécuté
Execution dunouveauCompilateur
Code à compiler
.c
Nouveaucompilateur assemblé
.exe
Entrée
Sortie
Sortie
Entrée
CPU
Sortie
Entrée
Execution del'anciencompilateur
CPU
Sortie
Entrée
Anciencompilateur assemblé
.exe
Code assembleur
.asm
Plus Tard
Sortie
Grammaire du langage
.y / .mly
Code duparseur
.c / .ml
Génnérateur de parseur
.exe
Bizon / Camlyacc
Sortie
Entrée
CPU
Sortie
Entrée
Génnérateur de lexeur
Expressionsregulières
.l / .mll
Code dulexeur
.c / .ml
Main
.c / .ml
.exe
Lex /CamlLex
Sortie
Entrée
CPU
Sortie
Entrée
Copyright (C) 2020Flavien BreuvartLicence Creative Commons Paternité