CSC4251_4252 — Compilation : du langage de haut niveau à l'assembleur

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 :

$ java -version
openjdk version "21.0.4" 2024-07-16
OpenJDK Runtime Environment (build 21.0.4+7-Ubuntu-1ubuntu224.04)
OpenJDK 64-Bit Server VM (build 21.0.4+7-Ubuntu-1ubuntu224.04, mixed mode, sharing)
$ mvn -version
Apache Maven 3.9.7 (8b094c9513efc1b9ce2d952b3b9c8eaedaf8cbf0)
Maven home: /opt/maven
Java version: 21.0.4, vendor: Ubuntu, runtime: /usr/lib/jvm/java-21-openjdk-amd64
Default locale: fr_FR, platform encoding: UTF-8
OS name: "linux", version: "6.8.0-39-generic", arch: "amd64", family: "unix"

Mise en place de l'environnement du cours

Récupérer le code des projets JFlex (seul) et JFlex+CUP

$ mkdir -p $HOME/CSC4251_4252
$ cd $HOME/CSC4251_4252
# si vous préférez, connectez-vous à l'adresse https://gitlabense.imtbs-tsp.eu/csc4251_4252/csc4251_4252-archetypes-maven
# et téléchargez l'archive via le bouton/menu « Code » puis « zip » ou une autre archive
$ git clone git@gitlabense.imtbs-tsp.eu:csc4251_4252/csc4251_4252-archetypes-maven.git
$ cd csc4251_4252-archetypes-maven
$ ls
compil-nouveau-cup-jflex.sh   csc4251_4252-cup-jflex-sample0  Makefile
compil-nouveau-jflex-seul.sh  csc4251_4252-jflex-sample0      readme.md

Dans le fichier readme.md, suivre la section « Configuration » pour, au besoin, créer le répertoire $HOME/.m2 pour le dépôt local Maven et pour, au besoin, créer le fichier $HOME/.m2/settings.xml pour la configuration du dépôt local.

# vous devez avoir ce qui suit
$ ls -1 $HOME/.m2
...
settings.xml

Dans le fichier readme.md, suivre la section « Construction des artefacts » (incluant la création des archétypes) :

# après make, vous devez avoir ce qui suit
$ cat $HOME/.m2/repository/archetype-catalog.xml | grep  jflexsample0
      jflexsample0-archetype
      jflexsample0-archetype
      cupjflexsample0-archetype
      cupjflexsample0-archetype

Dans le fichier readme.md, suivre la section « Configuration de votre compte » pour modifier votre environnement shell :

# vous devez avoir ce qui suit
$ alias | grep compil
alias compil-nouveau-cup-jflex='.../CSC4251_4252/csc4251_4252-archetypes-maven/compil-nouveau-cup-jflex.sh'
alias compil-nouveau-jflex-seul='.../CSC4251_4252/csc4251_4252-archetypes-maven/compil-nouveau-jflex-seul.sh'

Dans le fichier readme.md, suivre la section « Construction d'un nouveau projet JFlex (seul) » pour construire le projet qui sert à la question suivante pour les premiers pas :

$ compil-nouveau-jflex-seul jflex_exo1_premierspas
création d'un projet JFlex seul dans le repertoire jflex_exo1_premierspas
...
[INFO] Installing .../CSC4251_4252/jflex_exo1_premierspas/target/jflex_exo1_premierspas-0.1.0-SNAPSHOT.jar to .../.m2/repository/eu/telecomsudparis/csc4251_4252/jflex/jflex_exo1_premierspas/0.1.0-SNAPSHOT/jflex_exo1_premierspas-0.1.0-SNAPSHOT.jar
[INFO] Installing .../CSC4251_4252/jflex_exo1_premierspas/pom.xml to .../.m2/repository/eu/telecomsudparis/csc4251_4252/jflex/jflex_exo1_premierspas/0.1.0-SNAPSHOT/jflex_exo1_premierspas-0.1.0-SNAPSHOT.pom
[INFO] Installing .../CSC4251_4252/jflex_exo1_premierspas/target/jflex_exo1_premierspas-0.1.0-SNAPSHOT-tests.jar to .../.m2/repository/eu/telecomsudparis/csc4251_4252/jflex/jflex_exo1_premierspas/0.1.0-SNAPSHOT/jflex_exo1_premierspas-0.1.0-SNAPSHOT-tests.jar
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
...
$ cd jflex_exo1_premierspas/
$ ls
pom.xml  readme.md  src  target

