Université des Sciences et de la Technologie Houari Boumediene
Faculté d’Electronique et d’Informatique
Département Informatique
TP Compilation
03/11/2021
1
Compilation :
On a l’habitude de faire la compilation des langage naturel qu’on utilise dans notre vie
courante.
J’étudie en master.
Analyse lexicale : la phrase est lexicalement correcte (tous les mots appartient à la langue
française).
Analyse syntaxique : la phrase est syntaxiquement correcte (il existe une règle de
grammaire qui accepte la succession Sujet + Verbe + Complément).
J’en master étudie lexicalement correcte mais syntaxiquement fausse
Analyse sémantique : la phrase est sémantiquement correcte (puisque elle a un sens)
Je mange une table lexicalement et syntaxiquement correcte, mais sémantiquement fausse.
03/11/2021
2
L’analyse lexicale
Structure d’un fichier FLEX
03/11/2021
3
Introduction à la compilation
Erreurs de compilation
Programme source écrit
dans un langage X. Compilateur
Programme compilé est pris pour être exécuté
Plus en détail Exemple
Programme source
Soit le programme C suivant :
Analyse lexicale Erreurs lexicales
Main ()
Entités lexicales {
Analyse syntaxique Erreurs syntaxiques int x, y ;
Table de
if x==2) y=1;
symboles
Arbre syntaxique x=3,14;
}
Analyse sémantique Erreurs sémantiques
• Le pgm est correcte lexicalement,
Génération et
• Le pgm est syntaxiquement incorrecte :
Erreurs manque de la ( dans l’instruction if
Optimisation de code
• Le pgm sémantiquement incorrecte :
x = 3,14
03/11/2021
Programme compilé
4
Analyse lexicale
L’analyseur lexical constitue la première étape d’un compilateur.
Ses tâches principales sont :
La lecture des caractères d’entrée et de la production des entités lexicales en sortie.
L’élimination de caractères superflus : les commentaires, les tabulations, fin de lignes, …
Gérer les numéros de ligne dans le programme source afin de récupérer la ligne dans
laquelle une erreur lexicale est apparue.
Exemple :
Code source avant compilation :
If (x==2) y=z ; /* affectation*/
Après l’analyse lexicale :
Mc_If ( Idf Egal Const ) Idf Aff Idf pvg
03/11/2021
5
Analyse lexicale
L’analyseur lexical est basé sur l’algorithme simple suivant :
Lire (ChaineEntrée) ;
Switch (ChaineEntrée)
Case (ExpReg1) : coder(« Entité1 ») ;
Case (ExpReg2) : coder (« Entité2 ») ;
….
Case (ExpRegN) : coder (« EntitéN ») ;
Default : écrire (« Erreur lexicale ») ;
L’implémentation de cet algorithme nécessitera l’écriture de centaines/milliers de
lignes de code.
Heureusement des outils logiciels, tel que F(lex), existent pour nous faciliter la tâche.
03/11/2021
6
L’analyse lexicale « FLEX »
FLEX est un générateur d’analyseur lexicale.
Il traduit notre analyseur lexical écrit dans un langage simple (FLEX) vers le langage C.
Analyseur lexical flex Analyseur lexical en C
en Flex
MonTp.l [Link].c
But :
Reconnaître les entités lexicales du langage
Exécuter des actions a chaque entité rencontré
03/11/2021
7
Structure d’un fichier FLEX
Un document FLEX comporte trois partie importante séparées par le symbole %%
%{
Définitions en langage C
%} Partie 1
Les définitions des expressions régulière
%%
Les règles de traduction { Action C} Partie 2
%%
Partie 3
Code additionnel :
Redéfinitions des fonctions prédéfinies
03/11/2021
8
Structure d’un fichier FLEX
La partie 1 : Les expressions régulières
But : Donner les ER des différentes entités lexicales sous la forme suivante :
<identificateur_de_l’entité> <expression_régulière>
• identificateur_de_l’entité : doit commencer par une lettre
Il ne comporte que des caractère alphanumériques et des _ ou bien des -
L’expression_régulière doit être valide
Les caractères suivants sont réservés : ils doivent être précédés par \ ou notés entre " " si l'on
veut leur valeur littérale.
03/11/2021
9
Structure d’un fichier FLEX
La partie 1 : Les expressions régulières
caractères significations exemples
+ Répéter 1 ou plusieurs fois x+ x...x
* Répéter 0 ou plusieurs fois t* vide ou t...t
? 0 ou 1 fois a? vide ou a
| union ab|bc ab ou bc
() factorisation (a|b)c ac ou bc
" valeur littérale des caractères "+?"+ +?...+?
\ valeur littérale de caractère qui le précède même entre "" \++ +…+
"\"+ erreur car la première " ne se ferme pas.
. N’importe quel caractère sauf la fin de ligne (\n). .|\n n’importe quel caractère
03/11/2021
10
Structure d’un fichier FLEX
La partie 1 : Les expressions régulières
caractères significations exemples
[...] ensemble de caractères. [aeiou] la voyale :a ou e ou i ou o ou u.
- Utilisé dans [] signifie un intervalle d'ensemble [0-9] 0|1|2|3|4|5|6|7|8|9
^ Utilisé dans [] signifie le complément d'ensemble [^0-9] tout caractère sauf chiffre
Attention :
[...] = ensemble de caractères, pas d'expressions régulières, ce qui veut dire:
[(0|1)+] un des caractères (, ), 0, 1, |, +, pas une suite de 0 ou 1.
Mais les caractères ^, \, - restent des caractères spéciaux.
[^\]] tout caractère sauf ]
03/11/2021
11
Structure d’un fichier FLEX
La partie 1 : Les expressions régulières
Donner une expression régulière qui définit les entités suivantes :
Une suite de caractères alphanumériques qui commence par un caractère alphabétique.
[a-zA-Z]([a-zA-Z]|[0-9])*
Les constantes numérique signées par le (-/+).
[+-]?([1-9][0-9]*|0)
N’importe quel caractère (la fin de ligne (\n) est inclue).
.|\n
Tous les caractère à part les espace, les tabulations et les fins de lignes.
[^ \n\t]
03/11/2021
12
Structure d’un fichier FLEX
La partie 2 : Les règles de traduction
But: présenter l’ensemble des actions associées à chaque entité lexicale sous la forme suivante:
<pattern> <action>
• Un pattern : une expression régulière décrivant une entité lexicale
• Une action : c’est un code C qui sera exécuté à chaque fois qu’une entité lexicale apparaît
Exemple :
{entier } {printf (’’L’entité reconnu est un entier’’) ; }
03/11/2021
13
Structure d’un fichier FLEX %{
int nb_ligne=1;
La partie 2 : Les règles de traduction %}
lettre [a-zA-Z]
Exemple 1: Un analyseur lexical pour le chiffre [0-9]
langage : X=5 ; IDF {lettre}({lettre}|{chiffre})*
cst {chiffre}+
%%
{IDF} printf ("IDF \n");
{cst} printf("cst");
"=" printf ("aff");
";" printf("pvg");
[ \t]
\n {nb_ligne++; }
. printf("erreur lexicale à la ligne %d \n",nb_ligne) ;
%%
Int main ()
{
yylex () ;
return 0
03/11/2021
} 14
Structure d’un fichier FLEX %{
int nb_ligne=1;
%}
La partie 2 : Les règles de traduction lettre [a-zA-Z]
chiffre [0-9]
Exemple 2: Un analyseur lexical pour le IDF {lettre}({lettre}|{chiffre})*
langage : X=5 ; Y=4.5; cst {chiffre}+
réel {chiffre}+ ‘’.’’ {chiffre}+
%%
{IDF} printf (‘’%s’’, yytext) ;
{réel} { printf (‘’%s’’, yytext) ;}
{cst} printf (‘’%s’’, yytext) ;
= printf (‘’aff’’) ;
; printf ( ‘’pvg‘’);
[ \t]
\n {nb_ligne++; }
. printf("erreur lexicale à la ligne %d \n", nb_ligne) ;
%%
Int main ()
{
yylex () ;
return 0 ;
}
03/11/2021
15
Commandes de compilation
Pour compiler le programme :
flex MonTP.l
cc [Link].c -o MonTP -lfl (Linux)
gcc [Link].c -o MonTP -lfl (Windows)
Pour exécuter le programme :
./MonTP
Pour arrêter le programme :
Ctrl + c
03/11/2021
16
Macro-action de FLEX
Fonctions yylex Permet de lancer l’analyseur lexical
yywrap Elle est appelée par le Lexer quand il rencontre la fin du fichier.
Elle doit soit obtenir un nouveau flux d’entrée et retourner simplement la
valeur 0 soit renvoyer 1 signifiant que la totalité des flux a été
consommée et que le lexer a fini sa tâche.
yyterminate Permet de provoquer la fin d’exécution du lexer
ECHO Affiche l’unité lexicale reconnue
Variables yytext Récupère le texte formant le lexème reconnu
yyleng Détermine la langueur du texte contennue dans yytext
yylval Est une variable globale utilisé par FLEX pour stocker la valeur
correspondante au Token reconnu
yylineno Est le numéro de la ligne courante
yyin Fichier d’entrée
yyout Fichier de sortie03/11/2021
17
Exemple
%{
int nb_ligne=1;
%}
lettre [a-zA-Z]
chiffre [0-9]
IDF {lettre}({lettre}|{chiffre})*
cst {chiffre}+ int main( )
%% {
{IDF} printf(" IDF reconnu %s \n",yytext); yyin = fopen( "[Link]", "r" );
{cst} printf(" CST reconnu\n"); if (yyin==NULL) printf("ERROR \n");
"=" printf(" = reconnu\n"); else yylex();
";" printf(" ; reconnu\n"); }
[ \t]
\n nb_ligne++;
. printf("erreur lexicale à la ligne %d \n",nb_ligne) ;
%%
03/11/2021
18
