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

Portail informatique

Exercices d'utilisation de JFlex (seul)

Prologue

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 $ 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_exo1_premierpas | | | `-- jflex_exo1_premierpas.jflex | | `-- Jflex.include | `-- test | |-- java | | `-- TestCompiler.java | `-- resources | `-- jflex_exo1_premierpas | `-- 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


[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.
$ 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 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 :
  • 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 :
  • 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.

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 :
À venir

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.

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 :
À venir

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 :
À venir

Variante sans haine


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

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 :
À venir

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.

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

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

Top Scrabble


Lister les mots contenant exactement un "z" et un "q"
Résultats sur /usr/share/dict/words : 219 mots.
À venir

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

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

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

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

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

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

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"); }
et
%% ^ (!{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".
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).
À venir

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)
À venir

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

WC

[Lire la section 7 du mémento JFlex]
Utilisation de variables, Code utilisateur, Traduction lexicale à la volée.
É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".
À venir

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

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
À venir

Filtres

Gestion de lignes, Code Utilisateur, Ordre des règles.
Les questions sont indépendantes.

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 «&nbps;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: Novembre 2024