Structure d'un Compilateur

f

&

&

&

&

Table de symboles du compilateur

Les blancs, les autres s parateurs et les commentaires qui figurent dans un programme seront

ignor s au cours de la phase d'analyse lexicale.

Exemple 1 : L'instruction C suivante :

E = m c c

est form e de :

. L'identificateur E

. L'op rateur d'affectation =

. L'identificateur m

Structure dun 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 derreurs lexicales en C: 1x, a&, whle, doo, &

Les outils utilis s par un compilateur pour faire lanalyse lexicale sont les expressions

r guli res et les automates tats finis.

1.2. Analyse Syntaxique

Durant l tape de lanalyse 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 nSuds 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 derreurs syntaxiques en C: x=y++2, z= x , f(a,b, &

Les outils utilis s par le compilateur pour faire lanalyse syntaxique sont les grammaires et les

automates pile.

= E m c c

Structure dun Compilateur

6

1.3. Analyse S mantique

Durant l tape danalyse 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 derreurs 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 lanalyse 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 loptimisation 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 dun 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 doptimiser 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 lextraction 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 dun 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 dun 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 dexemple, 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 dexemple, 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 dun Compilateur

10

Dans ce cours, nous nous int ressons aux tapes danalyse lexicale, analyse syntaxique et

analyse s mantique.