Structure d'un Compilateur

est formée de :

. L'identificateur E

. L'opérateur d'affectation = . L'identificateur m

Structure d’un Compilateur

5

. L'opérateur de multiplication *

. L'identificateur c

(ii) D'autre part, on détecte les erreurs lexicales, i.e., les erreurs qui se produisent au niveau de

l'écriture d'un identificateur. Cependant, la détection d'une erreur durant une phase n'arrête pas la

compilation, on passe à la phase suivante afin de détecter le maximum d'erreurs durant la

compilation.

Exemple 2 : Voici des exemples d’erreurs lexicales en C: 1x, a&, whle, doo, …

Les outils utilisés par un compilateur pour faire l’analyse lexicale sont les expressions

régulières et les automates à états finis.

1.2. Analyse Syntaxique

Durant l’étape de l’analyse syntaxique, le compilateur :

(i) D'une part, génère les arbres syntaxiques associées aux différentes expressions: Ce sont des

arbres binaires dont les nœuds internes sont des opérateurs et les feuilles sont des opérandes.

L'insertion des opérateurs dans l'arbre se fait de haut en bas en partant de l'opérateur le plus

prioritaire et en allant vers l'opérateur le mois prioritaire, e.g., = est plus prioritaire que * et +, et *

est plus prioritaire que +.

Exemple 3 : L'arbre syntaxique associée à l'instruction de l'Exemple 1 est le suivant:

(ii) D'autre part, détecte les erreurs syntaxiques, i.e., les erreurs qui se produisent au niveau de

l'écriture d'une expression, i.e., une séquence d'identificateurs et d'opérateurs représentant une

opération à réaliser.