L'arborescence fournie est la suivante :

src/main/resources/jflex_exo1_premierspas/ : le fichier de spécification JFlex (jflex_exo1_premierspas.jflex) ainsi qu'un exemple de fichier de données à analyser (jflex_exo1_premierspas.txt) ;
src/main/java/compil/ : quelques classes JAVA permettant d'exécuter l'analyseur lexical généré par JFlex (compil.Compiler avec la méthode main) ;
src/test/java/ : les classes pour les tests (TestCompiler analyse par défaut le fichier de données en entrée cité ci-avant, c.-à-d. jflex_exo1_premierspas.txt).
target/classes/compil/Yylex.class : le répertoire target n'existe qu'après la construction du logiciel, c'est-à-dire après l'exécution de la commande mvn install, ou au minimum mvn generate-sources.

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.

Processus Maven de construction du compilateur avec l'exécution des tests

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 créé le nouveau projet JFlex (seul) de nom jflex_exo1_premierspas à partir de l'archétype Maven pour un projet JFlex (seul).
On obtient l'arborescence qui suit :
$ cd $HOME/CSC4251_4252 $ ls csc4251_4252-archetypes-maven jflex_exo1_premierspas $ cd jflex_exo1_premierspas $ tree --charset=ascii . |-- pom.xml |-- readme.md `-- src |-- main | |-- java | | `-- compil | | |-- Compiler.java | | `-- util | | |-- CompilerException.java | | `-- Debug.java | `-- resources | |-- Jflex8bits.include | |-- JflexCup.include | |-- Jflex.include | `-- nouveaujflex.jflex `-- test |-- java | `-- TestCompiler.java `-- resources `-- nouveaujflex.txt $ tree --charset=ascii . |-- pom.xml |-- readme.md |-- src | |-- main | | |-- java | | | `-- compil | | | |-- Compiler.java | | | `-- util | | | |-- CompilerException.java | | | `-- Debug.java | | `-- resources | | |-- Jflex8bits.include | | |-- JflexCup.include | | |-- jflex_exo1_premierpas.jflex | | `-- Jflex.include | `-- test | |-- java | | `-- TestCompiler.java | `-- resources | `-- jflex_exo1_premierpas.txt `-- target |-- classes ...

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 > ~/CSC4251_4252/jflex_exo1_premierspas 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

Utilisation simple de JFlex, unité et catégorie lexicale, Règle-balai, ECHO().

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 :

first0.jflex

et un exemple de données :

first.data

Construire l'analyseur lexical, exécuter sur l'exemple, et suivre les explications qui suivent.

$ java -jar jflex.jar first0.jflex
$ javac Yylex.java
$ java Yylex first.data

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 créé le nouveau projet JFlex jflex_exo1_premierspas.
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/jflex_exo1_premierspas/jflex_exo1_premierspas.jflex par le contenu du fichier qui suit :

first1.jflex
Regarder en particulier la définition des méthodes ECHO(), WARN() et WHERE() dans le fichier src/main/resources/Jflex.include.
Remplacer le contenu du fichier de test src/main/resources/jflex_exo1_premierspas/jflex_exo1_premierspas.txt par le contenu du fichier qui suit :

first.data
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é :
=== Étape 1 Analyse Lexicale === Reading standard input Analyse Lexicale Sample0 (type any text) :
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.

Attention aux potentiels « ... » dans le code inséré !

...
%%
%include Jflex.include
...
...
%%
[a-zA-Z] [a-zA-Z0-9]*  { ECHO("ID"); }
[^]                    { ECHO(); }
...

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.

Les classes [+-*/], [-+*/], et [+*-/] sont différentes. Pourquoi ?

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 :

