Langages et Compilation

Unité 1: Introduction

Redouane EZZAHIR
[Link]@[Link]
R. Ezzahir (ENSA-Agadir)
27/02/2014 1
 Livres références

Pearson Education 2006 Addison-Wesley 1986

27/02/2014 R. Ezzahir (ENSA-Agadir) 2

 Plan d’aujourd’hui

 Compilateurs et interprètes

 Pourquoi étudier les compilateurs?

 Un peu d’historique

 Structure d'un compilateur

27/02/2014 R. Ezzahir (ENSA-Agadir) 3

 objectif

 Décrire la structure des compilateurs et les

interfaces des phases centrales.

 Donner des exemples de sorties des phases

de compilation.

 Poser des question comment réalisé chaque

tâche de compilateur ? Lesquelles peuvent
être obtenues par des générateurs?

27/02/2014 R. Ezzahir (ENSA-Agadir) 4

Compilateurs et interprètes
0xF100F

Programme Compilateur Cible 0xF1AAAF

0xF1CCA Sortie
Langage L1 Langage L2 0xF1FFF

Messages d'erreur
Données Off-line

On-line
Données
Interprète Sortie
Programme

Messages d'erreur

27/02/2014 R. Ezzahir (ENSA-Agadir) 5

 Pourquoi étudier les compilateurs?
Peu de gens écrivent des compilateurs comme profession.
Alors pourquoi apprendre à construire des compilateurs?

 Voir la théorie appliqué dans la vie.

 Savoir comment les langages de programmation sont construits et

comment fonctionnent.
 Connaitre le compromis dans la conception d’un langage de
programmation.

 La construction de compilateur vous rendra plus compétent en

programmation et en génie logiciel.
 Les compilateurs sont d’excellents exemples de grands systèmes
complexes qui peuvent être :
 Spécifiés rigoureusement,
 réalisés seulement en combinant théorie et pratique.

27/02/2014 R. Ezzahir (ENSA-Agadir) 6

 Un peu d’historique - la préhistoire (avant 1940)

 820 : Le mathématicien musulman Al Khawarizmi a publié à Bagdad un

traité intitulé “Abrégé du calcul par la restauration et la comparaison” qui
a beaucoup influencé le développement des mathématiques.

 1840 : Collaboratrice de Babbage, Ada Lovelace, mathématicienne, a

défini le principe des itérations successives dans l’exécution d’une
opération. En l’honneur Al Khawarizmi, elle a nommé le processus
logique d’exécution d’un programme : algorithme (déformation de Al
Khawarizmi). Ada Lovelace a traduit le mémoire du mathématicien italien
Luigi Menabrea sur la Machine analytique, la dernière machine proposée
par Charles Babbage.

 1854 : Boole a publié un ouvrage dans lequel il a démontré que tout

processus logique peut être décomposé en une suite d’opérations
logiques (ET, OU, NON) appliquées sur deux états (0-1, V-F).

27/02/2014 R. Ezzahir (ENSA-Agadir) 7

 Un peu d’historique – les années 40
 1943 : Le Plankalkül imaginé par Konrad Zuse (implémenté fin 90)

 1943 : Jean Bartik, l’une des programmeurs d'ENIAC, a conçu un langage

de programmation (BINAC) ainsi qu’un système électrostatique pour la
sauvegarde mémoire de l’UNIVAC UNIVAC I, le successeur de l’ENIAC.

 En 1945, un insecte coincé dans les circuits bloque le fonctionnement du

calculateur Mark I. La mathématicienne Grace Murray Hopper a décidé
alors que tout ce qui arrête le bon fonctionnement d’un programme
s’appellera BUG.

 Il faut noter que le terme BUG était déjà utilisé avant cela : Thomas Edison
par exemple avait employé ce terme dans un courrier où il parlait de la
mise au point problématique de l’une de ses inventions.

27/02/2014 R. Ezzahir (ENSA-Agadir) 8

 Un peu d’historique – les années 50

 1954 - IBM développe le 704

 Successeur du 701
 Premier ordinateur muni de capacité
d'arithmétique en virgule flottante
produit en grande quantité.
[Link]

 Clients : Coût logiciel >> coût matériel

 Comment pourraient-ils faire une programmation

plus productive?
27/02/2014 R. Ezzahir (ENSA-Agadir) 9
 Un peu d’historique – les années 50
[Link]

“Speedcoding”
 développé en 1953 par John Backus
 Un exemple précoce d'une interprète
 10-20 fois plus lent que l'assemblage écrit à
la main
 Occupe 30% de la mémoire

