Compilation : De l'algorithme à la porte logique

Exercices d'utilisation de JFlex seul

Prologue : Mise en place de l'environnement du cours

Récupérer l'archive LibCompil.tar.gz et installer l'arborescence à votre convenance.
Modifier votre environnement shell pour :
- définir la variable d'environnement LIBCOMPIL avec le chemin de l'arborescence créée,
- ajouter le chemin $LIBCOMPIL/bin dans la variable PATH.
- Par exemple :
  - dans ~/.bashrc : export LIBCOMPIL=~/Compil/LibCompil; export PATH=$LIBCOMPIL/bin:$PATH
  - dans ~/.cshrc : setenv LIBCOMPIL ~/Compil/LibCompil; set path = ($LIBCOMPIL/bin path)
Vérifier l'installation avec which jflex, i.e. ~/Compil/LibCompil/bin/jflex.
L'arborescence fournit (cf. $LIBCOMPIL/README.md) :
- $LIBCOMPIL/lib : les outils JFlex, CUP et MARS sous forme d'archives Java exécutables.
- $LIBCOMPIL/bin : quelques commandes pratiques (jflex, cup, mars, Compil-*).
- $LIBCOMPIL/editor : des modes JFlex pour emacs ou vi (support non fourni).
- $LIBCOMPIL/proto* des squelettes de projet JFlex et CUP contenant :
  - des options de configuration pour le cours et des classes Java utiles,
  - des exemples de spécifications,
  - de la génération de code avec au choix les outils GNU Make ou Apache Ant.

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]
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 expliquer le résultat.

  java -jar $LIBCOMPIL/lib/jflex.jar first0.jflex    ## ou  jflex first0.jflex
  javac Yylex.java
  java Yylex first.data

first0.out

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. 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]
La commande Compil-new-jflex mon_projet crée un répertoire mon_projet avec l'environnement adéquat pour utiliser rapidement JFlex seul (sans CUP). On peut, à la convenance, utiliser le même projet pour plusieurs analyseurs lexicaux ou créer un nouveau projet pour chaque analyseur.

Refaire la question précédente avec l'environnement du cours :

Créer un projet JFlex pour l'exercice (ou pour le TP, ou...) et aller dans le projet.
Regarder les fichiers fournis et tester la commande make (ou la commande ant) avec la spécification fournie sample0.jflex.
Regarder en particulier la définition des méthodes ECHO(), WARN() et WHERE() dans le fichier Jflex.include.
Tester la spécification

first1.jflex

i.e :
make first1 java Yylex # saisie interactive au clavier java Yylex first.data # ou make run < first.data make clean

Pour la 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,....).

Exemple de résultat attendu :

first2.out

first2.jflex

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

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

lipo1.jflex

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

lipo2.jflex

Variante sans haine

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

lipo3.data

lipo3.jflex

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

lipo4.jflex

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

dico1.jflex

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

dico2.jflex

Top Scrabble

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

dico3.jflex

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.

dico4.jflex

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

dico5.jflex

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 :

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 : java Astar ab -10 | java Yylex # => OK = 1534, NOT = 513

abba1.jflex

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 : java Astar ab -10 | java Yylex # => OK = 21, NOT = 2026

abba2.jflex

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 : java Astar ab -10 | java Yylex # => OK = 814, NOT = 1233

abba3.jflex

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

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 "/*" ~"*/" (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).

comment1.jflex

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)

comment2.jflex

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.

comment3.jflex

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

wc.jflex

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

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

v_oulipo.jflex

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.

filtre1.jflex

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.

filtre2.jflex

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.

filtre3.jflex

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.

filtre4.jflex

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.

filtre5.jflex

CSC4251-52 (CSC 4536), TELECOM SudParis, P. Hennequin,Last modified: Novembre 2023