first2.out

Attention aux potentiels « ... » dans le code inséré !

...
%%
[-+*/]                 { ECHO("OP");  }
[<>]"="?               { ECHO("CMP"); }
[(){},;\[\]]           { ECHO("SEP"); }
[-+*/]?"="             { ECHO("AFF"); }
"++"                   { ECHO("INC"); }
for|if|else|while      { ECHO("KW");  }
[a-zA-Z] [a-zA-Z0-9]*  { ECHO("ID");  }
[0-9]+ \.?             |
[0-9]* \.? [0-9]+      { ECHO("NUM"); }
[ \t]+                 { /* ignore espaces  */ }
"//".*                 { /* ignore comments */ }
\R                     { ECHO(); }
[^]                    { WARN("Invalid char : " + yytext()); }
...

Les mots-clés doivent être reconnus avant les identificateurs, sinon aucun mot-clé ne sera reconnu.
Noter la gestion des caractères spéciaux ou méta-caractères JFlex :

On peut utiliser le \, ou les classes de caractères [..]. Les expressions \<|\> et [<>] sont équivalentes.
À l'intérieur d'une classe de caractères, les seuls caractères réservés sont -, ^, \ et ]. De plus, le ^ n'est spécial que en première position et le - n'est plus spécial en première ou dernière position. Par exemple, la classe [-+=] contient bien 3 caractères alors que la classe [+-=] contient les 19 caractères ASCII entre le + (0x2b) et le = (0x3d).

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

Priorité des règles, Action nulle, Classe de caractères.

Les questions sont courtes et indépendantes. Elles reprennent des extraits de l'Oulipo Ouvroir de Littérature Potentielle.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex2. Ensuite, on importe le nouveau projet Maven dans son IDE, par exemple Eclipse.

Lipogramme sans e

Un lipogramme est un texte d'où une lettre est bannie. Cet exercice est à faire "ni six moins cinq, ni dix moins huit" (Lipogramme sans "e" pour "ni une, ni deux" !).

Écrire un analyseur lexical qui n'affiche que les lettres "e" ou "E" d'un texte.
Tester sur un extrait de "La Disparition" de Georges Perec :

lipo1.data

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%%
[eE]  {} /* { ECHO("E!" + WHERE()); } */
[^]   { ECHO(); }
...

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 :

lipo2.data

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%%
[rR]    { }
[^]     { ECHO(); }
...

Variante sans haine

Écrire un analyseur supprimant les "n".
Exemple :

lipo3.data

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%%
n|N    { }
[^]    { ECHO(); }
...

Abécédaire

Écrire un analyseur affichant la première lettre de chaque mot (Indication : utiliser la méthode String.CharAt(int i)).

Qu'est-ce qu'un mot ?

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.

On pourra, au choix, définir un mot à partir des caractères qu'il peut contenir ou bien à partir des caractères qui séparent les mots.
Exemple pour tester :

lipo4.data

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%eof{  /* code en action final */
System.out.println();
%eof}

