Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
INTRODUCTION
Qu'est ce qu'un compilateur?
Un compilateur est un logiciel qui traduit un programme source écrit dans un langage de haut niveau en un
programme équivalent écrit dans un langage cible appelé aussi programme objet.
Ce langage cible peut être:
- Le langage machine
- L'assembleur
- Ou un langage intermédiaire.
On peut distinguer aussi d'autres formes de compilation:
- Les interpréteurs: contrairement aux compilateurs, un interpréteur analyse et exécute les instructions du
programme source une après l'autre.
- Les traducteurs: la compilation peut être aussi une traduction d'un langage à un autre (par exemple du C++
vers JAVA) ou d'un format à un autre (par exemple du Word vers HTML)
Les qualités d'un compilateur
Le programme cible doit être équivalent au programme source.
Le temps de compilation doit être proportionnel à la taille du programme source.
Le code produit doit être efficace en temps et en espace.
Le diagnostique d'erreurs doit être de très bonne qualité.
La possibilité d'utiliser un debugger sur le code produit.
Structure d'un compilateur
La compilation se décompose en deux phases (figure 1):
(1) Une phase d'analyse (partie frontale): qui permettra de reconnaitre les variables, les instructions, les
opérateurs, … et élaborer la structure syntaxique du programme ainsi que certaines propriétés sémantiques.
(2) Une phase de synthèse et de production (partie finale): qui consiste en la production du code.
Table des symboles
Partie Partie
Code Représentation intermédiaire Code
Source frontale finale cible
Gestionnaire des erreurs
Figure 1: phases de compilation
La table des symboles et le gestionnaire des erreurs sont des phases parallèles.
Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
Table des symboles
C'est une structure de données utilisée pour stocker des informations concernant les variables du programme source
(le type, l'emplacement en mémoire, la portée, la visibilité, …)
Gestionnaire des erreurs
Il a pour rôle de détecter et d'informer l'utilisateur le plus précisément possible des erreurs rencontrées (les erreurs
de syntaxe, de sémantique, …).
Les étapes de la phase d'analyse (figure 2)
(1) Analyse lexicale (scanner) appelée aussi analyse linéaire (Eliminer les caractères superflus, identifier les mots
qui composent le texte, …)
Les outils: les expressions régulières, les automates à états finis
(2) Analyse syntaxique (parser) appelée aussi analyse hiérarchique ou grammaticale: Il s'agit de découvrir la
structure du programme source et de vérifier s'il respecte la grammaire du langage.
Les outils: les grammaires, les automates à pile
(3) Analyse sémantique appelée aussi analyse contextuelle: Il s'agit de vérifier certains aspects sémantiques (les
déclarations, les types, la consistance des expressions, …)
Les outils: la définition dirigée par la syntaxe (DDS)
Les étapes de la phase de synthèse
(1) Génération du code: En général, un compilateur produit un code intermédiaire pour une machine virtuelle
qui traduit par la suite en code machine
Outils: la traduction dirigée par la syntaxe (TDS)
(2) Optimisation du code: Il s'agit d'améliorer le code produit afin d'augmenter son efficacité (éliminer les
calculs inutiles, …)
Outils: des algorithmes d'optimisation
Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
Programme
Source
Analyse lexicale
(scanner)
Phase d'analyse
Partie frontale
Ou
Gestion des erreurs Analyse syntaxique
(parser)
Table des symboles
Analyse sémantique
Génération du code
Phase de synthèse
Partie finale
Ou
Optimisation du code
Programme
objet
Figure 2: Structure générale d'un compilateur
Exemple Langage simplifié des expressions arithmétiques
Une grammaire G (S,N,T,P) où: - P l'axiome
- N = {P,S,E,D,I,T,L,OP} l'ensemble des non terminaux
- T = {; , entier reel = + * ident nombre}
- P ensemble de productions:
P={ PS
S DI
DTLD |TL
T entier | reel
L id,L | id ;
I id=E;
E E OP E | ident | nombre
OP+|* }
Définitions des unités lexicales (tokens)
- ID : "ident" est une suite de lettres alphabétiques ( l ) et de chiffres ( c) dont le premier caractère est une
lettre l ( l | c )* .
- NBR: "nombre" est suite non vide de chiffres pour les entiers (c+) ou une suite de chiffres suivie d'un point
suivi d'une autre suite de chiffres (c+.c*|c*.c+)
- OPA: liste d'opérateurs arithmétiques {+, *}
- L'opérateur d'affectation {=}
- Liste de séparateur {, ;}
Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
Programme Source
entier i ;
reel p,v ;
p=i+v*60 ;
Analyse lexicale
Modèle 1: élimination des délimiteurs 0 " " |tabulation|saut de ligne
2 return("OPA");
+/*
1 = 3 return("=");
Modèle 2: reconnaissance des lexèmes spéciaux
,
4 return(",");
;
5 return(";");
Modèle 3: reconnaissance des identificateurs 6 l 7 l |c
si "entier" ou "reel" return ("TYPE") sinon return("ID");
c 9
. 10
c return("NBR");
Modèle 4: reconnaissance des nombres 8
. 11
c 12 c
Autre: Erreur
<entier,TYPE> <i,ID> <;> <reel,TYPE> <p,ID> <v,ID>
Programme
Analyseur <;> <p,ID> <=> <i,ID> <+,OPA> <v,ID> <*,OPA>
Source
lexical <60,NBR> <;>
Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
Analyse syntaxique
S
<entier,TYPE> <i,ID> <;> D I
<reel,TYPE> <p,ID> <v,ID>
<;> <p,ID> <=> <i,ID> Analyseur T L D p = E ;
<+,OPA> <v,ID> <*,OPA> syntaxique
<60,NBR> <;> entier i ; E OP E
T L ; + E OP E
reel p , L v * 60
v ;
Arbre syntaxique ou de dérivation
Ident Type Adresse ….
p réel
i entier
v réel
Table des symboles
Analyse sémantique: Vérification de la consistance de l'instruction (déclaration et type)
Génération du code intermédiaire trois adresses:
t1=intoReal(60);
t2=v*t1;
t3=i+t2
p=t3;
Optimisation:
t1=v*60.0;
p=i+t1;
Génération du code final (Programme objet):
LDF R2,v
MULT R2,#60.0
LDF R1,i
ADDF R1,R2
SET R1,p
Cours de compilation Mr HAMMOUDA Mohamed
ème
USDB, 3 année licence, SI
Implémentation en Flex/Bison
L'analyseur lexical Alex.l L'analyseur syntaxique ASynt.y
%{ %{
/* /* Déclaration en C de variables,
Déclaration en C de variables, constantes, de constantes, inclusions de fichiers … */
inclusions de fichiers
*/ #include <stdio.h>
#include <stdlib.h>
#include "[Link].h" #include <math.h>
#include <stdlib.h>
%}
%} /* Déclaration des unités lexicales
/* de priorités et de types */
Déclarations des définitions régulières
*/ %token NBR TYPE ID OPA
%token FIN VIR PVIR AFF
blancs [ \t\n]+
lettre [a-zA-Z] %left '+'
chiffre [0-9] %left '*'
reel ({chiffre}*"."{chiffre}+)
| ({chiffre}+"."{chiffre}*) %start P
entier {chiffre}+
type "entier"|"reel" %%
ident {lettre}({lettre}|{chiffre})* /* Les règles de production et actions
operat "+"|"*" Sémantiques */
%% P: S
/* règles de traductions */ ;
{blancs} { /* On ignore */ } S: FIN {YYACCEPT;}
| D I { printf("correct syntax");YYACCEPT;}
{reel} return(NBR); ;
{entier} return(NBR);
{type} return(TYPE); D: T L D
{ident} return(ID); | T L
{operat} return(OPA); |
"," return(VIR); ;
";" return(PVIR);
"=" return(AFF); T: TYPE
"{" return(AO); ;
"}" return(AF);
L: ID VIR L
"$" return(FIN); | ID PVIR
;
%%
I: ID AFF E PVIR I
/* bloc principal et fonctions auxiliaires */ |
;
E: E OPA E
| ID
| NBR
;
%%
/* Les routines C et bloc principal */
int yyerror(char *s) {
printf("%s\n",s);
}
int main(void) {
yyparse();
}
