Principe et fonctionnement des
systèmes d’exploitation
NFA003, 4 ECTS
Séance 3
La compilation
Le plus grand soin a été apporté à la réalisation de ce support pédagogique afin de vous fournir une
information complète et fiable. Cependant, le Cnam Champagne-Ardenne n'assume de responsabilités,
ni pour son utilisation, ni pour les contrefaçons de brevets ou atteintes aux droits de tierces personnes
qui pourraient résulter de cette utilisation.
Les exemples ou programmes présents dans cet ouvrage sont fournis pour illustrer les descriptions
théoriques. Ils ne sont en aucun cas destinés à une utilisation commerciale ou professionnelle.
Le Cnam ne pourra en aucun cas être tenu pour responsable des préjudices ou dommages de quelque
nature que ce soit pouvant résulter de l'utilisation de ces exemples ou programmes.
Tous les noms de produits ou autres marques cités dans ce support sont des marques déposées par
leurs propriétaires respectifs.
Ce support pédagogique a été rédigé par Nils Schaefer, formateur au Cnam Champagne-Ardenne.
Copyright Ó 2010-2011 - Cnam Champagne-Ardenne.
Tous droits réservés.
L'utilisation du support pédagogique est réservée aux formations du Cnam Champagne-Ardenne. Tout
autre usage suppose l'autorisation préalable écrite du Cnam Champagne-Ardenne.
Toute utilisation, diffusion ou reproduction du support, même partielle, par quelque procédé que ce soit,
est interdite sans autorisation préalable écrite du Cnam Champagne-Ardenne. Une copie par
xérographie, photographie, film, support magnétique ou autre, constitue une contrefaçon passible des
peines prévues par la loi, du 11 mars 1957 et du 3 juillet 1995, sur la protection des droits d'auteur.
Edition du 28 mars 2019
La compilation
La compilation est la phase la plus importante de la chaîne de production de programmes. Il convient
donc de bien maîtriser son fonctionnement et son utilité́.
1. Les langages de programmation
1.1. Qu’est-ce qu’un langage de programmation ?
Un langage de programmation informatique est un langage qui permet de donner à un ordinateur
l'ensemble des instructions qu'il doit exécuter. Comme n'importe quel langage, un langage de
programmation possède un ensemble de règles et de mots-clés. Le programmeur doit donc connaître
ces règles pour pouvoir donner des ordres à un système informatique.
Un programme est une suite d'instructions à exécuter dans un langage donné. Un programme exécutable
(fichiers .exe) est une suite d'instructions à exécuter données directement dans le langage du
processeur.
On distingue deux types de langages de programmation : les langages bas-niveau et les langages haut-
niveau.
1.2. Le langage machine
Le langage machine est le langage du processeur. Il s'agit d'un langage où chacune des instructions est
codée par un nombre.
Un programme écrit en langage machine est totalement illisible pour un humain mais il s'agit du seul
langage que le processeur peut comprendre. Le programmeur est donc obligé de produire un programme
en langage machine s’il veut pouvoir l'exécuter sur un ordinateur.
Notez bien qu'il n'existe pas qu'un seul langage machine. En principe, chaque processeur utilise un
langage qui lui est propre. Dans la pratique, il n'existe que quelques langages machines différents et les
processeurs d'une marque utilisent le même langage ou différentes versions qui restent toutefois
compatibles entre elles.
1.3. Les langages bas-niveau
Un langage bas-niveau est un langage qui est très proche du langage machine. Il peut éventuellement
être lisible par un humain mais reste toutefois difficile à comprendre.
On dit généralement que le langage machine est un langage de très bas-niveau. Il est important de
savoir que les langages bas-niveau ne sont presque plus utilisés à l'heure actuelle car ils sont complexes
et offrent une vision trop éloigné́ de celle du programmeur.
Le langage bas-niveau le plus connu est l'assembleur. Chacune des instructions du langage machine est
exprimée à l'aide de mnémoniques (mot-clé́ de taille réduite) et affiché sous une forme textuelle lisible
par un humain... Un programme écrit en assembleur n'en reste pas moins très difficile à comprendre et
n'est pas exécutable par le processeur.
Le passage du langage assembleur au langage machine n'est pas une phase de compilation, il s'agit tout
au plus d'un codage que l'on appelle assemblage. C'est la raison pour laquelle il est possible de passer
du langage assembleur au langage machine et vice-versa. L'opération inverse de l'assemblage est le
désassemblage. Il s'agit d'une pratique qui est interdite sur les applications commerciales car elle permet
La compilation 1 / 10
aux programmeurs qui maitrisent l'assembleur d'étudier le code de l'application et donc ses éventuelles
failles.
1.4. Les langages haut-niveau
Un langage de haut-niveau est un langage plus proche de la manière de penser d'une personne humaine.
Il s'agit d'un langage qui est indépendant de la machine et du processeur.
Un langage de programmation de haut-niveau est structuré, il dispose d'un alphabet (ensemble de
symboles utilisables), de différents identificateurs (groupes de symboles de l'alphabet), de différentes
instructions.
Un programme écrit en langage haut-niveau n'est pas exécutable. Pour devenir exécutable il faut qu'il
soit compilé. La compilation est une phase beaucoup plus complexe que l'assemblage qui doit être
réalisée par un programme de conception évoluée.
2. La phase de compilation
Lorsqu'un programme est écrit dans un langage de programmation quelconque (autre que le langage
machine), on parle de code source. Il s'agit donc d'un programme non exécutable destiné à être compilé.
La phase de compilation réalise la traduction du code source pour obtenir du code objet. Il s'agit
d'instructions en langage machine qui ne sont pas encore stockées sous la forme d'un fichier exécutable
car une phase supplémentaire est nécessaire : il s'agit de l'édition de liens.
La plupart du temps, lorsqu'on parle de « compilation », on fait référence à l'ensemble des outils de la
chaîne de production permettant de produire un fichier exécutable à partir du code source. Il faut bien
faire la distinction avec la phase de compilation que nous sommes en train d'étudier.
La phase de compilation est composée de trois phases :
ü L'analyse lexicale
ü L'analyse syntaxique
ü L'analyse sémantique
Chacune de ces trois phases peut se solder par un échec rendant la compilation impossible. Pour obtenir
le code objet d'un programme il faut que chacune de ces trois phases se déroule correctement. Une
seule erreur empêche la génération du code objet.
Lors de la compilation, il est également possible d'obtenir des avertissements (warning en anglais). Ces
derniers n'empêchent pas la compilation de se terminer normalement. Il s'agit uniquement d'avertir le
programmeur sur certains points du programme qui semblent étranges. Il existe plusieurs niveaux
permettant de soulever plus ou moins d'avertissements en fonction de la qualité́ du programme que l'on
souhaite obtenir.
2.1. L'analyse lexicale
Le code source d'un programme est un fichier en mode texte dans lequel sont présents différents
symboles ayant tous (normalement) une signification particulière dans le langage de programmation.
L'analyseur lexical travail sur les caractères du fichier et cherche à reconnaitre les symboles du langage.
Chacun de ces symboles est ensuite codé par l'analyseur lexical à l'aide d'une représentation interne.
L'objectif est de trouver le début et la fin de tous les symboles. Bien entendu, l'analyseur lexical supprime
dans un premier temps les commentaires présents dans le code source. C'est la raison pour laquelle ces
derniers peuvent contenir plus ou moins n'importe quoi.
NFA004 : Architecture des machines 2 / 10
Voici un exemple de langage :
Symboles du langage Suite de caractères associée
Identificateur Lettre suivie de lettres et/ou chiffres
Nombre entier Chiffres
Opérateur +, -, >, <, >=, <=, =, .
Séparateur Espace, tabulation, fin de ligne
Voici les interprétations de différentes suites de caractères dans ce langage :
Suites de caractères Symboles reconnus
toto+tutu Identificateur (toto), opérateur (+), identificateur (tutu)
Analyse lexicale correcte
a=56+56 Identificateur (a), opérateur (=), nombre entier (56), opérateur (+), nombre
entier (56)
Analyse lexicale correcte
id+-56 67 Identificateur (id), opérateur (+), opérateur (-), nombre entier (56), nombre entier
(67)
Analyse lexicale correcte
5t=toto56 Symbole non reconnu (5t), opérateur (=), identificateur (toto56)
Analyse lexicale incorrecte
5 t = toto 56 Nombre entier (5), identificateur (t), opérateur (=), identificateur (toto),
nombre entier (56)
Analyse lexicale correcte
toto ? titi Identificateur (toto), symbole non reconnu (?), identificateur (titi) Analyse
lexicale incorrecte
Les espaces jouent un rôle important pour éviter une ambiguïté́. On voit bien que les opérateurs peuvent
+ et - sont bien interprétés comme étant séparés même s'ils ne sont séparés par aucun espace car il
n'existe pas d'opérateur +-. En revanche, lorsque les caractères 5 et t sont collés, ils sont généralement
interprétés comme une seule entité́. Bien entendu cela dépend de la configuration du compilateur et
plus précisément de son comportement vis-à-vis des espaces.
Pour définir une suite de caractères de manière plus formelle, on utilise les expressions régulières. Dans
une expression régulière on peut préciser les caractères attendus, leur répétition et d'autres contraintes.
Voici différentes expressions régulières :
Expressions régulières Symboles acceptés
a+ a, aa, aaa, aaaa, aaaaa ...
a* ∅, a, aa, aaa, aaaa, aaaaa ...
(a | b) a, b
a ( b | c)* d+ abd, acd, abcd, abbbddd, abcbd, abbccdd ...
∅ : Absence de caractère
Voici maintenant le langage présenté́ plus haut écrit avec des expressions régulières :
La compilation 3 / 10
Symboles du langage Expression régulière associée
Lettre ( a | b | c | ... | z | A | B | C | ... | Z )
Chiffre (0|1|2|3|4|5|6|7|8|9)
Identificateur ( Lettre ) ( Lettre | Chiffre )*
Nombre entier ( + | - | ∅ ) ( Chiffre )+
Opérateur ( + | - | > | < | >= | <= | = | . )
Séparateur (Espace | Tabulation | Fin de ligne )
Il est même possible d'ajouter des symboles plus complexes à notre langage :
Symboles du langage Expression régulière associée
Nombre hexadécimal 0x ( Chiffre | a | ... | f | A | ... | F )+
Nombre à virgule ( + | - | ∅ ) ( Chiffre )* ( . ( Chiffre )* | ∅ )
( ( e | E ) (+ | - | ∅ ) ( Chiffres )+ | ∅ )
Avec ce langage, l'analyseur lexical est capable de reconnaitre les nombres à virgules suivants :
ü 34. soit 34
ü 89.2e3 soit 89,2 x 103
ü -.56E-5 soit – 0,56 x 10-5
ü -56.78e9 soit – 56,78 x 109
La structure lexicale d'un langage de programmation doit être non ambiguë̈. En effet, l'analyseur lexical,
n'est pas capable de choisir entre plusieurs symboles possibles pour une même suite de caractères, il ne
doit donc pas avoir à faire ce choix... En revanche, lorsque deux règles peuvent être utilisées à un endroit
donné, il faut utiliser la règle qui permet d'associer la plus grande suite de caractères à un symbole. Un
langage est ambigu si l'analyseur lexical se retrouve avec deux règles qui peuvent s'appliquer à la même
suite de caractères.
Voyons un exemple pour éclaircir cette explication... On suppose que l'analyseur lexical doit interpréter
la suite de caractères suivante :
toto=56.67
Si l'analyseur n'est pas obligé de choisir la règle la plus grande, voici différentes interprétations possibles
:
ü Identificateur (to), identificateur (to), opérateur (=), nombre entier (56), opérateur (.), nombre
entier (67)
ü Identificateur (toto), opérateur (=), nombre à virgule (56.67)
Il est clair que seule la deuxième possibilité́ est valable si on oblige l'analyseur lexical à utiliser la plus
grande suite de caractères possible.
Par analogie, l'analyse lexicale est similaire à la recherche de mots dans un texte de langue française.
L'analyse lexicale est correcte si tous les mots du texte sont des mots appartenant à la langue française.
Pour générer un analyseur lexical adapté à un langage il faut utiliser un générateur d'analyseur lexical.
Sous Unix, il existe le logiciel lex ainsi que son équivalent sous Linux nommé flex.
NFA004 : Architecture des machines 4 / 10
2.2. L'analyse syntaxique
L'analyse syntaxique a pour objectif de vérifier pour chacune des instructions si elle est syntaxiquement
correcte. L'analyseur syntaxique est lancé uniquement si l'analyse lexicale est correcte pour chacun des
symboles. De ce fait, les instructions sur lesquelles travaille l'analyseur syntaxique sont obligatoirement
lexicalement correctes.
Pour étudier la syntaxe des différentes instructions, l'analyseur syntaxique a besoin d'un ensemble de
règles de production. Ces règles de production indiquent comment construire une instruction
syntaxiquement correcte à partir de plusieurs symboles. L'analyse syntaxique consiste à retrouver pour
chaque instruction les différentes règles qui doivent être utilisées pour que cette instruction soit
syntaxiquement correcte. Si ce n'est pas possible, cela signifie que l'instruction n'est pas syntaxiquement
correcte.
La syntaxe doit être non ambiguë̈. Il ne doit donc pas être possible d'utiliser deux manières différentes
de décomposer une instruction.
La syntaxe doit également être indépendante du contexte. L'analyse syntaxique ne doit pas essayer
d'analyser l'instruction par rapport à son sens dans le programme complet.
Les règles de production sont définies par les formes normales de Backus-Naur. Voici les différentes
fonctionnalités disponibles pour créer les règles de production :
ü <...> : ces symboles permettent de définir une dénomination syntaxique.
ü ::= : ce symbole permet d'indiquer la réécriture d'une dénomination syntaxique.
ü | : ce symbole représente une alternative (ou).
ü (…) : contenu non répété
ü {...} : ce symbole représente un contenu répété́ 0 fois, une fois ou plus.
ü [...] : ce symbole représente un contenu répété́ 0 ou une fois.
ü "…" : le contenu est une chaîne de caractère et n’est pas compris comme faisant partie de la syntaxe
de Backus-Naur.
ü * : représente un symbole de répétition. Par exemple, pour "a"*3, le texte "a" est répété trois fois.
Voici un exemple de syntaxe définie à l'aide de formes normales de Backus-Naur :
ü <expression> ::= <facteur> | <facteur> <op add> <expression> (1)
ü <facteur> ::= <terme> | <terme> <op mult> <facteur> (2)
ü <terme> ::= <identificateur> | <nombre> | "("<expression>")" (3)
ü <opadd>::="+"|"-" (4)
ü <opmult>::="*"|"/" (5)
Nous allons utiliser cette syntaxe pour analyser l'expression : 23 x 2 + 5
L'analyse lexicale de cette instruction, nous donne le résultat suivant :
Terme (23), op mult (x), terme (2), op add (+) et terme (5)
Pour commencer l'analyse syntaxique, on part toujours d'une dénomination syntaxique de base. Ici il
s'agit de la dénomination « expression ». Cela revient à dire que chaque instruction à analyser est
toujours une expression.
A partir de là, l'analyseur va maintenant essayer d'utiliser les règles de réécriture pour trouver
l'organisation syntaxique de l'expression. Dans notre exemple, il se trouve que la règle 1 peut être
utilisée. Nous allons donc utiliser cette réécriture :
La compilation 5 / 10
<expression> ::= <facteur> <op add> <expression>
Au niveau de l'analyseur syntaxique cela donne le résultat intermédiaire suivant :
Pour parvenir au résultat final, il faut continuer à utiliser les règles de production jusqu'à ce qu'on
parvienne à obtenir la suite de symboles identifiée par l'analyseur lexical.
L'analyseur syntaxique va utiliser les règles de réécritures suivantes :
ü <facteur> ::= <terme> <op mult> <facteur>
ü <op add> ::= +
ü <expression> ::= <facteur>
L'analyseur syntaxique va utiliser les règles de réécritures suivantes :
ü <terme> ::= <nombre>
ü <facteur> ::= <terme>
ü <facteur> ::= <terme>
NFA004 : Architecture des machines 6 / 10
L'analyseur syntaxique va utiliser les règles de réécritures suivantes :
ü <terme> ::= <nombre>
ü <terme> ::= <nombre>
L'expression est syntaxiquement correcte car l'analyseur syntaxique a réalisé́ l'arborescence permettant
de partir de la dénomination « expression » en arrivant à la décomposition de l'analyseur lexical.
Dans le résultat obtenu, la structure de l'arbre fait bien apparaitre la priorité́ de la multiplication sur
l'addition. En effet, la décomposition syntaxique de l'expression va permettre son évaluation (connaître
sa valeur).
Par analogie, l'analyse syntaxique cherche à savoir si une phrase composée de mot existant est
syntaxiquement correcte. Cette phrase est correcte si les mots sont placés dans un ordre particulier qui
respecte une grammaire.
Pour générer un analyseur syntaxique adapté à un langage il faut utiliser un générateur d'analyseur
syntaxique. Sous Unix, il existe le logiciel yacc ainsi que son équivalent sous Linux nommé bison.
La compilation 7 / 10
2.3. L'analyse sémantique
L'analyse sémantique a pour objectif de référencer les différentes entités manipulées afin de contrôler
leur utilisation dans le programme.
Il s'agit dans un premier temps de détecter le type des différentes variables en cherchant d'éventuelles
déclarations de variables. Il faut également détecter la durée de vie de toutes les variables. Sont-elles
globales (utilisable dans tout le programme) ou locales (utilisable dans une partie du programme) ? A
quelle partie du programme une variable locale appartient-elle (fonction, bloc de code, ...) ?
Un des objectifs de l'analyse sémantique est de mesurer les besoins en espace en mémoire du
programme. Pour cela il faut prendre en compte le type de chacune des variables.
L'analyseur sémantique doit aussi analyser les utilisations qui sont faites de chaque variable. L'objectif
est de s'assurer que chacune de ces utilisations est correcte.
Par analogie, l'analyse sémantique cherche à savoir si les phrases (syntaxiquement correctes) utilisées
dans un texte forment un ensemble cohérent. Le texte est sémantiquement correct si les phrases
utilisées ensembles forment une suite logique qui a un sens.
2.4. La table des symboles
La table des symboles est construite durant les phases d'analyse lexicale et sémantique. Elle liste les
entités utilisées dans le programme et stocke leurs paramètres (nom, type, taille).
Lors de l'analyse lexicale, la table des symboles est remplie avec les différents identifiants rencontrés.
Aucune information relative au type ou à la taille des données n'est renseignée.
Lors de l'analyse sémantique la table des symboles est complétée par le type et la taille de chacune des
variables.
2.5. Génération de code
Après avoir réalisé́ les trois étapes, le compilateur peut maintenant produire le code objet. Ce dernier
est composé d'instructions en langage machine mais n'est pas encore sous la forme d'un fichier
exécutable.
Lors de la génération de code objet, toutes les constantes et variables globales sont converties en
adresses et sont placées dans le segment de données. Il s'agit de la zone qui contient les données
utilisées par le programme. Les instructions en langage machine sont stockées dans le segment de code.
Le segment de données est indexé à l'adresse 0 et le segment de code est placé à la suite.
Deux compilateurs différents ne vont pas produire un fichier identique à partir du code source. Chaque
compilateur travaille d'une manière un peu différente et utilise ses propres méthodes pour traduire
chaque instruction de code source en instructions en langage machine. L'optimisation du code objet
produit mesure la qualité́ d'un compilateur par rapport à un autre.
3. Les langages compilés et interprétés
Ces deux types de langages étant très répandus, il est important de bien comprendre leur signification.
NFA004 : Architecture des machines 8 / 10
3.1. Les langages compilés
Un langage est un langage compilé lorsqu'à partir du code source, un compilateur se charger de produire
un programme exécutable. Pour schématiser la production d'un programme exécutable avec un langage
compilé jusqu'à son exécution, on peut distinguer les différentes étapes suivantes :
ü Écriture du code source
ü Traduction du code source en code objet puis en code exécutable
ü Exécution du code exécutable
Le code exécutable est produit pour un système d'exploitation et pour une famille de processeurs Il est
donc nécessaire de compiler, une nouvelle fois, le code source pour obtenir un nouvel exécutable.
Voici une liste de langages compilés :
ü C
ü C++
ü Pascal
ü Delphi
ü ...
3.2. Les langages interprétés
Un langage est un langage interprété́ lorsqu'il n'y a pas de génération de code exécutable et donc pas
de phase de compilation. Le code source n'étant pas exécutable, le programme doit être exécuté́ par un
interpréteur. Il s'agit d'un programme qui connaît le langage et qui le lit et exécuté chacune des
instructions. Pour schématiser la production d'un programme exécutable avec un langage interprété́
jusqu'à son exécution, on peut distinguer les différentes étapes suivantes :
ü Écriture du code source
ü Traduction/Exécution instruction par instruction
Le code source est au format texte il peut donc être lu sur n'importe quel système d'exploitation et de
ce fait exécuté́ sur n'importe quel système d'exploitation qui dispose d'un interpréteur.
Voici une liste de langages interprétés :
ü PHP
ü Python
ü Javascript
ü Perl
ü Scheme
ü ...
3.3. Un langage compilé pour une machine virtuelle
Notez que le langage Java est un langage semi-compilé, le code source Java subit une phase de
compilation qui ne produit pas un fichier exécutable mais qui « mâche » le travail pour l'interpréteur
Java (JVM, Java Virtual Machine, machine virtuelle Java).
Microsoft s’est fortement inspiré du langage Java pour créer le langage C# qui est maintenant intégré́ à
sa suite Visual Studio.
La compilation 9 / 10
3.4. Comparaison
Il est nécessaire de bien comprendre que chacun de ces deux types de langages est intéressants dans
le cadre d'une utilisation particulière.
Les langages compilés sont plus rapides car il n'y a plus aucune étape de traduction du code.
Les langages interprétés sont plus lents mais ils peuvent être exécutés sur n'importe quelle plate- forme
disposant d'un interpréteur.
NFA004 : Architecture des machines 10 / 10