MOT = [-[:letter:]] +
MOT2 = [^ \n\t,.!?\'():] + // autre solution

%%
{MOT}      { System.out.print(yytext().charAt(0)); }
{MOT2}     { ECHO("MOT2"); }
[^]        { }
...

Recherches dans un dictionnaire

Expressions régulières, Contexte et gestion des lignes.

Les questions sont indépendantes et de difficulté croissante. On considère un dictionnaire comme le fichier /usr/share/dict/words qui contient des « mots » ligne à ligne, et l'on désire extraire les mots vérifiant certaines propriétés. Ceci s'apparente directement à la commande UNIX grep. (N.B. le fichier /usr/share/dict/words est très dépendant de la distribution Unix, les résultats donnés ne sont que indicatifs)

Rappel sur la gestion des lignes :

[^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.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex3. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

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 »...

Attention aux potentiels « ... » dans le code inséré !

...
/* Au moins 1 q non suivi de u : 308 mots sur /usr/share/dict/words */
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
MOT = .* [qQ] ( [^uU\n] .* )?
%%
^ {MOT} \R { ECHO(); }
[^]        { }
...

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...

Attention aux potentiels « ... » dans le code inséré !

...
/* au moins 1 z et 1 q : 253 mots sur  /usr/share/dict/words */
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
MOT  =  .* [zZ] .* [qQ] .*
     |  .* [qQ] .* [zZ] .*
%%
^ {MOT} \R { ECHO(); }
[^]        { }
...

Top Scrabble

Lister les mots contenant exactement un « z » et un « q ».

Résultats sur /usr/share/dict/words : 219 mots.

Attention aux potentiels « ... » dans le code inséré !

...
/* exactement 1 z et 1 q : 219 mots sur /usr/share/dict/words */
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
OTH = [^zZqQ\n]
MOT  =  {OTH}* [zZ] {OTH}* [qQ] {OTH}*
     |  {OTH}* [qQ] {OTH}* [zZ] {OTH}*
%%
^ {MOT} \R { ECHO(); }
[^]        { }
...

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.

L'utilisation des expressions régulières n'est pas la solution la plus simple pour cet exercice. Il est plus rapide d'écrire directement du code.

Attention aux potentiels « ... » dans le code inséré !

...
/* Au moins 1 z, 1 q , 1x : 21 mots sur le dictionnaire /usr/share/dict/french
   désintoxiquassiez désintoxiquerez désintoxiqueriez désintoxiquez désintoxiquiez
   expliquassiez expliquerez expliqueriez expliquez expliquiez extorquassiez
   extorquerez extorqueriez extorquez extorquiez intoxiquassiez intoxiquerez
   intoxiqueriez intoxiquez intoxiquiez quartzeux
 */
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
MOT = .* [zZ] .* [qQ] .* [xX] .*
    | .* [zZ] .* [xX] .* [qQ] .*
    | .* [qQ] .* [zZ] .* [xX] .*
    | .* [qQ] .* [xX] .* [zZ] .*
    | .* [xX] .* [zZ] .* [qQ] .*
    | .* [xX] .* [qQ] .* [zZ] .* 
%%
^ {MOT} \R { ECHO(); }
[^]        { }
...

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...

Attention aux potentiels « ... » dans le code inséré !

...
/* DeadBeef */
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
STRICT = [a-fA-F]
APPROX = {STRICT}|[oOiIzZsSgG]
%%
^ {STRICT}{4} $ { ECHO("4-STRICT"); System.out.println(); }
^ {APPROX}{4} $ { ECHO("4-APPROX"); System.out.println(); }
^ {STRICT}+   $ { ECHO("*-STRICT"); System.out.println(); }
^ {APPROX}+   $ { ECHO("*-APPROX"); System.out.println(); }
[^]             { }
...

ABBA

[Lire les sections 5 et 7 du mémento JFlex]

Expressions régulières non triviales, Négation d'expressions régulières, Point de vue théorie des langages.

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.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex4. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

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 :

abbaProto.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 ».

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%{
  int nbOK=0, nbNOT=0, nbUNK=0;
  void OUT(String s) { System.out.print( s + ":" + yytext()); }
%}
%eof{
  System.out.println("OK=" + nbOK + ", NOT=" + nbNOT + ", UNK=" + nbUNK);
%eof}

OK  =  a .* | .* a
NOT =  ( [^a] (.* [^a])? )? 
// Astar ab -5   : OK = 46, NOT = 17
// Astar ab -10  : OK = 1534, NOT = 513

%%
^ {OK}  \R  { OUT("OK "); nbOK++;   }
^ {NOT} \R  { OUT("NOT"); nbNOT++;  }
^ [ab]* \R  { OUT("UNK"); nbUNK++;  } /* balai sur Sigma* */
[^]         { WARN("Invalid Char"); } /* autre que a,b ou NL */
...

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 ».

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%{
  int nbOK=0, nbNOT=0, nbUNK=0;
  void OUT(String s) { System.out.print( s + ":" + yytext()); }
%}
%eof{
  System.out.println("OK=" + nbOK + ", NOT=" + nbNOT + ", UNK=" + nbUNK);
%eof}

OK =  a? (ba)* b? 
NOT =  .* ( aa | bb ) .* 
// Astar ab -5  : OK = 11, NOT = 52
// Astar ab -10 : OK = 21, NOT = 2026

%%
^ {OK}  \R  { OUT("OK "); nbOK++;   }
^ {NOT} \R  { OUT("NOT"); nbNOT++;  }
^ [ab]* \R  { OUT("UNK"); nbUNK++;  } /* balai sur Sigma* */
[^]         { WARN("Invalid Char"); } /* autre que a,b ou NL */
...

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 ».

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
...
...
%include Jflex.include
%{
  int nbOK=0, nbNOT=0, nbUNK=0;
  void OUT(String s) { System.out.print( s + ":" + yytext()); }
%}
%eof{
  System.out.println("OK=" + nbOK + ", NOT=" + nbNOT + ", UNK=" + nbUNK);
%eof}

// la solution traditionnelle calculée par négation
// d'automate et recurrence de McNaughton & Yamada
// OK  =  b* (a+bb+)* (a*|a+b)

// variante lemme de Arden et reduction de Gauss au lieu de McNaughton & Yamada
// OK = (a+bb|b)*(a+b)?

// La solution habile de Paul VANCAUWENBERGHE CSC4536 2021-2022
OK  =  b*(a|bb+)*b*
NOT =  .* aba .* 
// Astar ab -5  : OK = 47,  NOT = 16
// Astar ab -10 : OK = 814, NOT = 1233

%%
^ {OK}  \R  { OUT("OK "); nbOK++;   }
^ {NOT} \R  { OUT("NOT"); nbNOT++;  }
^ [ab]* \R  { OUT("UNK"); nbUNK++;  } /* balai sur Sigma* */
[^]         { WARN("Invalid Char"); } /* autre que a,b ou NL */
...

Preuve mathématique dans les diapositives du cours.

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 :

%%
^ ({OK} |  {NOT}) \R  { }   /* Union */
^ [ab]* \R            { OUT("UNK"); }

%%
^ (!{OK} | !{NOT}) \R { }   /* Complémentaire de l'intersection */
^ [ab]* \R            { OUT("UNK"); }

Commentaire en C

Expressions régulières non triviales, Utilisation des « super-états ».

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex5. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

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 :

comment.data

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).

Attention aux potentiels « ... » dans le code inséré !

...
// Commentaire avec uniquement expression reguliere
package compil; // nom du paquetage à adapter
%%
%include Jflex.include

START = "/*"
END   = "*/"
// mauvaise solution : monoligne, glouton
COMMENT0 = {START} .* {END}
// mauvaise solution : multiligne, mais tres glouton !
COMMENT1 = {START} [^]* {END}
// solution OK (vincent PESENTI, promo ASR3 2011-2012)
COMMENT2 = {START} ( [^*] | "*"+ [^*/] )* "*"* {END}
// solution spécifique JFlex avec opérateur UpTo
COMMENT3= "/*" ~"*/"

%%
{COMMENT2}    { ECHO("COMMENT"); }
{COMMENT3}    { ECHO("COMMENT3"); } // ne paire pas !!
"//".*        { ECHO("COM_C++"); }
[^]           { ECHO(); }
...

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)

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
...
...

