Le but de ce TP est de mieux comprendre l'analyse lexical, grâce à la découverte d'un outil dévolu à cette tâche : lex.
Lex est un préprocesseur qui, à partir d’un fichier source (respectant la syntaxe lex), produit un fichier C.
C’est une aide à la programmation : le fichier lex que vous avez saisi est souvent bien plus court que le fichier C que vous auriez dû taper.
Vous pourrez utiliser lex à chaque fois que vous aurez à concevoir un analyseur lexical en C.
On rappelle qu’un analyseur lexical est un programme qui reçoit en entrée un flot de caractères (en provenance de l’entrée standard, ou d’un fichier) et qui le découpe en unités lexicales de base : les lexèmes (token).
Normalement, quelle que soit votre distribution GNU/Linux, vous devriez déjà avoir lex.
Si cependant, dans un terminal, la commande lex ne répond pas, vous devrez peut-être installer le package flex.
Voici notre premier programme lex. On le tapera dans un éditeur de textes, et on le sauvegardera sous le nom exemple0.l (l'extension réglementaire pour un fichier lex est .l) :
%{
%}
%%
%%
Voici la marche à suivre pour le compiler et l'exécuter. Dans un terminal, à l’endroit où se trouve exemple0.l, tapez :
$ lex exemple0.l
On obtient alors un fichier C au nom de lex.yy.c, qui contient plusieurs milliers de lignes, chargées en commentaires (vous pouvez l’éditer pour vous en assurer)...et qui ne fait rien !
On va le vérifier. La commande...
$ cc -o nomExecutable lex.yy.c -ll
compile le fichier lex.yy.c (vous pouvez remplacer nomExecutable par le nom de votre choix ; quant à l’option -ll, elle sert à inclure la bibliothèque lex /usr/lib/libl.a).
On exécute alors :
$ ./nomExecutable
Une nouvelle ligne apparaît. Saisissez du texte, puis validez : ledit texte est recopié dans le terminal, sans modification. Bref, vous lui avez dit de ne rien faire (ne pas toucher au flux d’entrée), donc il ne fait rien.
Pour quitter, Ctrl-D.
Les symboles %{, %}, et %% (à deux endroits) sont obligatoires, dans l’ordre d’exemple0.l, et en début de ligne. Lex est rigide à bien des égards, vous vous en rendrez bien vite compte.
Ces symboles séparent le fichier lex en quatre parties, pouvant chacune être vide...
Les quatre parties d’un fichier Lex sont :
%%, qui sera recopiée intégralement dans le fichier C généré, et qui est la place idéale pour définir ses fonctions et son main().
On peut faire des commentaires de la même manière que pour un fichier C, mais pas n’importe où.
Ainsi, un commentaire en première ligne d’un fichier lex engendrera une erreur ; de même, une ligne de règle ne peut pas commencer par un //.
Prenez l’habitude d’écrire un commentaire dans la partie 1 (entre %{ et %}) pour préciser ce qu’est sensé faire le programme.
On souhaite, dans ce qui suit, filtrer les chiffres.
On récupère, à partir de notre flux entrant (le terminal, un fichier...), des caractères, et si ces caractères ne sont pas des chiffres, on les recopie vers la sortie standard.
On souhaite donc que si l’analyseur rencontre un chiffre, il le filtre : c’est une règle (donc partie 3), associée au motif correspondant à un chiffre.
Le ou se traduit en lex par des crochets : [0123456789] signifie donc un chiffre. C’est un peu long à saisir, aussi on peut le noter [0-9].
Dans le même esprit, les lettres b,c ou d se note [bcd], quand une lettre minuscule s’écrit [a-z].
Que faire s’il rencontre le motif [0-9] ? rien. D'où le fichier filtreChiffre.l :
%{
// Filtre les chiffres
%}
%%
[0-9]
%%
Tous les motifs situés entre %% et %% sont interceptés, les autres sont recopiés sans changement à la sortie standard. C’est exactement ce que l’on souhaitait.
Supposons que, après lex et cc, l’exécutable s’appelle filtrerChiffre, et que l’on ait un fichier texte à filtrer, portant le nom de toto.
Cela peut se faire tout simplement :
$ ./filtreChiffre < toto
On peut aussi rediriger la sortie vers un fichier toto2 :
./filtreChiffre < toto > toto2
Améliorons le programme précédent. Supposons que l’on souhaite compter les chiffres d’un fichier.
En face du motif [0-9], on peut associer l’incrémentation d'un compteur :
[0-9] compteChiffre++ ;
Que l’on aura soin d’initialiser dans la partie 1...
%{
// Compte les chiffres
#include <iostream>
using namespace std ;
int compteChiffre=0 ;
%}
...et d’afficher dans le main() de la partie 4, après avoir lancé l’analyseur lexical par un appel à la fonction yylex() :
int main(){
yylex() ;
cout << compteChiffre <<endl ;
}
Cela donne au final ça...
%{
// Compte les chiffres
#include <iostream>
using namespace std ;
int compteChiffre=0 ;
%}
%%
[0-9] {compteChiffre++ ;}
%%
int main(){
yylex() ;
cout << compteChiffre <<endl ;
}
...que l’on compile comme d’habitude :
$ lex compteChiffre.l $ g++ -o compteChiffre lex.yy.c -ll $ ./compteChiffre < toto
où toto est le fichier dont on souhaite compter les chiffres.
Un fichier Lex se compose de quatre parties distinctes :
%{
%} définition de symboles non-terminaux et de contextes%%règles%%partie principale
Comment faire une en-tête lex ?
Pourquoi faire une telle en-tête ?
Vient alors la définition de symboles non-terminaux et de contextes. Pourquoi définir de tels symboles ? D’abord...
Ensuite, pour les contextes :
Pour définir les lexèmes reconnus par le langage qui va être analysé.
Une règle se compose de deux parties :
L’action est une suite d’instructions en langage C, indiquant ce qu’il faut faire à chaque fois que le motif est reconnu.
Par exemple :
[0-9] compteChiffre++ ;
signifie que s’il l’on rencontre un chiffre (le motif), on incrémente le compteur associé d’une unité.
Elles commencent par les caractères (accolés, en début de ligne, etc.) et se terminent de même.
Le motif utilise la syntaxe des expressions rationnelles sed ou egrep.
Entre le motif et l’action associée, il faut au moins un espace ou une tabulation, le tout tenant sur une même ligne.
S’il y a plus d’une action pour un motif donné, on doit encadrer ces actions par des accolades.
La recherche du motif s’arrête naturellement à la fin du fichier.
[a-z] |
[A-Z] printf("Une lettre\n") ;
[0-9]+ printf("Nombre entier reconnu : %d \n",atoi(yytext)) ;
Il se peut qu’une expression puisse marcher avec plusieurs motifs.
Par exemple, si l’on a
. {printf("un symbole") ;}
[a-zA-Z]+ {printf("un mot" ;)}
Passons maintenant à la partie principale :
S’il n’y a pas de main(), lex écrira :
int main(){
yylex() ;
}
yylex(), fonction sans paramètre et retournant un entier, définie par le lex (vous n’avez pas à vous en préoccuper), est la fonction d’analyse lexicale écrite par le lex à partir de vos règles.
Vous devrez l’appeler, dans le cas où vous faites votre propre main(), si du moins vous souhaitez que votre flux soit analysé.
On rappelle ci-dessous les règles des expressions rationnelles, adaptées à lex.