27/02/2014 R. Ezzahir (ENSA-Agadir) 10

 Un peu d’historique – les années 50
[Link]

“FORTRAN I”
 FORmula TRANslated (1954-1957)
 1958
 50% de Programmes en FORTRAN

27/02/2014 R. Ezzahir (ENSA-Agadir) 11

 Le premier compilateur

 Impact énorme sur l'informatique

 Conduit à un énorme corps de travail théorique
et pratique

 Les compilateurs modernes préserver

toujours les contours du FORTRAN I

 Alors quelle est la structure d’un

compilateur moderne ?
27/02/2014 R. Ezzahir (ENSA-Agadir) 12
 Structure d'un compilateur Code source

 Les compilateurs modernes

contiennent deux (grandes)
parties : Partie Frontale

 La partie frontale réalise l’analyse:

Découpe le programme source en Représentation
pièces constituantes et crée une
représentation intermédiaire (R.I). Intermédiaire

 La partie finale réalise la synthèse:

Génère le programme cible de la Partie Finale
représentation intermédiaire.

Code machine M
27/02/2014 R. Ezzahir (ENSA-Agadir) 13
Structure d'un compilateur
Code Source
(Flux de caractères)
Analyse Lexicale
Flux de Token
Analyse syntaxique
Table de Partie Frontale
symboles (Indépendante de la
Analyse symantique machine)

Arbre syntaxique Abstrait

Génération de Code Intermédiaire O(n) ou

O(n log n)
Code Intermédiaire
Optimisation R.I

Code Intermédiaire Partie finale

génération de Code (dépendante de la
machine)
Code Cible Optimisation de Code NP-Complete

27/02/2014 R. Ezzahir (ENSA-Agadir) 14

 Les phases d'analyse
 Consiste à partitionner le
Analyse Lexicale programme source, qui est sous
forme d'une suite de caractères,
Analyse en un suite de mots ou unités
Syntaxique lexicales.
Table de
Analyse Exemple: symboles
Sémantique
position := initial + rate * 60 1 position
Génération RI 2 initial
id(1) aff id(2) add id(3) mul nbr(60) 3 rate

Optimisation RI
 Détecte des erreurs telles que
Génération de
• Identificateurs trop longs ou illégaux
code
• Caractères ou nombres illégaux.
Optimisation de
code

27/02/2014 R. Ezzahir (ENSA-Agadir) 15

 Les phases d'analyse
 L'analyse syntaxique consiste
Table de d'une part à reconnaître si la suite
symboles Analyse Lexicale
1 position
de mots forme une phrase correcte
2 initial
Analyse
et d'autre part à construire l'arbre
3 rate
Syntaxique syntaxique abstrait du code source.
Analyse :=
Sémantique
<id, 1> +
Génération RI

Optimisation RI <id, 2> *

<id, 3> <nbr, 60>
Génération de
code  Détecte des erreurs telles que
Optimisation de • Parenthèses non fermées,
code
• Manque de délimiteurs
27/02/2014 R. Ezzahir (ENSA-Agadir) 16
 Les phases d'analyse
 Vérifier si certaines règles liées à la
Table de signification des programmes en un
symboles Analyse Lexicale langage donné sont respectées.
1 position
2 initial  les identificateurs apparaissant dans les
3 rate
Analyse Syntaxique expressions ont-ils été déclaré?
 les opérandes ont-ils les types requis par
Analyse les opérateurs ?
Sémantique
 les conversions de types requis à ont-ils
Génération RI été inséré?
:=
Optimisation RI
<id, 1> +
Génération de code
<id, 2> *
Optimisation de <id, 3> Integer-to-real
code
<nbr, 60>
27/02/2014 R. Ezzahir (ENSA-Agadir) 17
 Représentation intermédiaire
 Le compilateur génère ici un
Table de
symboles Analyse Lexicale code intermédiaire à partir de
1 position
2 initial
l’arbre syntaxique. Ce code est
Analyse Syntaxique
3 rate le code d’une machine
Analyse abstraite.
Sémantique
Génération RI
t1 = inttofloat(60)
Optimisation RI
t2 = id3 * t1
Génération de code
t3 = id2 + t2
id1 = t3
Optimisation de
code

27/02/2014 R. Ezzahir (ENSA-Agadir) 18

 Représentation intermédiaire
 Analyses plus ou moins poussées pour
Table de signaler :
symboles Analyse Lexicale
 les risques d’erreur à l'exécution ;
1 position
 les opportunités d’optimisation.