%xstate COMMENT

START = "/*"
END   = "*/"

%%
{START}        { yybegin(COMMENT);  System.out.print("/*.."); }

// syntaxe v1 
<COMMENT>{END} { yybegin(YYINITIAL); System.out.print("..*" + "/"); }
<COMMENT>[^]   { }

// syntaxe v2
// <COMMENT>{
//  {END}  { yybegin(YYINITIAL);  System.out.print("..*/"); }
//  [^]    { }
// }

[^]           { ECHO(); }
...

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.

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%{
int level = 0;
%}

%%
"/*"   { level++; System.out.print("/*" + level + " "); }
"*/"   { System.out.print(" " + level + "*/"); level--; }
[^]    { if (level == 0) ECHO(); }
...

WC

[Lire la section 7 du mémento JFlex]

Utilisation de variables, Code utilisateur, Traduction lexicale à la volée.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex6. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

É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".

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
...
...
%include Jflex.include
%{
  int nb_car = 0, nb_mot = 0, nb_ligne = 0;
%}
%eof{
  System.out.println("Lignes : " + nb_ligne
                     + ", Mots : " + nb_mot 
                     + ", Car. : " + nb_car
                     );
%eof}

CAR = [^ \t\n\r]

%%
{CAR}+  { nb_mot++;   nb_car += yylength(); }
\R      { nb_ligne++; nb_car += yylength(); }
[^]     { nb_car++; }
...

