Chapitre 1 : Traducteurs et interpréteurs
1.1 Les traducteurs
La difficulté de programmer directement en langage machine,
c'est-à-dire en introduisant des mots binaires à la main dans la
mémoire de l'ordinateur, a fait naître plusieurs
générations d'outils appelés traducteurs. Ces outils
permettent de programmer en utilisant des structures, souvent
conceptuellement complexes, formulées de façon relativement
lisible.
Un traducteur est un programme qui accepte en entrée une
représentation textuelle d'un algorithme décrit dans un langage source et qui produit en sortie une représentation du
même algorithme dans un autre langage appelé langage cible,
ou langage objet. De nos jours, les traducteurs les plus
modernes produisent souvent du langage cible aussi << bon >> que celui
que produirait un spécialiste humain.
On distingue différents types de traducteurs :
-
Assembleur
- Le langage source des assembleurs utilise une
représentation symbolique des instructions machines. Le langage
cible est alors le langage machine. Un assembleur traduit
généralement une instruction symbolique en une instruction
machine. Les macro-assembleurs utilisent un mécanisme
quelquefois sophistiqué de remplacement de texte pour permettre
à l'utilisateur de créer ses propres instructions symboliques.
- Compilateur
- Le langage source des compilateurs est dit de
haut niveau. Une instruction du langage source est souvent
traduite en un nombre important d'instructions du langage objet de
bas niveau. Lorsque le langage produit n'est pas destiné
à la machine sur laquelle tourne le compilateur, on parle de
cross-compilateur.
- Préprocesseur
- Le langage source et le langage objet des
préprocesseurs sont des langages de haut niveau. Un
préprocesseur fournit à l'utilisateur un sur-ensemble d'un
langage donné en ajoutant certaines possibilités absentes du
langage. Par exemple dans le langage C, il n'y a pas de
déclarations de constantes, c'est le préprocesseur
cpp qui
les prend en charge.
- Décompilateur et désassembleur
- Le langage source des
décompilateurs et des désassembleurs est de plus bas niveau
que le langage objet. En général, ces outils servent à
regénérer un programme source à partir d'un programme objet.
Les désassembleurs produisent une forme lisible d'un code en
langage machine. Les décompilateurs de langages comme Pascal ne
peuvent se concevoir que dans le cadre d'environnements de
compilation appropriés (par exemple Mentor) dans lesquels les
informations habituellement absentes d'un programme objet (par
exemple les symboles utilisés dans le texte source) sont
conservées.
1.2 T-diagramme et bootstrapping
Un traducteur est un programme lui-même écrit dans un langage
informatique. Il est maintenant rare que ce langage soit de bas
niveau, le plus souvent il s'agit aussi d'un langage de haut niveau.
Ce langage est appelé langage hôte du traducteur. Une bonne
notation pour un traducteur est le T-diagramme
(figure 1.1).
+---------------------------------+
| langage traducteur langage |
| source cible |
+----------+ +----------+
| langage |
| hote |
+-----------+
Figure 1.1 : T-diagramme pour un traducteur.
Une traduction est alors notée par un T-diagramme
(figure 1.2).
+---------------------------------+
programme | langage traducteur langage | programme
source | source cible | objet
+----------+ +----------+
| langage |
| hote |
+-----------+
machine
hote
Figure 1.2 : T-diagramme pour une traduction.
Par exemple, la compilation C de myprog.c sur Sun 3 sera notée par
le T-diagramme de la figure 1.3.
+---------------------------------+
myprog.c | C compilateur C code | a.out
| (cc) 68000 |
+----------+ +----------+
| code |
| 68000 |
+-----------+
Sun 3
Figure 1.3 : T-diagramme pour cc myproc.c.
Le bootstrapping est une technique de construction de compilateurs
portables au cours de laquelle on va écrire le compilateur dans son
propre langage source.
Prenons l'exemple du premier compilateur Pascal développé par le
créateur du langage : Nicklaus Wirth. Wirth a commencé par
écrire un compilateur d'un sous-ensemble de Pascal, Pascal-1, en
code CDC (le langage machine des Control Data), produisant du code CDC
(figure 1.4).
+---------------------------------+
| Pascal-1 PAS-1 code |
| CDC |
+----------+ +----------+
| code |
| CDC |
+-----------+
Figure 1.4 : Compilateur PAS-1.
Il écrivit ensuite un programme Pascal qui faisait la même chose
que son premier compilateur. De plus, il inclua dans son programme des
fonctionnalités absentes de Pascal-1. La compilation de ce programme
par son premier compilateur donna un nouveau compilateur plus
performant (figure 1.5).
+---------------------------------+
| Pascal-2 code |
| CDC |
+----------+ +----------+----------------------+
| Pascal-1 | Pascal-1 PAS-1 code |
| | CDC |
+-----------+----------+ +----------+
| code |
| CDC |
+-----------+
Figure 1.5 : Compilation produisant PAS-2.
Cette chaîne peut être notée par l'imbrication des
T-diagrammes comme à la figure 1.6.
+---------------------------------+ +---------------------------------+
| Pascal-2 code | | Pascal-2 PAS-2 code |
| CDC | | CDC |
+----------+ +----------+-----------+----------+ +----------+
| Pascal-1 | Pascal-1 PAS-1 code | code |
| | CDC | CDC |
+-----------+----------+ +----------+-----------+
| code |
| CDC |
+-----------+
Figure 1.6 : Chaîne de compilation produisant PAS-2.
Lorsque Wirth voulut porter son compilateur sur machine ICL, il
réécrivit un compilateur en Pascal générant du code ICL. Ce
travail n'était pas trop difficile, puisque qu'il l'avait déjà
fait pour CDC. En le compilant avec le compilateur Pascal du CDC
(PAS), il fabriqua un cross-compilateur (Cross-PAS,
figure 1.7).
+---------------------------------+ +---------------------------------+
| Pascal code | | Pascal Cross-PAS code |
| ICL | | ICL |
+----------+ +----------+-----------+----------+ +----------+
| Pascal | Pascal PAS code | code |
| | CDC | CDC |
+-----------+----------+ +----------+-----------+
| code |
| CDC |
+-----------+
Figure 1.7 : Production d'un cross-compilateur pour ICL.
Un dernière compilation produisit un compilateur fonctionnant sur
ICL (PAS-ICL, figure 1.8).
+---------------------------------+ +---------------------------------+
| Pascal code | | Pascal PAS-ICL code |
| ICL | | ICL |
+----------+ +----------+-----------+----------+ +----------+
| Pascal | Pascal Cross-PAS code | code |
| | ICL | ICL |
+-----------+----------+ +----------+-----------+
| code |
| CDC |
+-----------+
Figure 1.8 : Production d'un compilateur pour ICL.
1.3 Structure d'un compilateur
Un compilateur est un programme complexe divisé en phases. On
peut imaginer que chaque phase communique avec la précédente et la
suivante grâce à un langage approprié. En réalité les
différentes phases sont le plus souvent entrelacées.
On peut mettre en évidence les phases suivantes :
-
Interface d'entrée
-
Cette phase est responsable de la communication avec l'extérieur, il
s'agit souvent du système d'exploitation, pour lire et écrire dans
les fichiers d'entrée et de sortie. Cette phase est dépendante de
la machine.
- Analyseur lexical
-
Son rôle est de reconnaître dans le flux de caractères fourni
par l'interface d'entrée les mots élémentaires du langage tels
les identificateurs, les mots clés, les opérateurs, etc. Les mots
reconnus sont codés sous forme de tokens qui seront fournis
à la phase suivante.
- Analyseur syntaxique
-
Son rôle est de reconnaître dans le flux de tokens fourni par
l'analyseur lexical des phrases vérifiant la syntaxe du
langage. La syntaxe du langage, précisée par une grammaire
algébrique, permet à l'analyseur syntaxique de construire un arbre de dérivation ou arbre de syntaxe abstraite qui sera
utilisé par les phases suivantes.
- Analyseur sémantique
-
Son rôle est de déterminer si les phrases reconnues par
l'analyseur syntaxiques ont un sens. En pratique son rôle est
essentiellement d'assurer que le texte source vérifie les règles
non syntaxiques qui pourraient être imposées (concordance de type,
visibilité des variables, présence des déclarations
nécessaires...).
- Générateur de code intermédiaire
-
On va souvent, pour des raisons de portabilité, traduire le texte
source dans un langage de plus bas niveau dit intermédiaire car ne
correspondant pas au but final de la traduction, à savoir produire
du code exécutable sur une machine. Ce code intermédiaire a la
propriété d'être général et de ne pas supposer une
architecture de machine précise (nombre de registres, disposition de
la mémoire...). Pour passer d'une machine à une autre, il
suffit en général de réécrire les phases ultérieures à la
génération de code intermédiaire.
- Optimisation du code intermédiaire
-
Cette phase optionnelle réalise une amélioration de la qualité
du code intermédiaire. Son rôle est d'éliminer le code inutile
ou de simplifier ce code.
- Génération de code et optimisation finale
-
Cette phase est bien sûr dépendante de la machine cible. Le code
intermédiaire va être traduit en instructions machines, les
emplacements mémoires vont être choisis, les registres vont être
affectés à des tâches particulières... Cette phase étant
très importante pour la future efficacité du compilateur, une
dernière optimisation peut être entreprise.
De plus, au cours de toutes ces phases, il est nécessaire de
maintenir une table des symboles qui garde trace des symboles
utilisés dans le texte source et les attributs qui leur sont
associés (type, adresse, valeur...).
Une autre tâche que doit réaliser un compilateur est la gestion des erreurs avec des techniques qui le plus souvent
permettent au compilateur de continuer << sainement >> le travail
d'analyse après la détection d'erreurs, et qui quelquefois
permettent la correction d'erreurs simples.
La structure d'un compilateur est schématisée par la
figure 1.9.
+-------------+
| Code source |
+------|------+
V
Interface d'entree <-|
| |
V |
|-> Analyseur lexical <-|
| | |
| V |
|-> Analyseur syntaxique <-|
| | |
| V |
|-> Analyseur semantique <-|
| | |
| V |
Table des symboles |-> Generation de code <-| Gestion des erreurs
| intermediaire |
| | |
| V |
|-> Optimisation de code <-|
intermediaire |
| |
V |
Generation de code <-|
|
V
Optimisation de code
|
+-----V------+
| Code objet |
+------------+
Figure 1.9 : Organisation générale d'un compilateur.
Exemple
Prenons en exemple le texte source suivant :
while (1<P) and (P<3) do
P:=P+Q
L'interface d'entrée va fournir une suite de caractères
significatifs (l'espace blanc est noté par le caractère _) :
w h i l e _ ( 1 < P ) _ a n d _ ( P < 3 ) _ d o _ P : = P + Q _
L'analyseur syntaxique va reconnaître les mots (tokens) suivants :
|
mot clef |
|
|
|
while |
|
|
symbole |
|
|
|
parenthèse ouvrante |
|
|
constante numérique |
|
|
|
1 |
|
|
opérateur relationnel |
|
|
|
< |
|
|
identificateur |
|
|
|
P |
|
|
symbole |
|
|
|
parenthèse fermante |
|
|
mot clef |
|
|
|
and |
|
|
symbole |
|
|
|
parenthèse ouvrante |
|
|
identificateur |
|
|
|
P |
|
|
opérateur relationnel |
|
|
|
< |
|
|
constante numérique |
|
|
|
3 |
|
|
symbole |
|
|
|
parenthèse fermante |
|
|
mot clef |
|
|
|
do |
|
|
identificateur |
|
|
|
P |
|
|
symbole |
|
|
|
affectation |
|
|
identificateur |
|
|
|
P |
|
|
opérateur |
|
|
|
+ |
|
|
identificateur |
|
|
|
Q |
|
L'analyseur syntaxique va construire un arbre tel celui de la
figure 1.10.
while_inst
v-----------|----------------v
cond_compose inst_simple
v---------|--------v |
cond and cond affectation
v-----|------v v-----|-----v v---|---v
num op_inf id id op_inf num id exp
v---|------v
id op_add id
Figure 1.10 : Exemple d'arbre de dérivation.
Le code intermédiaire généré sera de la forme :
|
L0 |
|
|
|
if 1<P goto L1 |
|
|
|
|
|
|
goto L3 |
|
|
L1 |
|
|
|
if P<3 goto L2 |
|
|
|
|
|
|
goto L3 |
|
|
L2 |
|
|
|
P:=P+Q |
|
|
|
|
|
|
goto L0 |
|
|
L3 |
|
|
|
... |
|
Il pourra être optimisé en :
|
L0 |
|
|
|
if 1<P goto L1 |
|
|
|
|
|
|
goto L3 |
|
|
|
|
|
|
if P>=3 goto L1 |
|
|
|
|
|
|
P:=P+Q |
|
|
|
|
|
|
goto L0 |
|
|
L1 |
|
|
|
... |
|
1.4 Interpréteur
Certains compilateurs ne possèdent pas de phase de génération de
code en langage machine. Ils s'arrêtent à la production de code
intermédiaire. L'exécution du programme source consiste alors en
une interprétation du code intermédiaire par un programme
appelé interprète ou interpréteur. Quelquefois,
l'interprète exécute directement le langage source, comme en Basic
ou en APL. Le plus souvent, il exécute un code intermédiaire
fabriqué par un compilateur, par exemple le P-Code fabriqué par le
compilateur Pascal UCSD, ou le A-Code du compilateur ADA-Artek.
L'intérêt d'une interprétation du langage intermédiaire est la
portabilité du compilateur ainsi créé : le groupe de Wirth à
Zurich diffusait le langage Pascal en fournissant le source d'un
compilateur Pascal en P-Code et le source Pascal d'un interprète
P-Code. Pour porter Pascal sur sa machine, il suffisait de
réécrire un programme équivalent à l'interprète fourni.
Le désavantage d'une interprétation est une baisse de performance
des programmes ; l'interprétation étant souvent plus lente que ne
le serait l'exécution de code machine optimisé d'un compilateur
complet.
1.5 Exemple de code intermédiaire pour une machine à pile
Nous présentons ici un langage intermédiaire qui est une forme
simplifiée du P-Code, et étudions la réalisation d'un
interprète pour ce langage à la
section 1.6.
Le P-Code est le langage intermédiaire utilisé pour le Pascal
UCSD. Il est associé à la machine abstraite P-Machine. Cette
machine n'a qu'une zone mémoire gérée en pile (en particulier,
elle n'a donc pas de registres, mis à part le pointeur de sommet de
pile (SP) et le compteur d'instructions (PC)). La plupart des
instructions du P-Code prennent donc leurs opérandes sur la pile et
laissent leur résultat sur cette pile.
La structuration de la mémoire en pile facilite la compilation de
langages de haut niveau autorisant la récursion et la compilation
d'expressions arithmétiques complexes. Cette structuration n'a pas que
des avantages, en particulier pour l'utilisation optimale de
registres de la machine physique.
Le bas de la pile est réservé pour l'allocation des variables
globales, c'est-à-dire que la première instruction d'un programme
P-Code réserve une partie de la pile correspondant à la zone
d'allocation des variables utilisées dans le programme ; cette
réservation est faite par incrémentation du pointeur de pile de la
taille mémoire nécessaire.
Les éléments de la pile sont de simples entiers ; les adresses
sont des adresses absolues dans la pile.
Le jeu d'instruction du P-Code simplifié que nous considérerons
est donné à la figure 1.11.
ADD |
additionne le sous-sommet de pile et le sommet,
laisse le résultat au sommet (idem pour SUB,
MUL, DIV) |
EQL |
laisse 1 au sommet de pile si sous-sommet = sommet,
0 sinon (idem pour NEQ, GTR, LSS, GEQ, LEQ) |
PRN |
imprime le sommet, dépile |
INN |
lit un entier, le stocke à l'adresse trouvée au
sommet de pile, dépile |
INT c |
incrémente de la constante c le pointeur de
pile (la constante c peut être négative) |
LDI v |
empile la valeur v |
LDA a |
empile l'adresse a |
LDV |
remplace le sommet par la valeur trouvée à l'adresse
indiquée par le sommet (déréférence) |
STO |
stocke la valeur au sommet à l'adresse indiquée par
le sous-sommet, dépile 2 fois |
BRN i |
branchement inconditionnel à l'instruction i |
BZE i |
branchement à l'instruction i si le sommet = 0,
dépile |
HLT |
halte |
Figure 1.11 : Jeu d'instructions du P-Code.
L'exemple suivant :
begin
repeat
read (A) ;
B := A + B ;
until A = 0 ;
write (B) ;
end
produira le P-code de la figure 1.12.
|
0 |
|
|
|
INT 2 |
|
|
|
réserve 2 emplacements pour A (0) et B (1) |
|
|
1 |
|
|
|
LDA 0 |
|
|
|
empile l'adresse de A |
|
|
2 |
|
|
|
INN |
|
|
|
lit une valeur la range dans A |
|
|
3 |
|
|
|
LDA 1 |
|
|
|
empile l'adresse de B |
|
|
4 |
|
|
|
LDA 0 |
|
|
|
empile l'adresse de A |
|
|
5 |
|
|
|
LDV |
|
|
|
déréférence. Valeur de A au sommet |
|
|
6 |
|
|
|
LDA 1 |
|
|
|
empile l'adresse de B |
|
|
7 |
|
|
|
LDV |
|
|
|
déréférence. Valeur de B au sommet |
|
|
8 |
|
|
|
ADD |
|
|
|
addition de A et B |
|
|
9 |
|
|
|
STO |
|
|
|
stocke le résultat dans B |
|
|
10 |
|
|
|
LDA 0 |
|
|
|
empile l'adresse de A |
|
|
11 |
|
|
|
LDV |
|
|
|
déréférence. Valeur de A au sommet |
|
|
12 |
|
|
|
LDI 0 |
|
|
|
empile la valeur 0 |
|
|
13 |
|
|
|
EQL |
|
|
|
test d'égalité |
|
|
14 |
|
|
|
BZE 1 |
|
|
|
branchement en 1 si A <> 0 |
|
|
15 |
|
|
|
LDA 1 |
|
|
|
empile l'adresse de B |
|
|
16 |
|
|
|
LDV |
|
|
|
déréférence. Valeur de B au sommet |
|
|
17 |
|
|
|
PRN |
|
|
|
écrit le résultat |
|
|
18 |
|
|
|
HLT |
|
|
|
fin |
|
Figure 1.12 : Exemple de programme P-Code.
1.6 Écriture d'un interprète de P-Code
Les structures de données nécessaires lors de l'écriture d'un
interprète simplifié pour le P-Code sont 1--un tableau
MEM représentant la pile
de la machine et un pointeur de pile associé
(SP, stack pointer) :
|
var |
|
MEM : array [0 .. TAILLEMEM] of integer ; |
|
|
|
|
SP : integer ; |
|
2--un tableau PCODE
stockant les pseudo-instructions, auquel sont associés l'instruction
courante INST et un
pointeur d'instruction PC ;
une instruction est un couple (mnémonique, opérande
éventuelle) :
|
type |
|
MNEMONIQUES = (ADD,SUB,MUL,DIV,EQL,NEQ,GTR,LSS,GEQ,LEQ, |
|
|
|
|
PRN,INN,INT,LDI,LDA,LDV,STO,BRN,BZE,HLT) ; |
|
|
|
|
INSTRUCTION = record |
|
|
|
|
MNE : MNEMONIQUES ; |
|
|
|
|
SUITE : integer |
|
|
|
|
end |
|
|
var |
|
PCODE : array [0 .. TAILLECODE] of INSTRUCTION ; |
|
|
|
|
PC : integer ; |
|
|
|
|
INST : INSTRUCTION ; |
|
L'algorithme se divise en deux parties ; le << chargeur >> et
l'interpréteur proprement-dit.
Le chargeur remplit la table PCODE à partir d'un fichier de code
P-Code. L'interprète est basé sur le modèle de la
figure 1.13
begin
(* initialise pointeur d'instruction PC et pointeur de pile SP *)
(* initialise program status PS a EXECUTION *)
repeat
(* chargement *)
INST = PCODE [PC]
incremente PC
(* execution *)
with INST do
case MNE of
ADD : begin SP:=SP-1; MEM[SP]:=MEM[SP]+MEM[SP+1] end ;
...
HLT : PS:=FINI ;
end
until PS <> EXECUTION
end.
Figure 1.13 : Modèle d'un interprète P-Code.
1.7 Travaux dirigés et travaux pratiques
-
Écrire un programme P-Code dont l'algorithme est défini par
begin
read (A) ; SMALLEST:=A ; LARGEST:=A ;
while A <> 0 do begin
if A > LARGEST then LARGEST:=A ;
if A < SMALLEST then SMALLEST:=A ;
read (A)
end
write (SMALLEST,LARGEST)
end.
- Le jeu d'instructions du P-Code vous semble-t-il suffisant pour
définir une << machine à entiers >> ?
- Écrire le << chargeur >> de P-Code ; il est préalablement
nécessaire de définir la syntaxe du source P-Code (label
d'instruction, commentaires...).
- Compléter le programme de la
figure 1.13 pour définir un
interprète P-Code.
- Réaliser une série de tests de l'interpréteur ainsi défini.
- Un programme P-Code peut-il être incorrect ? Deux types
d'incorrections sont distinguées : celles qui peuvent être
détectées statiquement, et celles qui ne peuvent être
détectées qu'à l'exécution. Proposer un outil d'analyse
statique d'un programme P-Code qui en vérifie la correction. Ajouter
dans l'interpréteur la détection des erreurs survenant lors de
l'exécution.
- Quels outils peuvent être utiles pour la mise au point de programmes
P-Code ? En expliquer la mise en place.
- Développer une variante du P-code avec des instructions de branchements relatifs plutôt qu'absolus. Quels sont les avantages
de cette approche ?
- Quelles optimisations peuvent être mises en place au niveau du
P-Code. Expliciter la structure d'un optimiseur. Comment l'intégrer
dans l'interpréteur ?