Exemple 4 : Voici des exemples d’erreurs syntaxiques en C: x=y++2, z=* x *, f(a,b, …

Les outils utilisés par le compilateur pour faire l’analyse syntaxique sont les grammaires et les

automates à pile.

= E * m * c c

Structure d’un Compilateur

6

1.3. Analyse Sémantique

Durant l’étape d’analyse sémantique, le compilateur :

(i) D'une part, fait les contrôles suivants:

(i.i) Contrôle de type: on vérifie le type des variables impliquées dans une expression. (i.ii) Contrôle de structures des structures de contrôle: on vérifie si les structures if … else,

while … do, for …, etc. ont la bonne structure.

(i.iii) Contrôle de l'unicité: on vérifie qu'un identificateur est déclaré une et une seule fois

dans le même bloc.

(i.iv) Contrôle de l'utilisation d'un identificateur: on vérifie si un identificateur a été déclaré et

utilisé correctement.

(ii) D'autre part, détecte les erreurs sémantiques, i.e., les erreurs obtenues suite aux contrôles

précédents

Exemple 5 : Voici des exemples d’erreurs sémantiques en C :

(a)

x=t[2.5],

où t est un tableau. L'indice 2.5 est n'est pas un entier (contrôle (i.i)).

(b)

(i=1; i<10; i++)

{x=x+1}

où i est un entier. Il manque for (contrôle (i.ii)).

(c)

int x;

float x;

x est déclarée deux fois (contrôle (i.iii)).

(d)

x=y/0;

Division par 0 (contrôle (i.iv)).

Les outils utilisés par le compilateur pour faire l’analyse sémantique sont les traductions

dirigées par la syntaxe.

2. PHASE DE SYNTHESE

La phase de synthèse se décompose en deux étapes :

(i) La génération de code

(ii) Et l’optimisation de code

2.1. Génération de Code

La génération de code consiste à générer à partir des arbres syntaxiques, générés durant la phase d'analyse, la version en langage d'assemblage, i.e., un langage dont les instructions sont des

Structure d’un Compilateur

7

instructions élémentaires, faisant appel à des opérations élémentaires comme le chargement

(MOV), la multiplication (MUL), l'addition (ADD), la soustraction (SUB) et le branchement

(GOTO). La génération de code se fait en deux temps:

(i) En un premier temps, on génère des instructions pour une machine abstraite (virtuelle) qui

fait abstraction des architectures des machines réelles existantes. Ainsi, on s'attache plus aux

principes de traduction et aux concepts des langages qu'à l'architecture des machines.

(ii) En un second temps, on traduit les instructions destinées à la machine virtuelle en des

instructions destinées à la machine réelle existante sur laquelle on veut exécuter le programme.

Ainsi, le portage du programme sera facilité car la traduction en code cible virtuel sera faite une

fois pour toutes, indépendamment de la machine cible réelle. Il ne reste plus ensuite qu'à étudier les

problèmes spécifiques à la machine cible, et non plus les problèmes de reconnaissance du

programme.

2.2. Optimisation de Code

Durant cette étape, le compilateur tente d’optimiser le code machine produit de telle sorte que le

programme résultant soit plus rapide. Il y a des optimisations qui ne dépendent pas de la machine

cible réelle telles que l’élimination de calculs inutiles, l’élimination du code d'une fonction jamais

appelée, la propagation des constantes et l’extraction des invariants de boucles. Et il y a des

optimisations qui dépendent de la machine cible réelle telles que le remplacement des instructions

générales par des instructions plus efficaces et plus adaptées et l'utilisation optimale des registres.

Exemple 6 : Voici la traduction, en langage d'assemblage du microprocesseur Intel 8088, de

l'instruction C de l'exemple 1. Cette traduction a été faite à partir de l'arbre syntaxique présenté dans

l'exemple 3.

MOV AX c

(charger c dans l'accumulateur AX)

IMUL c

IMUL m

(multiplier c par le contenu de AX, le résultat se trouvera dans AX)

(multiplier m par le contenu de AX, le résultat se trouvera dans AX)

MOV E AX

(charger le registre AX dans E)

3. LES COLLABORATEURS DU COMPILATEUR

Une fois que le compilateur a finit de générer la version en langage d'assemblage d'un

programme, commence la tâche de l'assembleur.

3.1. L'Assembleur

L'assembleur est un programme qui génère, à partir de la version écrite en langage d'assemblage

d'un programme utilisateur, la version en langage machine, i.e., langage où tout est décrit par une

succession de bits.

En général un assembleur opère en deux étapes :

Structure d’un Compilateur

8

(i) Durant la première étape, l'assembleur fait une première lecture de la version en langage

d'assemblage du programme et entre les identificateurs rencontrés dans une table de symboles,

différente de celle générée par le compilateur. Chaque identificateur, lui est associé son adresse

mémoire.

identificateur

adresse

E

m

c

…

24

40

49

…

Table de symboles de l'assembleur

(ii) Et durant la seconde étape, l'assembleur fait une seconde lecture de la version en langage

d'assemblage du programme et traduit chaque instruction élémentaire en binaire. La traduction se

fait de la manière suivante:

(a) Chaque code opération, comme MOV, MUL, ADD, SUB et GOTO, est remplacé par son

code binaire.

(b) Chaque identificateur, comme E, c et m, est remplacé par son adresse mémoire, écrite

binaire. Cette adresse est récupérée à partir de la table de symboles, générée durant la première

étape.

(c) Chaque registre, comme AX, BX et BL, est remplacé par son numéro, écrit en binaire.

Exemple 7 : Voici une traduction, en langage machine, des instructions élémentaires de

l'exemple 6.

0011 0001 110001

MOV AX c

0001 110001

IMUL c

0001 101000

IMUL m

0011 11000 0001

MOV E AX

Structure d’un Compilateur

9

3.2. L’Éditeur de Lien

L’éditeur de lien est un programme qui accomplit deux tâches:

(i) La reliure: Il arrive que les codes machine des différentes fonctions et/ou procédures faisant

partie d'un programme soient définis dans plusieurs fichiers différents. D'autre part, il arrive aussi

que les données du programme doivent être lues à partir d'un ou plusieurs fichiers. La reliure

consiste donc à regrouper le code machine du programme principal, celui des différentes fonctions

et/ou procédures faisant partie du programme et ceux associés aux fichiers de données en un seul

code exécutable par le microprocesseur.

(ii) Le chargement: Il consiste à prendre le code machine généré par l'assembleur et le mettre

dans la RAM, à l'endroit approprié.

4. CONCLUSION

Fig. 2 Traitement d'un programme en utilisant les compilateurs.

Pendant toutes les années 50, les compilateurs furent tenus pour des programmes difficiles à

écrire. A titre d’exemple, en 1957, la réalisation du premier compilateur Fortran nécessita 18

hommes travaillant pendant toute une année. On a découvert depuis des techniques systématiques

pour traiter la plupart des tâches importantes qui sont effectuées lors de la compilation.

Contrairement à une idée souvent répandue, la plupart des compilateurs sont écrits dans un

langage de haut niveau, et non pas dans un langage d'assemblage. Les avantages sont multiples :

(i) Facilité de manipulation de concepts avancés,

(ii) Maintenabilité accrue du compilateur, (iii) Et portage plus aisé sur d'autres machines.

A titre d’exemple, le compilateur C++ de Björne Stroustrup est écrit en C.

Programme enlangage évolué(Pascal, C, ...)CompilateurAssembleurChargeur etEditeur de lienProgramme enlangage d'assemblageProgramme encode machineRAM

Structure d’un Compilateur

10

Dans ce cours, nous nous intéressons aux étapes d’analyse lexicale, analyse syntaxique et

analyse sémantique.

* * *