Rôle de l'analyseur lexical dans un compilateur
Dans un compilateur, l'analyseur lexical transforme le flux d'entrée de caractères (provenant du fichier qui contient le programme source) en un flux de codes numériques qui représentent les unités lexicales (mots-clés, identificateurs, opérateurs, parenthèses, etc).
Il produit également une table des symboles, qui est utile pour retrouver la forme originale des codes représentant les identificateurs (noms de variables, de fonctions...)
But du TP
Le but du TP est de réaliser, avec l'aide de Flex, un analyseur lexical pour un sous-ensemble du C++, le C-. Vous trouverez la description des unités lexicales de C- en cliquant ici.
L'analyseur produit par flex (la fonction yylex()) devra retourner le code du prochain token lu dans le flux d'entrée. Puisque le reste du compilateur n'est pas développé, on se contentera d'un programme principal de test appelant yylex() en boucle et affichant les résultats produits.
Codage des unités lexicales
Pour réaliser un analyseur lexical, il faut tout d'abord convenir d'un codage des unités lexicales. Celles-ci sont de plusieurs types:
Les symboles non alphanumériques (par exemple en C++: + - * / { } [ ] = << >> etc).
Les mots-clés (par exemple en C++: if, while, for, etc).
Les identificateurs: ce sont les noms de variables, types, fonctions... utilisés par le programmeur.
Les valeurs constantes: nous nous limiterons ici aux constantes de type entier (123, 10000, etc), flottant (3.14159, 0.211E-10, etc) et de type caractère ('a', '\n', etc).
Les unités lexicales simples
Les symboles non alphanumériques et les mots-clés peuvent être codés chacun par un entier différent. Par exemple:
symbole code symbole code symbole code
+ 1 { 23 << 45
- 2 } 24 >> 46
* 3 [ 25 || 47
/ 4 ] 26 && 48
...
if 100 for 112 while 124
...
Lorsque l'analyseur lexical reconnaît dans le flux d'entrée un de ces symboles, il émet dans le flux de sortie (ici : l'écran) le code correspondant.
Les valeurs constantes
Dans le flux de sortie de l'analyseur lexical, il faudra émettre dans ces cas:
Les identificateurs
On ne les connaît pas à l'avance. Il faut donc les enregistrer au fur et à mesure de leur apparition dans le programme source, et les stocker dans une table des symboles.
La table des symboles établit la correspondance entre un symbole identificateur (nom de variable ou de fonction, par exemple) et un entier (l'index du symbole dans la table).
Certains identificateurs (comme main, char, int, float) sont prédéfinis : ils font partie du langage et sont chargés dans la table des symboles lors de l'initialisation de l'analyseur lexical. Question : pourquoi n'en fait-on pas des mots-clés ?
Dans le flux de sortie de l'analyseur lexical, il faudra émettre dans ce cas:
Important : L'apparition du même symbole plusieurs fois dans le programme source devra toujours donner lieu à l'émission dans le flux de sortie du même index.
La table des symboles
La table des symboles établit la correspondance entre un symbole identificateur (nom de variable ou de fonction, par exemple) et un entier (index du symbole dans la table).
La structure de données la plus simple pour gérer cette table est un tableau de chaînes de caractères :
extrait de programme:
void segmente()
{
int mesure;
int increment = 1;
int maximise = 0;
mesure = 0;
...
extrait correspondant de la table des symboles:
index chaine 0 segmente 1 mesure 2 increment 3 maximise
Il sera bien entendu nécessaire de disposer d'une fonction de recherche d'une chaîne de caractères dans cette table, ainsi que d'une procédure d'ajout d'une chaîne de caractères dans la table.
Vous pourrez utiliser une représentation de type tableau dans votre TP.
Cependant, il existe des structures mieux adaptées à ce problème, notamment en ce qui concerne la complexité de l'opération de recherche d'une chaîne de caractères. C'est le cas notamment des tables de hachage, parfois appelées aussi tables à adressage dispersé, utilisées dans la plupart des compilateurs (voir par exemple le chapitre 7.6 de "Compilateurs : principes, techniques et outils", A. Aho, R. Sethi, J. Ullman, Interéditions, disponible à la bibliothèque).