4ème Année G.
Info
Année 2013-2014
Support de cours
Théorie des Langages
&
Techniques de Compilation
Prof. Redouane EZZAHIR
Sommaire
Introduction ................................................................................................................................. 3
Compilateurs vs Interpréteurs ............................................................................................................ 3
Pourquoi apprendre à construire des compilateurs? ......................................................................... 4
Un bref historique ............................................................................................................................... 5
La Préhistoire ................................................................................................................................... 5
Naissance des compilateurs ............................................................................................................ 6
L’impact du FORTRAN I.................................................................................................................... 7
Structures d'un compilateur................................................................................................................ 7
Partie frontale ................................................................................................................................. 8
Analyse Lexicale........................................................................................................................... 8
Analyse syntaxique ...................................................................................................................... 8
Analyse sémantique .................................................................................................................... 9
Génération du code Intermédiaire.............................................................................................. 9
Optimisation du code intermédiaire ......................................................................................... 10
Partie finale ................................................................................................................................... 11
Génération du code machine. ................................................................................................... 11
Phases parallèles ........................................................................................................................... 12
Gestion de la table des symboles .............................................................................................. 12
Gestion des erreurs ................................................................................................................... 12
Générateurs de compilateurs............................................................................................................ 12
Organisation de cours ....................................................................................................................... 13
Références ......................................................................................................................................... 13
Introduction
En tant qu’informaticien vous avez sûrement écrit un programme en langage de haut niveau
(Java, C, C++, …). Puis vous avez compilé votre code source en utilisant des commandes (gcc, javac, ..)
ou des IDE (Environnement de développement intégré) pour générer un code directement
exécutables sur la Machine (cette machine peut être virtuelle comme le JVM pour java). Parmi les
outils misent en jeu figure un ou plusieurs compilateurs. C’est la raison pour laquelle le processus en
entier est appelé compilation.
Compilateurs vs Interpréteurs
Tous simplement, le compilateur traduit un programme écrit dans un langage L1 appelé langage
source (souvent un langage de haut niveau) en un programme équivalent écrit en un langage L2
appelé langage cible (voir Figure 1). Un rôle important du compilateur est de signaler les erreurs dans
le programme source qui sont détectées pendant le processus de traduction.
Programme Compilateur Programme
source cible
Message
d’erreur
Figure 1 : Schéma d’un Compilateur
Dans le cas où le programme cible est un programme exécutable écrit en langage machine, il peut
ensuite être appelée par l'utilisateur pour traiter les entrées et produire des résultats en sorties (voir
Figure 2).
Programme Sortie
Données
cible
Figure 2 : Schéma d’exécution d’un programme cible
Un interprète est un autre type commun de traitement de langage. Au lieu de produire un
programme cible comme une compilation, un interprète semble exécuter directement les opérations
spécifiées dans le programme source sur les entrées fournies par l'utilisateur (voir Figure 3).
Programme
source Interpréteur Sortie
Données
Message
d’erreur
Figure 3 : Schéma d’un Interprète
Dans certain cas le programme source est le résultat d’une compilation effectuée au préalable
(Exemple du Bytecode du langage java). Chaque instruction du programme source est convertie en
une ou plusieurs instructions en langage machine. L’exécution commence tout de suite,
contrairement au cas de la compilation, mais il est plus lent. L’interprète peut être qualifié par
« Moteur d'exécution » où l’exécution est entrelacée avec l'analyse du programme source. Le bloque
d’exécution de l’interprète peut être représenté par le code ci-dessous qui peut comprendre des
analyses répétées (ligne 3.) de certains états comme les boucles, les fonctions, etc.
running = true;
while (running) {
read and analyze next statement;
execute that statement;
}
En général, l’environnement intégré de développement de logiciel comprend de nombreux types de
processeurs de langage tels que des compilateurs, interprètes, préprocesseurs, lieurs (linkers),
chargeuses, débogueurs, et profileurs. Dans ce cours nous allons aborder en détaille seulement les
compilateurs. Malgré tout, le rôle des autres processeurs sont décrits en annexe. I. Cependant, vous
pouvez remarquer qu’il y a peu de gens qui écrivent des compilateurs comme profession. Par
conséquence une question à poser: pourquoi apprendre à construire des compilateurs?
Pourquoi apprendre à construire des compilateurs?
Il est important de savoir que pour toute formation académique et/ou dans le cas d'une formation
d’ingénieur, non seulement la connaissance et le savoir-faire doivent être transmis, mais aussi la
compréhension et la perspicacité. En particulier, la connaissance surfacique du système est
insuffisante en informatique. ce qui est nécessaire est la compréhension en détaille des contenus.
Chaque informaticien académique instruite doit connaître le fonctionnement d'un ordinateur, et doit
comprendre les moyens et les méthodes dont les programmes sont représentés et interprétés. Les
compilateurs convertissent les programmes source en code interne. Cela dit qu’une véritable
compréhension d'un sujet s'acquiert mieux d'une implication en profondeur avec les concepts et les
détails. Dans ce cas, cette participation est rien de moins que la construction d'un compilateur réelle.
En effet, les idées et techniques développées dans ce domaine sont si générales et fondamentales
qu’un informaticien (et même un scientifique non informaticien) les utilisera très souvent au cours
de sa carrière: traitement de données, moteurs de recherche, outils awk, etc.
En outre, vous allez acquis comment les des langages de programmation sont construits, comment ils
fonctionnent, et le compromis dans la conception d’un langage de programmation. En d’autre terme
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, et réalisés seulement en combinant directement théorie et pratique. En
effet, la construction de compilateur fait appelle à différents idées parvenant de nombreuses
disciplines d'informatique :
Intelligence artificielle: algorithmes gloutons, recherche heuristique
Théorie de graphes: algorithmes de construction et parcours de graphes
Algorithmiques : programmation dynamique, les algorithmes d'approximation
Théorie de langages: Grammaires, automates AFD, AFNA, et Expressions réguliers.
Systèmes: allocation et nomination, la synchronisation, et notion de localité.
Architecture des ordinateurs: utilisation jeu d'instructions, registres, et pipelines.
Etc.
Maintenant que vous être convaincu, nous allons commencer notre étude de compilateur par un
bref historique.
Un bref historique
La Préhistoire
Les machines à calculer sont utilisées depuis des milliers d'années : on trouvait probablement des
abaques à Babylone en 3000 avant notre ère. Les Grecs ont fabriqué des calculateurs analogiques
très perfectionnés. Le monde arabo-musulman à son apogée intellectuelle du viiie au xive siècle
permet le développement d'une culture scientifique spécifique. En 820, le mathématicien musulman
Al Khawarizmi publie à Bagdad un traité intitulé “Abrégé du calcul par la restauration et la
comparaison” qui, importé en Europe Occidentale lors des conquêtes islamiques aura une grande
influence sur le développement des mathématiques.
En 1840, La grande collaboratrice du mathématicien Charles Babbage (1791 -1871), Ada Lovelace,
mathématicienne, définit le principe des itérations successives dans l’exécution d’une opération. En
l’honneur Al Khawarizmi, elle nomme le processus logique d’exécution d’un programme : algorithme
(déformation d’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. Le langage
ADA créé en 1979 a été nommé en son honneur.
En 1854, Boole publie un ouvrage dans lequel il démontre 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).
Plankalkül est un langage de programmation, conçu de 1942 à 1946 par l'allemand Konrad Zuse. À
l'époque, Zuse ne fit aucune communication scientifique à ce sujet, pour diverses raisons : la Seconde
Guerre mondiale faisait rage, et il consacrait tous ses efforts à la conception et à la commercialisation
de son ordinateur, le Zuse 3. La première publication mentionnant Plankalkül date de 1948. En 1975,
il fut décrit et implémenté à l'occasion de la thèse de J. Hohmann. Le premier compilateur, proposé
par l'université libre de Berlin, a été achevé en 2000, soit cinq ans après la mort de Zuse.
En 1945, six femmes furent sélectionnées pour la programmation de l’Electronic Numerical
Integrator And Computer (ENIAC) : Marlyn Meltzer, Ruth Teitelbaum, Frances Spence, Kathleen
Antonelli, Jean Jennings Bartik en Betty Holberton.
Après la période ENIAC, Jean Bartik conçut 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. Alors que Betty Holberton fut employée dans la société Eckert & Mauchly, qui conçut les
premiers ordinateurs commerciaux. C’est elle qui programma le code d’instruction C-10 pour UNIVAC
I, qui permit aux programmeurs de programmer toujours plus vite et facilement. Pour UNIVAC I,
Holberton conçut également un panneau de contrôle, et un clavier numérique. Dans les années
cinquante, elle participa au Comité COBOL, qui conçut le premier langage de programmation
professionnel. Durant des dizaines d’années, elle participa à des comités actifs dans la normalisation
informatique nationale et internationale.
En 1945, un insecte coincé dans les circuits bloque le fonctionnement du calculateur Mark I. La
mathématicienne Grace Murray Hopper décide 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.
Naissance des compilateurs
La vraie histoire des compilateurs a commencée en 1950, et en particulier avec une machine appelée
la 704 construite par IBM. Il était leur première machine qui a connu un succès commercial, bien qu'il
y ait eu une certaine premières machines qu'ils avaient expérimentée. Mais, de toute façon la chose
intéressante à propos de la 704, et une fois les clients ont commencé à l’acheter et l’utilisée, est
qu'ils ont constaté que les coûts liés aux logiciels ont trop dépassé le coût du matériel.
Ceci est important car le matériel de ces jours était extrêmement cher. La charge du logiciel pour
faire bon usage des ordinateurs devenait dominante, que le matériel n’avait jamais coûté encore.
Ce qui a conduit un certain nombre de gens à réfléchir sur la façon dont ils pourraient faire un
meilleur travail de l'écriture de logiciels. Comment pourraient-ils faire une programmation plus
productive.
Les premiers efforts pour améliorer la productivité de la programmation ont été appelé
« speedcoding », développé en 1953 par John Backus. Speedcoding permet l’amélioration de la
vitesse du codage. C’est ce que nous appelons aujourd’hui, un exemple précoce d'une interprète. Et
comme tous les interprètes, il y avait des avantages et des inconvénients. Le principal avantage est
qu'il est beaucoup plus rapide, pour développer les programmes. Donc en ce sens, le programmeur
était beaucoup plus productif, mais parmi ses inconvénients, les programmes en speedcoding étaient
dix à vingt fois plus lents. En plus, l’interprète speedcoding avais besoins de 300 octets de mémoire.
Cela ne semble pas beaucoup, en fait, 300 octets, aujourd’hui, semblent comme un très petit
programme. Mais dans cette époque, vous devez garder à l’esprit, que c'était 30% de la mémoire sur
le Machine. Donc, ce fut 30% de la totalité de la mémoire de la 704. Par conséquent speedcoding ne
peut devenir populaire. Malgré tout, John Backus pensé qu'il était prometteur et il lui a donné l'idée
pour un autre projet.
Les applications les plus importantes de ces jours étaient les calculs scientifiques, et les
programmeurs ont pensé d’écrire des formules sous une forme que la machine pourrait l’exécuter.
John Backus jugeait que le problème avec le speedcoding est que les formules étaient en fait
interprétées. Alors, il pensait, s’il peut d'abord les traduire dans une forme que la machine pourrait
les exécuter directement pour que le code soit plus rapide, tout en permettant aux programmeurs
d'écrire des programmes à un niveau élevé. C’est à ce moment que le projet FORTRAN était né.
Le projet FORTRAN a duré de 1954 à 1957. Ils ont pensé qu'il ne ferait que prendre une année à
construire le compilateur mais il finirait par prendre trois ans. Ainsi, tout comme aujourd'hui, ils
n'étaient pas très bons pour prédire les projets de logiciels combien de temps prendrait. Mais c'était
un projet très réussi.
En 1958, plus de 50% de programmes étaient en FORTRAN. C'est une adoption très rapide d'une
nouvelle technologie. Nous serions heureux avec ce genre du succès aujourd'hui, et bien sûr, à ce
moment ils étaient ravis, et tout le monde pensait que FORTRAN a relevé le niveau d'abstraction,
l'amélioration de la productivité des programmeurs, et a permis à chacun une meilleure utilisation de
ces machines.
À peu près au même moment, Noam Chomsky a commencé son étude de la structure du langage
naturel. Sa conclusion a finalement fait la construction de compilateurs beaucoup plus facile. L'étude
de Chomsky a conduit à la classification des langues en fonction de leur complexité des règles
précisant leur structure et des algorithmes nécessaires pour les reconnaître. Un des niveaux de
Chomsky, la grammaire hors-contexte, s'est avéré le plus utile pour les langages de programmation.
L'étude de l'analyse, la détermination d'algorithmes efficaces pour la reconnaissance des langages
hors-contexte, a été poursuivie dans les années 1960 et 1970 et a conduit à une solution assez
complète de ce problème, qui est la théorie sous-jacente de la plupart des cours de compilation.
L’impact du FORTRAN I
FORTRAN I était le premier langage de haut niveau réussi. Ill a eu un impact énorme sur informatique.
En particulier, elle a conduit à un énorme corps de travail théorique. L'une
'une des cchoses intéressantes
sur les langages de programmation est la combinaison de la théorie ett la pratique
pratique. Car il n'est pas
vraiment possible dans les langages de programmation de faire un bon travail ail sans avoir à la fois
fois, une
très bonne connaissance assez profond
pro de la théorie et aussi de bonnes compétences techniques.
Donc, il y a de très bonne ne matière de construction des systèmes dans les langages de
programmation, et généralement ils il impliquent une interaction très subtile et fructueuse avec la
théorie. Je pense que c’est l'une des choses les plus attrayants en informatique. Et l'impact de
FORTRAN n'était pas seulement sur l'ordinateur, et bien sûr, la recherche scientifique, mais aussi sur
le développement de compilateurs pratiques. Son influence était si profonde qu’aujourd’hui les
compilateurs modernes préserver encore les le contours du FORTRAN. Alors quelle est la structure d d’un
compilateur moderne ?
Structures d'un compilateur
Figure 4 : Différentes phase de compilation
Le processus de compilation est complexe. Il est pratiquement impossible de le considérer comme
constituant un seul objet indissociable. Les compilateurs modernesodernes contiennent deux (grandes
(grandes)
parties, dont chacune est souvent subdivisée en plusieurs sous-parties.. Ces deux parties sont
appelées partie frontale (front-end)
end) et partie
part finale (back-end).). Si nous examinons le processus de
compilation plus en détail, on voit qu'il fonctionne comme une séquence de phases, dont chacune
transforme une représentation du programme source à une autre. Une décomposition typique d'un
compilateurr en phases est représentée sur la Figure 4. Dans la pratique, plusieurs phases peuvent
être regroupés, et les représentations intermédiaires entre les phases groupées ne doit pas être
construit de manière explicite. La table de symboles,
s qui stocke des informations sur le programme
source entier, est utilisée par toutes les phases de la compilation.
Partie frontale
La partie frontale fait les analyses du programme source, détermine ses parties constituantes, et
construit une représentation intermédiaire du programme. Typiquement la partie frontale est
indépendante du langage cible. Conceptuellement, il y a trois phases d'analyse successives dont la
sortie d'une phase est l'entrée de la suivante. Ces phases sont l'analyse lexicale, l'analyse syntaxique,
et l'analyse sémantique.
Analyse Lexicale
Elle consiste à lire la séquence de caractères constituant le programme source et à produire une
séquence d’éléments syntaxiques appelés unités lexicales du langage (symboles ou jetons (tokens))
qui seront traité ensuite par l’analyseur syntaxique : nombres, identificateurs, opérateurs, mots
réservés, séparateurs, etc. A titre d'exemple, l'analyse lexicale de l’énoncé position = initiale +
vitesse * 60 devrait donner la suite de jetons suivante:
• <position, identificateur>
• <=, symb-affectation>
• <initiale, identificateur>
• <+, symb-plus>
• <vitesse, identificateur>
• <*, symb-mult>
• <60, constante-entière>
Les identificateurs, tels que les noms des variables et des procédures, ainsi que leurs attributs, sont
stockés dans une table appelée table des symboles voir Figure 5.
Indice symbole Type
1 position float
2 initial float
3 rate float
4 … ..
Figure 5 Table de symboles
La sortie de l’analyse lexicale pour l’instruction position = initiale + vitesse * 60 est la suite de jetons
suivante: id(1) aff id(2) add id(3) mul nbr(60)
Quand l’analyse lexicale détecte une entité lexicale invalide, il rapporte une erreur. Les erreurs sont
telles que : identificateurs trop longs ou illégaux, caractères ou nombres illégaux, etc.
Analyse syntaxique
L'analyse syntaxique (appelée aussi analyse hiérarchique ou analyse grammaticale) tente de
reconnaître dans le flot des jetons la structure d'un texte correct. Il s'agit de vérifier que les unités
lexicales sont dans le bon ordre défini par le langage. Dans le cas contraire, une erreur sera signalée.
Cette analyse produit, implicitement ou explicitement selon les vœux du concepteur, un arbre
syntaxique
que qui sera utilisé par la prochaine phase. Chaque nœud de l'arbre à l'exception des feuilles
représentant les entités lexicales dénote une entité syntaxique. Aussi lors de cette phase, des
informations concernant les identificateurs comme par exemple leur
leur type, seront enregistrées dans
la table de symboles pour servir à l'accomplissement des phases ultérieures. Par exemple la forme
d’un arbre syntaxique concrète pour notre énoncé position = initiale + vitesse * 60 est présenté dans
la Figure 6.
Figure 6 : Arbre syntaxique de l’instruction position = initiale + vitesse * 60
Analyse sémantique
Dans cette phase (appelée aussi analyse contextuelle), on opère certains contrôles (contrôles de
type, par exemple)
ple) afin de vérifier que l'assemblage des constituants du programme a un sens. Le
compilateur a besoin d'informations sémantiques, par exemple, les types (entier, réel, popointeur sur
un tableau d'entiers)) des objets impliqués. Cela permet la vérification des
des erreurs sémantiques et
l'insertion d'une conversion de type si nécessaire. Par exemple, on ne peut pas additionner un réel
avec une chaîne de caractères, ou affecter une variable à un nombre. Par exemple, si la vitesse est un
nombre réel, nous avons besoinoin d'insérer des opérateurs de conversion "inttoreal" comme indiqué
dans la Figure 7 .
Figure 7 L’arbre syntaxique décoré
Génération du code
ode Intermédiaire
Lorsque on écrit un compilateur pour un processeur
processeur donné, il n'est alors pas évident de porter ce
compilateur (ce programme) sur une autre machine cible. C'est pourquoi on introduit des machines
dites abstraites qui font abstraction des architectures réelles existantes. Ainsi, on s'attache plus aux
principes de traduction, aux concepts des langages, qu'à l'architecture des machines.
En général, on produira dans un premier temps des instructions pour une machine abstraite. Puis
ensuite on fera la traduction de ces instructions en des instructions directement exécutables par la
machine réelle sur laquelle on veut que le compilateur s'exécute. Ainsi, le portage du compilateur
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 va rester ensuite qu'à étudier les problèmes spécifiques à la machine
cible, et non plus les problèmes de reconnaissance du programme. Donc, à partir de l'arbre
syntaxique et plus précisément, d'une entité syntaxique, un code intermédiaire simple sera produit.
Plusieurs formes pour le code intermédiaire peuvent être conçues. Les plus utilisés sont:
‒ Le code post-fixe: C'est un code dans lequel, tout opérateur apparait après ses opérandes.
C'est un code préconisé car les opérateurs et les opérandes dans ce code apparaissent dans
le même ordre qu'à l’exécution.
‒ le code 3 trois adresses: Il est caractérisé par le fait qu'une instruction du code contient un
seul opérateur. Et de cette manière, il se rapproche de l'assembleur. La différence majeure
existant entre ce code et le code assembleur est que contrairement au code intermédiaire,
l'assembleur spécifie des registres dans ses instructions.
t1 = inttofloat(60)
Le code de la représentation Intermédiaire de notre instruction t2 = id3 * t1
position = initiale + vitesse * 60 aura par exemple la forme le suivante : t3 = id2 + t2
id1 = t3
Optimisation du code intermédiaire
D'abord, il faut signaler que cette phase est optionnelle. Il existe un bon nombre de compilateurs qui
font abstraction totale de cette phase. C’est une phase d’analyses plus ou moins poussées pour
signaler :
‒ les risques d’erreur à l'exécution ;
‒ les opportunités d’optimisation.
Il réalise aussi l’analyse de flot de données :
‒ propagation de constantes ;
‒ indication des variables non initialisées/non utilisées ;
‒ élimination du code mort ;
‒ factorisation d’invariants de boucle ;
‒ limitation de calculs redondants.
C'est une étape à considérer lorsque le temps machine ou la place mémoire sont critiques. Et c'est
dans ce sens là que l'optimisation est appelée à jouer son rôle. A vrai dire il ne s'agit pas d'une
optimisation effective du code car jusqu'a l'heure actuelle, il n'existe pas encore d'optimiseurs au
sens propre du mot, mais plutôt d'une amélioration considérable du point de vue gain de place et
rapidité d'exécution. Plusieurs techniques d'optimisation sont mises au point actuellement parmi
lesquelles nous citons:
‒ Optimisation locale: Exemple
Soit le code Le code peut être réduit au code
if ( A < B ) goto L1
goto L2 if ( A >- B) goto L2
L1: L1:
Cette substitution a pour effet un gain de place (élimination d'une instruction) et aussi la
rapidité d'exécution (une instruction de moins à exécuter).
‒ Optimisation des boucles: On s'intéresse à l'optimisation des boucles car il a été prouvé
empiriquement que la majorité du temps d'exécution d'un programme se déroule dans des
boucles. L'objectif de cette optimisation est la réduction du temps d'exécution des boucles.
En effet si l'on remarque dans une boucle qu'un calcul est invariant pour toutes les itérations
de la boucle, il est bel et bien intéressant de faire déplacer ce calcul à l'extérieur de la boucle
pour éviter son exécution le nombre d'itérations de cette boucle.
Exemple:
Soit la boucle suivante:
while (i <= 10) {
x = 5;
read(ch);
write(ch);
i = i + x ;
}
On remarque que l'emplacement de l'instruction x = 5 est à l’intérieur de la boucle. Le
résultat de l'optimisation nous donne:
x = 5;
while (i <= 10){
read(ch);
write(ch);
i = i + x;
}
‒ Elimination des sous-expressions communes : c’est le troisième type d'optimisation, auquel
nous nous intéressons particulièrement. Lors de la génération du code intermédiaire, le
compilateur génère le plus souvent les mêmes instructions le long du code. Il est convient
d'abolir toutes les instructions répétitives et d'en garder qu’une seule. La détection de ces
sous-expressions communes se fait à l'aide d'une technique très efficace qui est l'analyse
data flow (data flow analysis).
Le code de la représentation intermédiaire (R.I) de notre instruction position = initiale + vitesse * 60
va être optimisé comme suit :
Code R.I -------> Code R.I optimisé
1 = inttofloat(60) t1 = id3 * 60.0
t2 = id3 * t1 id1 = id2 + t1
t3 = id2 + t2
id1 = t3
Partie finale
La partie finale synthétise le programme cible de la représentation intermédiaire produite par la
partie frontale. Cette partie est généralement indépendante du langage source.
Génération du code machine.
La génération de code objet est la phase finale de la compilation. Elle nécessite la connaissance de la
machine cible (réelle, virtuelle ou abstraite). Il faut connaître le jeu d'instruction de la machine, les
différents modes d’adressage et notamment de ses possibilités en matière de registres, piles, etc.
Cette phase génère du code objet relogeable, i.e. relatif à l’origine 0. Elle traduit chaque instruction
du code intermédiaire en langage machine cible. Par exemple la R.I de notre instruction de calcule de
position sera transformé en code machine suivant :
Code R.I optimisé -------> Code objet
t1 = id3 * 60.0 MOVF id3, r2
td1 = id2 + t1 MULF *60.0, r2
MOVF id2, r2
ADDF r2, r1
MOVF r1, id1
Un problème qui se pose lors de la génération du code objet est la gestion efficace de l'attribution
des registres aux variables des instructions. A tout moment, il faut mémoriser les registres affectés à
des variables et ceux qui ne le sont pas.
Un autre problème que l'on rencontre lors de cette phase est la redondance des instructions
générées.
Phases parallèles
Gestion de la table des symboles
La table des symboles est la structure de données utilisée servant pour stocker les informations qui
concernent les identificateurs du programme source (par exemple leur type, leur emplacement
mémoire, leur portée, visibilité, nombre et type et mode de passage des paramètres d'une
fonction,...). Le remplissage de cette table a lieu lors des phases d'analyse. Les informations
contenues dans la table sont nécessaires lors des analyses syntaxique et sémantique, ainsi que lors
de la génération de code.
1- L'analyse lexicale insère les identificateurs, les constantes ainsi que les labels dans cette
table.
2- L'analyse syntaxique, elle, associe à chaque identificateur son type, à chaque fonction, son
nombre d'arguments ainsi que ses paramètres formels etc.
3- Le générateur du code intermédiaire lui, avant de générer une instruction telle que x=y*z
par exemple, doit accéder à la table pour repérer les types des opérandes afin de vérifier la
compatibilité des types. Si le langage permet le mixage des types, une instruction spécifiant
une conversion de type sera générée et le générateur doit mémoriser le nouveau type dans
la table.
4- Lors de l'optimisation des sous-expressions communes, à tout identificateur résultant d'une
expression à éliminer doit être substitué à l'identificateur résultant de l'expression à garder.
Le résultat de cette modification doit figurer dans la table afin de poursuivre le processus.
Gestion des erreurs
Chaque phase peut rencontrer des erreurs. Cependant, après avoir détecté une erreur, une phase
doit la traiter de telle façon que la compilation puisse continuer et que d'autres erreurs dans le
programme source puissent être détectées. Un compilateur qui s'arrête à la première erreur n'est
pas non plus très performant. Bien sûr, il y a des limites à ne pas dépasser et certaines erreurs (ou un
trop grand nombre d'erreurs) peuvent entraîner l'arrêt de l'exécution du compilateur.
Générateurs de compilateurs
De nos jours, il existe des logiciels qui peuvent contribuer énormément à la construction des
compilateurs. Certains d'entre eux, génèrent automatiquement des analyseurs lexicaux (JFlex, Flex)
et des analyseurs syntaxiques (Cup, YCC). D'autres plus complexes génèrent des compilateurs
complets (compiler generators, compiler-compilers).
Le long de ce cours nous allons utiliser JFlex et Cup qui sont écrites en le langage java. Au lieu d'écrire
un programme pour les analyses lexicale et syntaxique, l'utilisateur doit simplement fournir la
grammaire du langage écrite selon la forme de Backus Naur (BNF) aux JFlex et Cup pour obtenir en
sortie un programme qui fait l'analyse lexicale et syntaxique.
Organisation de cours
Le but de ce cours est de présenter les principes de base inhérents à la réalisation de compilateurs.
Les outils fondamentaux utilisés pour effectuer les phases de l'analyse sont obtenus à partir des
fondements de la théorie des langages (grammaires, expressions réguliers, automates, méthodes
algorithmiques d‘analyse, etc). Les outils fondamentaux utilisés pour effectuer les phases de
synthèse sont la programmation java avancée et l’architecture des ordinateurs. Après cette
introduction nous allons aborder les chapitres suivants :
Chapitre 1: Grammaire, langages réguliers, expressions régulières, automates finis déterministes
(DFA), automates finis non-déterministe (NFA)
Chapitre 2: L’analyse Lexicale en pratique.
Chapitre 3: Analyse Syntaxique: Grammaires hors-contexte, Automate à pile, Analyse descendante
récursive, Tableau axée sur l'analyse descente et analyse ascendante.
Chapitre 4: Analyse Syntaxique en pratique.
Chapitre 5: Analyse sémantique: Grammaires et Sémantique attribués, Contrôle de type et de
compatibilité, règles de traduction, table de symboles et gestion de la portée des
identificateurs
Chapitre 6: Génération de code : Organisation de la mémoire, Génération de code pour les
expressions arithmétique, Allocation des registres, Structures de contrôle : si-alors-sinon,
boucles, etc. Evaluation des expressions Booléennes, et Appels de fonction
Chapitre 7: Optimisations : Graphe de flot de contrôle et Optimisation des boucles.
Références
1. Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman Compilateurs principes, techniques et outils,
2ème édition. Pearson Education, 2007
2. Andrew W. Appel, Jens Palsberg: Modern Compiler Implementation in Java, 2nd edition.
Cambridge University Press 2002, ISBN 0-521-82060-X
3. Alfred Aho, Jeffrey Ullman The Theory of Parsing, Translation and Compiling, Vol I : Parsing
Prentice-Hall, 1972
4. John Hopcroft, Rajeev Motwani, Jeffrey Ullman Introduction to Automata Theory, Languages and
Computation, 2ème édition Pearson Education International, 2001.
5. Jim Larus, Assemblers, Linkers and the SPIM Simulator
6. Henri Garreta, Polycopié du cours de compilation
7. [Link]
8. The Eniac programmers (1997) Kathryn A. Kleiman (Women in Technology, Hall of fame)
9. The ENIAC Story (1961) Martin H. Weik (U. S. Army Research Laboratory, History of Computing
Information)
10. A Very Brief History of Computer Science, texte écrit en 1995 (et revu en 1999) par Jeffrey
Shallit pour ses étudiants de l'Université de Waterloo (Canada)
11. [Link]
12. [Link]
13. [Link]