Utilisation simple de flex, Notions d'unité et et de catégorie lexicale, règle-balai, echo()
Expressions régulières non triviales, Utilisation de variables, Utilisation de "start-condition".
Règle-balai et priorité des règles, Action nulle, Classe de caractères et accents, Utilisation de variables et yywrap(), "Notion" de mot
Expressions régulières et gestion des lignes (\n),
Expressions régulières non triviales, Point de vue théorie des langages.
Gestion de lignes, Ordre des règles, Utilisation de variables, transformation (traduction lexicale) à la volée.
Exemple complet issu d'un TP Noté
Des suggestions en vrac, et sans corrections.
La spécification Flex suivante reconnaît des mots commençant par une lettre, puis pouvant comporter plusieurs lettres ou chiffres :
------ first00.flex
%%
[a-zA-Z][a-zA-Z0-9]* printf("[ %s ]", yytext );
%%
Pour tester, on utilisera l'exemple de texte source suivant :
------ first.data
for( i=0; i < 10; i++ ) {
truc[i] = 0;
machin = 12.3;
bidule = .0;
}
Construisez et testez cet analyseur lexical :
> flex first00.flex > gcc lex.yy.c -ll > ./a.out < first.data
Expliquez le résultat.
Variante : Si la librairie libl.a (-ll) n'existe pas, modifier first00.flex sous la forme :
------ first00-bis.flex
%%
[a-zA-Z][a-zA-Z0-9]* printf("[ %s ]", yytext );
%%
int yywrap(void) { return 1; }
int main(int argc, char *argv[]) { while (yylex()!=0) ; return 0; }
Corrigé :
------ resultat
[ for ]( [ i ]=0; [ i ] < 10; [ i ]++ ) {
[ truc ][[ i ]] = 0;
[ machin ] = 12.3;
[ bidule ] = .0;
}
On recommande l'utilisation de la commande make avec un fichier Makefile générique et on se donne les fichiers suivants comme base pour l'ensemble des exercices :
On suppose alors que :
> make NOM" yywrap()" et "main()" doivent être écrites dans les spécifications FlexQuelques recommandations génériques pour les exercices :
stderr ou stdout.
stderr n'est pas bufferisé contrairement à stdout, cela peut constitué un avantage si c'est bien maîtrisé
Adaptez la spécification précédente "first00.flex" au Makefile générique et testez
Corrigé : first0.flex
a) Modifiez et complétez la spécification pour que l'analyseur reconnaisse les unités lexicales suivantes :
( ) { } ; , [ ]L'affichage distinguera les différentes catégories lexicales. Pour cela, définissez une fonction echo() dans la spécification flex qui affichera pour chaque fragment reconnu, sa catégorie et le contenu du fragment. i.e "[KeyWord:if][Sep:(]..."
Corrigé : first1.flex
Notez la gestion des caractères spéciaux ou méta-caractères flex
b) Complétez l'analyseur précédent :
Le fichier de test "first.data" est disponible en 3 versions, Unix first.data, DOS first.data_DOS ou MAC first.data_MAC. Quelle est la différence? Rendez l'analyseur compatible avec ces 3 versions.
Corrigé : first2.flex
N.B.: Unix utilise '\n' pour la fin de ligne, Mac utilise '\r' et DOS/Windows utilise "\r\n" !!!
Le but est d'écrire un analyseur lexical permettant de reconnaître et de supprimer les commentaires C du type /*... */.
Écrivez une expression régulière pour repérer un commentaire C. Pour la mise au point, faites d'abord un analyseur qui affiche uniquement le contenu du commentaire. Ensuite, supprimez l'affichage des commentaires et rétablissez l'affichage du texte hors commentaire.
Testez sur les 2 exemples suivants
------ comment.data1 commentaire mono-ligne i = 5; /* initialisation au nombre d'objets */
------ comment.data2 commentaire multiligne
void mafonction() {
/* ici
je dois écrire le corps de ma fonction
mais pour l'instant elle est vide
*/
}
Corrigé : comment1.flex
N.B. : ne fonctionne pas pour des commentaires successifs, cf. question suivante
Le caractère "glouton" de flex conduit, si l'on utilise une expression régulière trop simple, à ce que l'analyseur agrège les commentaires successifs en un seul mega commentaires.
Écrivez un analyseur lexical capable de traiter les commentaires successifs avec chacune des stratégies suivantes :
------ comment.data3 commentaire multiligne
i = 5; /* initialisation (*)
au nombre d'objets en i*/
j = 6; /* initialisation (**)
au nombre d'objets en j*/
Corrigé
ATTENTION:
Écrivez un analyseur capable de traiter des commentaires imbriqués et repérant le niveau
d'imbrication des commentaires. On utilisera pour cela une "start-condition" COMMENT et une variable level comme
initié dans la question précédente.
Pour la visualisation du résultat, on pourra utiliser la fonction SET_COLOR(i) dans l'include "proto-color.h" pour afficher
d'une couleur différente chaque niveau de commentaire.
------ comment.data4 commentaires imbriqués
void mafonction2 (){
/*
int i;
int j;
i = 3; /* cette valeur est nickel */
j = 5; /* cette valeur
/* 3eme niveau
/* 4eme */
*/
est a revoir */
printf("afficher i\n");
printf("au revoir\n");
*/
}
Corrigé : comment3.flex
Voilà quelques extraits de texte issus de l'Oulipo: Ouvroir de Littérature Potentielle. Pour chacun, écrire l'analyseur lexical correspondant.
Écrire un analyseur affichant les 'e' contenus dans le texte (utilisation de la règle-balai).
Extrait de "La Disparition" de Georges Perec :
------ lipo1.data « Là où nous vivions jadis, il n'y avait ni autos, ni taxis, ni autobus : nous allions parfois, mon cousin m'accompagnait, voir Linda qui habitait dans un canton voisin. Mais, n'ayant pas d'autos, il nous fallait courir tout au long du parcours; sinon nous arrivions trop tard : Linda avait disparu. Un jour vint pourtant où Linda partit pour toujours. Nous aurions dû la bannir à jamais ; mais voilà, nous l'aimions. Nous aimions tant son parfum, son air rayonnant, son blouson, son pantalon brun trop long ; nous aimions tout. Mais voilà tout finit : trois ans plus tard, Linda mourut; nous l'avions appris par hasard, un soir, au cours d'un lunch. »
Corrigé :
------ lipo1.flex %option nounput noinput %% e ECHO; [ \n\t] . %% int yywrap(void) { return 1; } int main(void) { while (yylex()!=0) ; return 0; }
En asphyxiant un texte, c'est à dire en le privant de R, on obtient un
autre texte qui est dit anaérobie du premier. Écrire un analyseur supprimant les 'r'.
------ lipo2.data cette rosse amorale a fait crouler le parterre
Corrigé :
------ lipo2.flex %option nounput noinput %% r [ \n\t] ECHO; . ECHO; %% int yywrap(void) { return 1; } int main(void) { while (yylex()!=0) ; return 0; }
Écrivez un analyseur supprimant les 'n'.
------ lipo3.data Le chant anime les nombres
Corrigé :
------ lipo3.flex %option nounput noinput %% n [ \n\t] ECHO; . ECHO; %% int yywrap(void) { return 1; } int main(int argc, char *argv[]) { while (yylex()!=0) ; return 0;}
Écrire un analyseur affichant la première lettre de chaque mot.
------ lipo4.data(accents iso-latin1) A brader : cinq danseuses en froufrou (grassouillettes), huit ingénues (joueuses) kleptomanes le matin, neuf (onze peut-être) quadragénaires rabougries, six travailleuses, une valeureuse walkyrie, x yuppies (zélées).
Remarques :
On pourra définir lexicalement un mot :
Pour cet exercice, utilisez la seconde stratégie. Dans l'exercice suivant vous pourrez essayer le première approche.
Corrigé : lipo4.flex
Écrivez un analyseur comptant simultanément :
N.B. : cf. remarques de l'exercice précèdent sur la notion de mot.
------ lipo5.data (accents iso-latin15) Voilà ! Vois en moi l'image d'un humble vétéran de vaudeville, distribué vicieusement dans les rôles de victime et de vilain par les vicissitudes de la vie. Ce visage, bien plus qu'un vil vernis de vanité, est un vestige de la vox populi aujourd'hui vacante, évanouie. Cependant, cette vaillante visite d'une vexation passée se retrouve vivifiée et a fait v½u de vaincre cette vénale et virulente vermine vantant le vice et versant dans la vicieusement violente et vorace violation de la volition. Un seul verdict : la vengeance. Une vendetta telle une offrande votive mais pas en vain car sa valeur et sa véracité viendront un jour faire valoir le vigilant et le vertueux. En vérité ce velouté de verbiage vire vraiment au verbeux, alors laisse-moi simplement ajouter que c'est un véritable honneur que de te rencontrer. Appelle-moi V.
Discours prononcé par V dans le film "V pour Vendetta" (Traduction française par Féodor Atkin):
Résultat attendu : en comptant les 2 apostrophes et les 6 trait d'union comme séparateur de mots, on devrait obtenir 145 mots, 52 commençant par v, 23 ponctuations et 14 lignes. Comparez avec le résultat de la commande wc.
Corrigé : lipo5.flex
A titre d'illustration de l'usage du main() et de yywrap(), une version modifiée de l'analyseur qui accepte en argument de commande une liste de fichier (> lipo5-multi data1 data2 data3 ...) lipo5-multi.flex
On considère un dictionnaire comme le fichier /usr/share/dict/words qui contient
des "mots" ligne a ligne, et l'on désire extraire avec flex (et donc par expressions régulières)
les mots vérifiant certaines propriétés. Ceci s'apparente
directement à la commande Unix grep.
Une difficulté réside dans la gestion de la fin de ligne (\n). On rappel que dans les expressions régulières de Flex :
N.B.: On pourra utiliser l'option flex "%option case-insensitive" pour la gestion des majuscules
Listez les mots contenant une lettre 'q' non suivie de la lettre 'u', ceci comprend les mots terminant par 'q'.
Corrigé : dico1.flex
Dans le Scrabble version anglaise, les lettres les plus chères (10 points) sont 'z' et 'q'. Listez les mots contenant au moins un 'z' et au moins un 'q'.
Corrigé : dico2.flex
Listez les mots contenant exactement un 'z' et un 'q'.
Corrigé : dico3.flex
Listez les mots contenant au moins un 'z', au moins un 'q' et au moins un 'x'.
Corrigé : dico4.flex
Une autre solution plus générique avec moins de flex et plus de code C annexe dico4-gen.flex
Par exemple pour construire des adresses IPv6 humoristiques ou simplement plus faciles à retenir, on cherche des chaînes de chiffres hexadécimaux qui peuvent avoir un sens "littéral". De façon stricte, cela consiste à utiliser uniquement les chiffre-lettres 'a' à 'f'; de façon plus approximative d'utiliser la proximité graphique entre certains chiffres et certaines lettres comme '0' et 'O' ou '2' et 'Z' ...
Exemple DEADBEEF, CAFEBABE, DICECA5E, B16B00B5
Corrigé : dico5.flex
Un alphabet aussi limité offre des exercices d'analyse non triviaux, tout en étant gérables. En effet, il permet d'imaginer des tests relativement systématiques sans que le nombre de possibilités à envisager n'explose "trop vite".
A ce titre, on donne le programme Astar.c qui écrit ligne à ligne tout les mots de taille égale (resp. inférieure ou égale) à N sur un alphabet de taille M. On donne par exemple les fichiers de test
AB5 et AB10 qui sont les mots sur {a,b}* de taille inférieure
ou égale à 5 et à 10. (obtenus avec Astar ab -5 >AB5; Astar ab -10 >AB10)
La théorie des langages montre que l'ensemble des langages réguliers est fermé pour l'opération ensembliste "complémentaire" (et en conséquence aussi pour l'intersection). La construction du complémentaire ou de la négation est triviale si l'on se place du point de vue des automates finis, mais peut être rapidement très difficile du point de vue des expressions régulières.
Pour chacune des questions, il s'agit de reconnaître les mots qui appartiennent et ceux qui n'appartiennent pas à un langage donnée. On s'interdit l'utilisation du mécanisme de règle-balai de flex pour réaliser la négation, mais l'on veut à chaque fois une expression régulière explicite pour chacun des 2 cas : appartient et n'appartient pas.
On suggère ainsi le squelette suivant pour la spécification flex :
------ abba-proto.flex
%option nounput noinput
%{
#include "proto-color.h"
void echo(char *lex_cat) {
fprintf(stdout,GREEN("[%s:%s]"), lex_cat, yytext);
}
void echo1(char *lex_cat) {
fprintf(stdout,REV(GREEN("[%s:%s]")), lex_cat, yytext);
}
void echo2(char *lex_cat) {
fprintf(stdout,RED("[%s:%s]"), lex_cat, yytext);
}
int nbOK=0, nbNOT=0;
%}
OK expression1
NOT expression2
%%
^{OK}$ echo("OK"); nbOK++;
^{NOT}$ echo1("NOT"); nbNOT++;
\n ECHO;
^[ab]*$ echo2("UNK");
.* echo2("UNK");
%%
int yywrap(void) {
printf("Nb_OK = %d, Nb_NOT = %d\n",nbOK,nbNOT);
return 1; }
int main(int argc, char *argv[]) { while (yylex()!=0) ; return 0;}
La solution sera alors correcte (expression1 == Not (expression2) ) si :
Trouvez les expressions régulières pour reconnaître le langage des mots commençant ou finissant par la lettre "a" et le complémentaire de ce langage.
Corrigé : abba1.flex
Trouvez les expressions régulières pour reconnaître le langage des mots ne contenant pas 2 occurrences consécutives de la même lettre et le complémentaire de ce langage.
Corrigé : abba2.flex
Trouvez les expressions régulières pour reconnaître le langage des mots ne contenant pas la chaîne "aba" et le complémentaire de ce langage.
Corrigé : abba3.flex
On trouvera aussi dans les Illustrations d'Automates (ExoGram/Partie1) une résolution systématique par négation sur l'automate fini.
Il s'agit de transformations simples sur un fichier texte ...
On supposera conformément aux "bons usages" qu'un fichier texte se termine toujours par une fin de ligne (ou qu'il est vide). Flex ne fournit
pas de moyen simple de traiter des fragments avec un contexte fin de fichier. Par exemple r$, ne reconnaît pas l'expression r en fin de fichier, sauf si "\n" existe avant la fin de fichier.
Supprimer les lignes vides d'un fichier.
Supprimer aussi les lignes "blanches" c'est à dire ne contenant que des espaces et tabulations.
Supprimer aussi les "blancs" inutiles en fin de ligne.
N.B.1 : Pour la lisibilité, on suggère de visualiser en sortie les fins de ligne par exemple avec fprintf(stdout,GREEN("[\\n]")"\n"); (idem pour blancs et tab)
N.B.2 : Attention au cas de lignes vides en début de fichier
------ filtre1.data (attention aux blancs et tabulation!) pas vide
Corrigé : filtre1.flex
Remplacer les lignes vides consécutives par une seule ligne vide comme le fait la commande Unix "cat -s".
Modifier pour remplacer des lignes consécutives blanches ou vides par une ligne vide.
Variante : Remplacer les blancs consécutifs par un seul blanc.
Corrigé : filtre2.flex
Écrire l'équivalent de la commande Unix "wc" qui affiche le nombre de lignes, le nombre de mots et le nombre de caractères d'un fichier texte.
(Cf. aussi exo 3.5 "Tautogramme")
Pour suivre "wc", on appelle mot, une suite de caractères délimitée par des caractères de la classe Posix [:space:] (==[ \t\n\f\v\r])
Corrigé : filtre3.flex
Écrire l'équivalent des filtres "cat -n" et "cat -b" qui numérotent les lignes d'un fichier. (cf. aussi TP Noté CF2 2014 Sujet+Corrigé.)
Corrigé : filtre4.flex
Écrire un filtre qui rend visible les caractères spéciaux dans un fichier texte comme le font les commande Unix "cat -T", "cat -v" ou "cat -t". (cf. aussi TP Noté 2014)
Un fichier de test : ASCII.data
Corrigé : filtre5.flex
Écrire un filtre qui supprime les tabulations (\t) d'un fichier texte et les remplace par un nombre adéquat de caractères espace. On suppose que l'on a des "taquets" de tabulation tout les 8 caractères, et qu'une tabulation aligne sur le prochain taquet du texte. Ce filtre correspond aux commandes Unix "col -x" ou "expand"
Corrigé : filtre6.flex
Écrire un filtre qui fait la Justification d'un fichier texte sur des lignes de 80 caractères maximum. Les césures se feront sur des caractères blancs (espace ou tabulation). Les tabulations et espaces consécutifs seront remplacés par un seul espace. Les fins de ligne en entrée sont ignorées sauf pour les lignes vides qui sont conservées. Ce filtre s'apparente à la commande Unix "fold -s"
Corrigé : filtre7.flex
Convertir les fins de lignes entre le mode Unix (\n) , Mac (\r) et Dos (\r\n)
Corrigé :
%%
\r\n printf("\n"); /* Dos2Unix */
\r\n printf("\r"); /* Dos2Mac */
\r printf("\r\n"); /* Mac2Dos */
(...)
. ECHO;
%%
Un exemple complet issu du TP Noté 2006.
SVG (Scalable Vector Graphics) est un langage graphique pour définir
des dessins et animations. Le codage "vectoriel" d'éléments de dessin
est compact et permet de les mettre à l'échelle (scalable). Un code
SVG est compatible avec la gestion du Document Object Model, les
style sheets... il est donc insérable dans un fichier XML, sous cette
forme:
<?xml version="1.0"?> <!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> <svg width="140" height="170"> ********** PROGRAMME SVG *********** </svg>
Avec un navigateur sachant interpréter SVG, les graphismes sont donc
exploitables dans une page web. SVG peut s'articuler avec des langages
de scripts, avec XHTML, MathML,... Exemples d'applications sans
animation : description cartographiques, diagrammes UML, visualisation
du graphe du web lui-même. Les aspects animation sont compatibles avec
SMIL, Synchronized Multimedia Integration Language.
------ Exemple de programme SVG : svg3.data (text)
<svg width="140" height="170" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink">
<title>Plan</title>
<desc>Version 0</desc>
<circle cx="70" cy="95" r="50" style="stroke: black; fill: none;"/>
<circle cx="55" cy="80" r="5" stroke="black" fill="#339933"/>
<g id="voies">
<line x1="75" y1="95" x2="135" y2="85" style="stroke: black;"/>
<line x1="75" y1="95" x2="135" y2="105" style="stroke: black;"/>
</g>
<use xlink:href="#voies" transform="scale(-1,1) translate(-140 0)"/>
<polyline points="108 62, 90 10, 70 45, 50 10, 32 62"
style="stroke: black; fill: none;" />
</svg>
Ce que le browser peut visualiser sous la forme :
Deux exemples de fichier de test
------ svg1.data 15 -2 0.5 .999 -0.3 1. - 3 0.1. 14pt 14Pt #040 #2244CC #9999 red grey none gray rgb(20%, 30%, 50%) rgb( 20% 30% 50%) xxxx href #xxxx # polyline
------ Exemple de programme SVG : svg2.data 1, 2, 3 0 0 0 0, 1 1, 2 2 stroke="black" fill="#339933" points="108 62, 90 10, 70 45, 50 10, 32 62" scale(-1,1) transform="scale(-1,1) translate(-140 0)" style="stroke: #999;" style="stroke: #999; fill: none;" style="stroke: gray; fill: #339933;" style="stroke: rgb(20%, 30%, 50%); fill: none;" style="fill: red; stroke: green;" style="font-family: sans-serif; font-size: 14pt; stroke: none; fill: black;" style="font-family: serif; font-size: 8pt; stroke: none; fill: black;"
Implémenter l'analyseur lexical Flex permettant de reconnaître et d'afficher les catégories lexicales suivantes :
15 -2 0.5 .999 -0.3 1.
- 3 0.1.
black gray red green yellow blue
auxquels on ajoute le mot-clé none signifiant l'absence de couleur #040 red #2244CC green none rgb(20%, 30%, 50%)
#9999 grey rgb( 20% 30% 50%)
fill stroke font-family font-size points transform style href
fill -> FILL font-family -> FONT_FAMILY points -> POINTS ...
fill -> COLOR font-size -> FT_SIZE_VAL ...
font-family, les valeurs possibles sont: serif sans-serif
#xxxx: la catégorie REFERENCEhref: la catégorie HREF
EX.: dans la balise <g id="voies">, "voies" est un symbole du programmeur
dans la balise <use xlink:href="#voies" ... >, #voies est une référence
Corrigé : svg.flex
Des suggestions en vrac !
Écrire un analyseur reconnaissant les mots contenant les 5 voyelles
dans l'ordre. On supposera qu'il y a un seul mot à reconnaître par ligne.
------ aeiouy.data oiseau paqerisotu oioiseseauau
Corrigé : aeiouy.flex
Écrire un analyseur lexical pour reconnaître des nombres entiers "aérés", c'est à dire des nombres entiers signés contenant
éventuellement des séparateurs "_" qui sont autorisés uniquement pour les milliers et les puissances de milliers.
Exemples valides : 1234567, 1_234_567, 1234_567, 1_234567, 0_123, -12, +1_234 ...
Exemples invalides : 123_4567, 1234567_, _123, -_123
cf. exercice 1 du TP Noté 2014 : Sujet+Corrigé.
a) Reconnaître des champs "date":
b) Reconnaître des champs "heure", sous la forme hh:mn, pour hh sur [0,23] et mn sur [0,59]
c) Reconnaître des champs "date/time" à partir d'une définition standard de la syntaxe (ABNF) :
Utiliser les spécifications de syntaxe des RFC822 ou RFC2822 pour
faire l'analyse lexicale/syntaxique de mails Internet.
cf. par exemple le TP Noté 2013 Sujet+Corrigé
a) Traiter les cas ci-dessous, supposés non imbriqués entre eux :
Traiter d'abord le cas mono-ligne, étendre au cas multiligne
b) Ajouter la possibilité d'imbrication
N.B.: en réalité, on sort des langages réguliers (cf. Exercice sur les commentaires en C)
Imprimer toutes les lignes d'un texte qui contiennent un motif donné.
Idem pour la négation : toutes les lignes qui ne contiennent pas.
Reconnaître des balises *ml :
Reconnaître des URLs telles que "http://www.maileva.com:80/".
Construire une table de symbole et liste des numéros de ligne des occurrences des symboles dans un fichier
cf. symtab.c
et symtab.h
pour une implémentation générique d'une table de symboles
Ventiler les lignes d'un fichier F dans différents fichiers Fk, k=1,2..N le fichier Fk recevant les lignes caractérisées par une expression EXPk