2 initial
3 rate
Analyse Syntaxique
Analyse de flot de données :
Analyse  propagation de constantes ;
Sémantique  indication des variables non initialisées/non
Génération RI utilisées ;
 élimination du code mort ;

Optimisation RI  factorisation d’invariants de boucle ;

 limitation de calculs redondants.

Génération de code
t1 = inttofloat(60)
Optimisation de t2 = id3 * t1 t1 = id3 * 60.0
code t3 = id2 + t2 id1 = id2 + t1
id1 = t3

27/02/2014 R. Ezzahir (ENSA-Agadir) 19

 Les phases de synthèse
 Cette phase nécessite la connaissance de la
machine cible (réelle, virtuelle ou abstraite), et
Table de
symboles Analyse Lexicale notamment de ses possibilités en matière de
1 position registres, piles, etc.
2 initial
3 rate
Analyse Syntaxique  Elle utilise les adresses calculées par
l'allocation et sélectionne le code.
Analyse
Sémantique t1 = id3 * 60.0
Génération RI id1 = id2 + t1

Optimisation RI

Génération de code MOVF id3, r2

MULF *60.0, r2
MOVF id2, r2
Optimisation de
ADDF r2, r1
code
MOVF r1, id1

27/02/2014 R. Ezzahir (ENSA-Agadir) 20

 Les phases de synthèse
Table de À cette étape, on tente d’améliorer le
symboles Analyse Lexicale
code pour le rendre plus rapide à
1 position
2 initial
Analyse Syntaxique
l’exécution et/ou moins encombrant en
3 rate
mémoire.
Analyse
Sémantique
Génération RI

Optimisation RI

Génération de code

Optimisation de
code

27/02/2014 R. Ezzahir (ENSA-Agadir) 21

 Vue d’ensemble

27/02/2014 R. Ezzahir (ENSA-Agadir) 22

27/02/2014 R. Ezzahir (ENSA-Agadir) 23
 ANNEXES

27/02/2014 R. Ezzahir (ENSA-Agadir) 24

 Outils de construction de compilateurs

 Générateurs d’analyseurs lexicaux (JFlex, Flex, ..)

 Générateurs d’analyseurs syntaxiques (Cup, Ycc, ..)

 Outils de traduction orientée-syntaxe

 Engins de flot de données

 Générateurs de générateurs de code

27/02/2014 R. Ezzahir (ENSA-Agadir) 25

Translation d’un Programme en Code Exécutable

Programme C Compilateur Langage Assembleur

(Data) (Prog. Sys.) Code (Data)

Langage Machine Assembleur

Object Code (Data) (Prog. Sys.)

Bibliothèque
Langage Machine Linker
Langage Machine
Code Exécutable (Data) (Prog. Sys.)
Object Code (Data)

Programme en
Loader
Mémoire
(Prog. Sys.)
centrale

27/02/2014 R. Ezzahir (ENSA-Agadir) 26

