Exercices d'utilisation de JFlex (seul)
Prologue
Installation logicielle pour le module
Pour le module, vérifier l'installation qui suit :
- on programme en JAVA car c'est le langage appris dans le module CSC3101. Vérifier que vous avez une version ≥ 17 ;
- on construit les compilateurs avec l'outil Maven, qui est présenté lors du premier cours. Vérifier que vous avez une version ≥ 3.8.6. Cf. les instructions d'installation de Apache Maven ;
- les quelques scripts utilisés sont écrits en Bash, car c'est le langage appris dans le module CSC3102. Vérifier que vous pouvez exécuter des scripts Bash.
Par exemple, voici l'installation de JAVA et de Maven sur les machines des salles de TP :
Mise en place de l'environnement du cours
Récupérer le code des exercices JFlex (seul) et JFlex+CUP
Dans le répertoire, construisez tous les projets Maven en exécutant la commande make.
Pour les projets JFlex (seul), dans
l'arborescence JFlexExercices, par
exemple JFlexExercices/JFlexExercice01 estla
suivante :
Selon le processus de construction du compilateur défini dans le fichier pom.xml, les cibles principales suivantes sont disponibles (voir aussi la figure qui suit) :
- mvn clean generate-sources : créer l'analyseur lexical, c'est-à-dire la classe Yylex sans compiler ni exécuter les tests ;
- mvn clean install : construire et exécuter les tests du compilateur ;
- mvn test : une fois le compilateur construit (incluant aussi les classes de tests), exécuter les tests sur un nouveau contenu d'un des fichiers à analyser par le compilateur. Cette cible est utile lorsque l'on veut tester sans changer le compilateur mais sur un autre contenu d'un des fichiers à analyser.
Quelques adaptations possibles simples :
- changer le fichier de spécification JFlex dans le fichier pom.xml en modifiant le contenu de la balise <lexDefinition> ;
- changer le fichier pour les tests dans la classe TestCompiler ;
- créer un nouveau test avec un nouveau fichier en entrée en créant un nouveau test par mimétisme de la méthode TestCompiler::test1 ;
- ne tester que la génération de l'analyseur lexical Yylex avec la commande mvn generate-sources.
Utilisation de l'IDE Eclipse
Dans la question précédente, nous avons observé le projet Maven JFlex (seul) de nom jflex_exercice_01. Nous rappelons ici l'arborescence qui suit :
On peut réaliser la génération JFlex soit de façon externe à Eclipse avec les commandes Maven, soit de façon intégrée sous Eclipse avec le menu contextuel du projet Eclipse Run as.... Dans les deux cas, la commande Eclipse > File > Refresh (F5) est utile pour assurer la bonne synchronisation d'Eclipse avec le système de fichiers. Pour limiter le recours au Refresh (F5), on peut activer la préférence Eclipse > Window > Preferences > General > Workspace avec « Refresh using native hooks ».
Pour créer le projet, Eclipse demande deux fichiers de configuration : .project et .classpath. Voici la manière de procéder :
-
il s'agit d'utiliser le greffon m2e
(Maven to Eclipse)
de Eclipse : au lieu de créer le projet
dans Eclipse comme un projet JAVA,
importez-le comme un projet Maven
(menu File > Import > Maven
> Existing Maven Projects > Next
puis Browse
> $HOME/CSC4251_4252/csc4251_4252-exercices et
enfin Finish). Dans ce cas, c'est Eclipse
qui crée les fichiers de
configuration .project
et .classpath. Dans la vue « package
explorer » de Eclipse, un
« M » est ajouté à côté du
« J » sur l'icone du projet et les
cibles Maven sont disponibles dans le menu
contextuel : clic droit > Run
As :
- Maven clean : supprimer le répertoire target pour effacer tout ce qui a été généré et compilé. Un effet de bord est de voir des erreurs de compilation dans Eclipse : en effet, la classe de l'analyseur lexical Yylex a disparu ;
- Maven generate-sources : exécuter JFlex pour générer la classe de l'analyseur lexical Yylex. Comme Eclipse s'aperçoit que le code a changé, le projet est re-compilé et l'erreur de compilation disparaît lorsque la génération JFlex s'est bien passée ;
- Maven test : exécuter les tests JUnit selon les classes dans l'arborescence src/test/java et qui comportent dans leur nom la chaîne de caractères Test ;
- Maven install : construire le compilateur en enchaînant generate-sources, compile, test-compile, test, etc.
Premiers pas – Analyse lexicale d'un langage de programmation
Exécution manuelle (optionnelle)
[Lire la section 1 du mémento JFlex]
Avant d'utiliser uniquement les modules Maven, regardons une curiosité (le mode « traditionnel » appelé standalone) de JFlex en utilisant l'archive jflex.jar (à télécharger).
Soit une spécification JFlex : et un exemple de données : Construire l'analyseur lexical, exécuter sur l'exemple, et suivre les explications qui suivent.
Dans cet exemple de spécification JFlex, tout est reporté en sortie, mais on identifie les fragments reconnus (ici les identificateurs) en les marquant entre crochets. Il s'agit du fonctionnement « traditionnel » de lex/flex qui applique une règle-balai implicite qui imprime les caractères non reconnus. Dans toute la suite, on oubliera ce fonctionnement « traditionnel » et le mode %standalone de JFlex et on écrira toujours une règle-balai explicite pour définir le traitement des caractères non reconnus.
Environnement du cours
[Lire les sections 1, 2 et 3 du mémento JFlex]
Dans le prologue de cette page, vous avez récupéré le projet Maven JFlex jflex_exercice_01.
Refaire la question précédente avec l'environnement du cours :
- Remplacer le contenu de la spécification JFlex dans le fichier src/main/resources/spec.jflex par le contenu du fichier qui suit :
- Regarder en particulier la définition des méthodes ECHO(), WARN() et WHERE() dans le fichier src/main/resources/Jflex.include.
- Dans la classe de test TestCompiler, remplacer le fichier input.txt par le fichier input1b.txt
-
Tester la spécification avec des commandes Maven,
c.-à-d. :
- dans un terminal, avec la commande mvn clean install ;
- dans Eclipse, avec l'utilisation par le menu contextuel du projet Maven, Run As > Maven clean puis Run As > Maven install.
Une fois la classe JAVA de l'analyseur lexical Yylex générée et toutes les classes JAVA compilées, on peut tester le compilateur sans commande Maven :
- dans Eclipse, sélectionner la classe des tests à exécuter TestCompiler et utiliser le menu contextuel Run As > JUnit Test ;
-
dans Eclipse, sélectionner la classe du
compilateur Compiler et utiliser le menu
contextuel Run As > JAVA Application. Dans la vue
« console » de Eclipse, le message suivant est
affiché :
On peut alors entrer des lignes de texte à analyser. Pour terminer cette saisie interactive, le caractère de fin de fichier EOF s'obtient avec Ctrl-d.=== Étape 1 Analyse Lexicale === Reading standard input Analyse Lexicale (type any text) :
Analyseur lexical d'un langage de programmation
[Lire la section 4 du mémento JFlex]
Modifier et compléter la spécification précédente pour reconnaître les catégories lexicales suivantes :
- identificateur,
- mot-clé du langage : for, while, if...
- opérateur arithmétique : + * / -,
- opérateur de comparaison : < >,
- opérateur d'affectation et d'incrément : = += ++ ,
- séparateur : () {} ; , [],
- nombre entier ou flottant.
Compléter avec :
- une règle-balai générant un avertissement pour les caractères non reconnus (méthode WARN(..)),
- une catégorie "commentaire" pour ignorer les commentaires de style C++ (//... fin_de_ligne),
- d'autres catégories jusqu'à éliminer les caractères non reconnus. (blancs, etc.).
Exemple de résultat attendu :
le Graal
Pour réaliser une analyse lexicale complète et conforme du langage C 2011, il faut de l'ordre de 150 lignes de spécification lexicale : spécification Lex/Yacc pour ISO-C 2011.
Oulipo
Cf. le répertoire JFlexExercice02 avec le projet Maven jflex_exercice_02.
Lipogramme sans e
Tester sur un extrait de "La Disparition" de Georges Perec : fichier src/test/resources/input2a_oulipo_lipogramme_sans_e.txt
Asphyxie ou Lipossible
En asphyxiant un texte, c'est-à-dire en le privant de la lettre "r", on obtient un autre texte qui est dit anaérobie du premier.
Écrire un analyseur supprimant les "r".
Exemple dans le fichier src/test/resources/input2b_asphyxie_ou_lipossible.txt
Variante sans haine
Écrire un analyseur supprimant les "n".
Exemple dans le fichier src/test/resources/input2c_variante_sans_haine.txt.
Abécédaire
Écrire un analyseur affichant la première lettre de chaque mot (Indication : utiliser la méthode String.CharAt(int i)).
- 1 ou 2 mots ? : « Aujourd'hui », « l'amusement », « amuse-toi », « amuse-gueule »
- Et le « qu'en-dira-t-on » de la « pomme de terre » quand tout va « à vau-l'eau »
- Bref, le Mot est une notion sémantique qui ne répond pas toujours à une définition lexicale rigoureuse.
Exemple dans le fichier src/test/resources/input2d_abecedaire.txt.
Recherches dans un dictionnaire
- [^xyz] reconnaît la fin de ligne,
- . ne reconnaît pas la fin de ligne,
- ^ et $ reconnaissent la fin de ligne sans la "manger",
- ^ regexp $ est interdit, si l'expression regexp peut être vide.
Le projet de cet exercice, nommé jflex_exercice_03 est dans le répertoire JFlexExercice03.
Du cul pas cucul
Lister les mots contenant une lettre « q » non suivie de la lettre « u ». Ceci comprend les mots terminant par « q ».
Résultats sur /usr/share/dict/words : 308 mots comme « Aqaba », « antiq », « FAQ », « FQDN »...
Exemple dans le fichier src/test/resources/input3a_du_q_pas_culcul.txt.
Scrabble
Dans la version anglaise du Scrabble, les lettres les plus chères (10 points) sont « z » et « q ».
Lister les mots contenant au moins un « z » et au moins un « q »
Résultats sur /usr/share/dict/words : 253 mots comme Byzantinesque, benzoquinoxaline, quartz, Velasquez...
Exemple dans le fichier src/test/resources/input3b_scrabble.txt.
Top Scrabble
Lister les mots contenant exactement un « z » et un « q ».
Résultats sur /usr/share/dict/words : 219 mots.
Exemple dans le fichier src/test/resources/input3c_top_scrabble.txt.
Super Top Scrabble
Lister les mots contenant au moins un « z », au moins un « q » et au moins un « x ».
Résultats sur /usr/share/dict/words : 6 mots, benzofuroquinoxaline, benzoquinoxaline. extraquiz, quixotize, soixante-quinze, squeeze-box.
Exemple dans le fichier src/test/resources/input3d_super_top_scrabble.txt.
Dead Beef – hexspeak – leet speak
On cherche des chaînes hexadécimales 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 »...
Lister en même temps les mots du dictionnaire :
- contenant uniquement des lettres a, b, c, d, e ou f,
- contenant uniquement des lettres a, b, c, d, e ou f, ou encore 0, I, Z, S ou G (approximations de 0, 1, 2, 5 ou 6),
- de 4 lettres contenant uniquement des lettres a, b, c, d, e ou f,
- de 4 lettres contenant uniquement des lettres a, b, c, d, e ou f ou 0, I, Z, S ou G.
Exemples : DEADBEEF, CAFEBABE, DICECA5E, B16B00B5...
Exemple dans le fichier src/test/resources/input3e_dead_Beef_hexspeak_leet_speak.txt.
ABBA
La théorie des langages montre que l'ensemble des langages réguliers est fermé pour l'opération ensembliste « complémentaire ». La construction du complémentaire est facile si l'on se place du point de vue des automates finis, mais devient 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é en écrivant une expression régulière explicite pour chacun des deux cas. On s'interdit de tricher en utilisant des mécanismes de JFlex comme les règles-balais ou l'opérateur de négation.
Cf. le répertoire JFlexExercice04 avec le projet Maven jflex_exercice_04.
On se place sur l'alphabet {a, b}* et on validera les solutions en testant sur tous les mots de taille fixée. On donne le programme Astar.java qui génère ligne à ligne tous les mots de taille égale (resp. inférieure ou égale) à N sur un alphabet de taille M (documentation dans le code ou à l'exécution sans argument). Voici un fichier de données exemple résultant de la commande java Astar.java ab 10 : astar_ab_10.txt.
On utilisera le squelette suivant comme spécification JFlex :
Seules les lignes OK= et NOT= sont à éditer pour chacune des questions.
Une solution est correcte si :
-
Réunion « pleine » : aucun mot n'est
reconnaissable par la règle-balai [ab]*.
Ceci sera validé à la compilation par JFlex avec un message Rule can never be matched pour la règle [ab]*. -
Intersection vide : le résultat ne dépend pas de l'ordre
des 2 premières règles.
Ceci sera validé en testant sur un grand nombre de mots.
Ancien Alcoolique Anonyme
Trouver 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
Indication : Astar avec ab -10, puis analyse lexicale donne « OK = 1534, NOT = 513 ».
Exemple dans le fichier src/test/resources/input4a_abba_ancien_alcoolique_anonyme.txt.
Bébé bègue
Trouver 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.
Indication : Astar
avec ab -10, puis analyse lexicale donne
« OK = 21, NOT = 2026 ».
Exemple dans le fichier src/test/resources/input4b_bebe_begue.txt.
Béaba ou b.a.-ba (difficile !)
Trouver 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.
Indication : Astar
avec ab -10, puis analyse lexicale donne
« OK = 814, NOT = 1233 ».
Exemple dans le fichier src/test/resources/input4c_beaba_ou_b_a_ba.txt.
Bonus
Pour valider les réponses précédentes, on peut aussi utiliser l'opérateur de négation présent dans JFlex (et correcte depuis JFlex 1.8.2, merci au cours Compil !). Il suffit de vérifier que JFlex indique à la génération que la règle balai ne sera jamais appliquée pour les 2 spécifications suivantes :
Commentaire en C
Cf. le répertoire JFlexExercice05 avec le projet Maven jflex_exercice_05.
Le but est de reconnaître et de supprimer les commentaires C du type /*... */. Pour le débogage, l'analyseur indiquera clairement les commentaires reconnus même si il n'en affiche pas obligatoirement le contenu.
Un exemple pour tester :Expression régulière
- Expliquer pourquoi les expressions régulières "/*".*"*/" ou "/*"[^]*"*/" ne sont pas satisfaisantes.
-
Écrire une expression régulière pour reconnaître un
commentaire C.
Trouver une négation pour .* "*/" .*. -
Tester l'expression "/*"&nbs;~"*/"
(opérateur UpTo de JFlex), et utiliser cette
expression pour valider votre solution.
Deux expressions sont équivalentes si quelque soit l'ordre dans la spécification la première règle empêche la deuxième de s'appliquer (message Rule can never be matched à la compilation JFlex).
Exemple dans le fichier src/test/resources/input5a_commentaire_en_c_expression_reguliere.txt.
Super-état (bonus)
[Lire la section 6 du mémento JFlex]
Reconnaître les commentaires en utilisant les super-états de JFlex (directive %state ou %xstate)
Exemple dans le fichier src/test/resources/input5b_super_etat.txt.
Commentaires sans automate (optionnel)
- Les commentaires imbriqués n'existent pas en C.
- Ce que l'on cherche à faire sort du domaine des langages réguliers et concerne les langages algébriques. On triche donc avec l'objectif de JFlex.
Reconnaître les commentaires sans utiliser d'automates (expressions régulières ou super-états) mais en utilisant une variable entière qui compte le niveau d'imbrication. Accepter et identifier les commentaires imbriqués avec leur niveau d'imbrication.
Exemple dans le fichier src/test/resources/input5c_commentaires_sans_automate.txt.
WC
Cf. le répertoire JFlexExercice06 avec le projet Maven jflex_exercice_06.
É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. Les mots sont ici des séquences de caractère séparées par des "espaces".
Exemple dans le fichier src/test/resources/input6_wc.txt.
La Vengeance de l'Oulipo
Cf. le répertoire JFlexExercice06 avec le projet Maven jflex_exercice_06.
Écrire un analyseur comptant simultanément :
- le nombre total de mots,
- le nombre de mots commençant par la lettre « v »,
- le nombre de caractères de ponctuation,
- le nombre de lignes.
Avec les exemples issus du discours prononcé par V dans le film « V pour Vendetta » (Traduction française par Féodor Atkin) : src/test/resources/input7_la_vengeance_de_l_oulipo_francais.txt src/test/resources/input7_la_vengeance_de_l_oulipo_english.txt
Résultats attendus :
v_oulipo.data : nb_v = 52, nb_mots = 143, nb_punct = 21, nb_lignes = 14
v_oulipo-VO.data : nb_v = 49, nb_mots = 127, nb_punct = 20, nb_lignes = 10
Filtres
Cf. le répertoire JFlexExercice06 avec avec le projet Maven jflex_exercice_06.
Lignes vides
Écrire un filtre qui supprime :
- les lignes vides,
- les lignes blanches (uniquement espaces et tabulations),
- les blancs inutiles en fin de ligne.
Exemple dans le fichier src/test/resources/input8a_filtres_lignes_vides.txt.
Lignes vides et cat -s
Écrire un filtre qui remplace des lignes blanches ou vides consécutives par une seule ligne vide.
Comparer avec la commande UNIX cat -s.
Exemple dans le fichier src/test/resources/input8b_lignes_vides_et_cat_moins_s.txt.
Numéros de ligne, cat -n et cat -b
Écrire l'équivalent des filtres cat -n et cat -b qui numérotent les lignes d'un fichier.
Exemple dans le fichier src/test/resources/input8c_numeros_de_ligne_cat_moins_n_b.txt.
Détabulation, expand ou col -x
Écrire l'équivalent des filtres expand ou col -x qui remplacent les tabulations par des espaces.
On suppose que l'on a des « taquets » de tabulation tous les 8 caractères, et qu'une tabulation aligne sur le prochain taquet du texte.
Exemple dans le fichier src/test/resources/input8d_detabulation_expand_ou_col_moins_x.txt.
Justification, fold -s
Écrire un filtre qui fait la justification d'un texte sur des lignes de 80 caractères. Les césures se font sur des caractères blancs. Les tabulations et espaces consécutifs sont 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.
Comparer avec la commande UNIX fold -s.
Exemple dans le fichier src/test/resources/input8e_justification_fold_moins_s.txt.
CSC4251_4252, Télécom SudParis, Pascal Hennequin, J. Paul Gibson, Denis Conan, Dernière modification : Juillet 2025