La Vengeance de l'Oulipo

[Lire la section 7 du mémento JFlex]

WC++, Utilisation de variables, Code utilisateur.

Tautogramme – texte dont les mots commencent par la même lettre.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex7. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

É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) :

v_oulipo.data

v_oulipo-VO.data

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

Attention aux potentiels « ... » dans le code inséré !

...
package compil; // nom du paquetage à adapter
...
...
%include Jflex.include
%{
  int nb_v = 0, nb_mots = 0, nb_lignes = 0, nb_punct = 0;
%}
%eof{
  System.out.println("\n nb_v = " + nb_v +
                    ", nb_mots = " + nb_mots +
                    ", nb_punct = " + nb_punct +
                    ", nb_lignes = " + nb_lignes);
%eof}

NL = \R
BLANC = [ \t]
MOT = [-[:letter:]] +
PUNCT = [,.!?\'():-;]

// 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
%%
[vV]{MOT}? { ECHO("Vmot");  nb_mots++; nb_v ++; }
{MOT}      { ECHO("Mot");   nb_mots++; }
{PUNCT}    { nb_punct++; } /* NB : pas les - internes ! */
{BLANC}    { }
\R         { ECHO(); nb_lignes++; }
[^]        { WARN("Unknown"); }
...

Filtres

Gestion de lignes, Code Utilisateur, Ordre des règles.

Les questions sont indépendantes.

On commence par créer un nouveau projet Maven JFlex (seul) en exécutant la commande compil-nouveau-jflex-seul exojflex8. Ensuite, on importe le nouveau projet Maven dans son IDE (Eclipse).

Dans les différentes questions de cet exercice, on peut analyser le fichier exo8_filtres_lignes_vides.txt.

Lignes vides

Écrire un filtre qui supprime :

les lignes vides,
les lignes blanches (uniquement espaces et tabulations),
les blancs inutiles en fin de ligne.

À venir

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.

À venir

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.

À venir

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.

À venir

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.

À venir

CSC4251_4252, Télécom SudParis, Pascal Hennequin, J. Paul Gibson, Denis Conan, Last modified: Décembre 2024

CSC4251_4252 — Compilation : du langage de haut niveau à l'assembleur

Exercices d'utilisation de JFlex (seul)

Prologue

Installation logicielle pour le module

Mise en place de l'environnement du cours

Utilisation de l'IDE Eclipse

Premiers pas – Analyse lexicale d'un langage de programmation

Exécution manuelle (optionnelle)

Environnement du cours

Analyseur lexical d'un langage de programmation

le Graal

Oulipo

Lipogramme sans e

Asphyxie ou Lipossible

Variante sans haine

Abécédaire

Recherches dans un dictionnaire

Du cul pas cucul

Scrabble

Top Scrabble

Super Top Scrabble

Dead Beef – hexspeak – leet speak

ABBA

Ancien Alcoolique Anonyme

Bébé bègue

Béaba ou b.a.-ba (difficile !)

Bonus

Commentaire en C

Expression régulière

Super-état (bonus)

Commentaires sans automate (optionnel)

WC

La Vengeance de l'Oulipo

Filtres

Lignes vides

Lignes vides et cat -s

Numéros de ligne, cat -n et cat -b

Détabulation, expand ou col -x

Justification, fold -s

Lignes vides et `cat -s`

Numéros de ligne, `cat -n` et `cat -b`

Détabulation, `expand` ou `col -x`

Justification, `fold -s`