Préprocesseurs (Exemple langage C)
Traitement des macros #define
Inclusion de fichiers #include
Extensions de langages #ifdef
Les définitions de macros permettent l'utilisation de paramètres. Par exemple, en
TEX, une définition de macro a la forme
\define <nom> <modèle>{<corps>}
Par exemple, si on définit :
\define\JACM #1;#2;#3.
{{\sl [Link]} {\bf #1}:#2, pp. #3}
et si on écrit
\JACM 17;4;715-728
on doit voir
[Link] 17:4, pp. 715-728
 L’assembleur

L’assembleur est un programme qui traduit en langage machine le

programme source écrit en langage d’assemblage.

 Macroassembleur et cross-assembleur
Une macro-instruction ou macro est une séquence d’instructions à
laquelle on attribue un nom. Ensuite, chaque fois qu’on utilise ce nom
dans le programme, l’assembleur le remplace par la séquence
d’instructions en question. Un assembleur qui autorise l’utilisation de
macros est appelé un macro-assembleur.

27/02/2014 R. Ezzahir (ENSA-Agadir) 28

 Macroassembleur et cross-assembleur
Un cross-assembleur traduit un programme source en un pro-
gramme objet pour une machine autre que celle sur laquelle il effectue
la traduction.
Un macroassembleur permet la création et l’utilisation de macros
dans le code source. Une macro est un nom qu’on donne à un groupe
d’instructions qui revient souvent dans un programme. On peut ensuite
remplacer chaque occurrence de ce groupe par son nom, ce qui peut
rendre le code source plus lisible.

27/02/2014 R. Ezzahir (ENSA-Agadir) 29

Langages d’assemblage
Les langages d’assemblage ou assembleurs sont des versions un
peu plus lisibles du code machine avec des noms symboliques
pour les opérations et pour les opérandes
MOV a, R1
ADD #2, R1
MOV R1, b
Chaque processeur a son langage d'assemblage
Les langages d'assemblage d'un même constructeur se
ressemblent
Assemblage
L’assemblage consiste à traduire ce code en code binaire
La forme la plus simple est l’assemblage en deux passes

Première passe
On crée une table des symboles (distincte de celle du compilateur)
pour associer des adresses mémoires aux identificateurs
identificateur adresse
a 0
b 4
Assemblage
Deuxième passe
On crée du code machine relogeable c’est-à-dire relatif à l’adresse
mémoire L où il commence
Les instructions précédentes peuvent être traduites en :
0001 01 00 00000000 *
0011 01 10 00000010
0010 01 00 00000100 *

La table des symboles de l'asssembleur sert aussi à l'édition de

liens
Elle permet de remplacer les références à des noms externes
Langages machines
Chaque processeur a son langage

Exemples d'instructions binaires

0001 01 00 00000000 *
0011 01 10 00000010
0010 01 00 00000100 *
Les 4 premiers bits : code de l’instruction
0001 = charger
0011 = ajouter
0010 = sauvegarder
Les 2 bits suivants : registre
Langages machines
Les 2 bits suivants : mode d’adressage
00 = mode adresse
10 = mode littéral
L’étoile (bit de translation) indique que l’adresse L doit être ajoutée
aux opérandes. Si L = 00001111, c’est-à-dire 15, a et b doivent
être placés en 15 et 19
Code absolu obtenu :
0001 01 00 00001111
0011 01 10 00000010
0010 01 00 00010011
 L’éditeur de liens

L’éditeur de liens (linker ou link editor) est un logiciel qui permet de

combiner plusieurs programmes objets en un seul.

On structure les gros programmes en modules que l’on traduit

indépendamment. Ainsi, un programme peut être constitué de
plusieurs fichiers contenant chacun un ou plusieurs sous-program-
mes. Tous ces fichiers sont traduits séparément, mais peuvent utiliser
les sous-programmes et les variables se trouvant dans les autres
fichiers, ce qui donne lieu à des références externes.

L’éditeur prend ces différents morceaux de programme et les groupe

pour former un programme complet et exécutable.

27/02/2014 R. Ezzahir (ENSA-Agadir) 35

 Le Chargeur

Le programme objet, obtenu après l’édition de liens, doit encore être
chargé en mémoire centrale pour être exécuté. Le chargeur s’occupe
de cette tâche. Dans les systèmes d’exploitation moder-nes, on décide
au dernier moment à quelle adresse charger le programme, puisque
plusieurs programmes peuvent résider simul-tanément en mémoire.

Dans les anciens systèmes (comme DOS), on pouvait fixer les

adresses à l’avance et charger le programme à l’endroit spécifié. On
utilisait donc un chargeur absolu.

Aujourd'hui, les chargeurs s’occupent de reloger les programmes en

mémoire centrale. Ce sont des chargeurs relogeables.

27/02/2014 R. Ezzahir (ENSA-Agadir) 36

 Le débogueur

Le débogueur (debugger) est un logiciel qui facilite la mise au point

de programmes et la correction des erreurs ou bogues (bugs). Il
permet d’examiner le contenu de la mémoire ainsi que celui des
différents registres du processeur.

Il permet également de créer des points d’arrêt (breakpoints) lors de

l’exécution du programme à mettre au point, et à partir de ces points
d’arrêt, d’exécuter le programme pas à pas, i.e. instruction par
instruction tout en observant le contenu des registres, des variables et
de la mémoire.

27/02/2014 R. Ezzahir (ENSA-Agadir) 37

Compilation d’un programme C
Si on compile par gcc –S essai.c le fichier suivant :

#include <stdio.h>

int main(void) {
printf("bonjour\n") ; }

on obtient de l'assembleur 8086 avec

- epb pour base pointer
- esp pour stack pointer
- pushl pour push long
etc.
 .file "essai.c"
.version "01.01"
gcc2_compiled:
.section .rodata
.LCO:
.string "bonjour\n"
.text
.align 16
.globl main
.type main,@function
main:
pushl %ebp
movl %esp, %ebp
subl $8, %esp
subl $12, %esp
pushl $.LCO
call printf
addl $16, %esp
movl %ebp, %esp
popl %ebp
ret
.Lfe1:
.size main,.Lfe1-main
.ident "GCC: (GNU) 2.96 20000731 (Linux-Man