CSC4536– Compilation : De l'algorithme à la porte logique

Portail informatique
  • Récupérer l'archive LibCompil.tar.gz et installer l'arborescence à votre convenance.
  • LIBCOMP désignera l'emplacement de l'arborescence; i.e. ~/Compil/LibCompil
  • Inclure le chemin LIBCOMP/bin dans la variable PATH de votre environnement;
    i.e. ajouter export PATH=~/Compil/LibCompil/bin:$PATH dans ~/.bashrc
  • Vérifier l'installation avec which jflex; i.e. ~/Compil/LibCompil/bin/jflex

L'arborescence LIBCOMP fournit (cf. LIBCOMP/README.md) :

  • LIBCOMP/lib : les outils JFlex, CUP et MARS sous forme d'archives Java exécutables
  • LIBCOMP/bin : quelques commandes pratiques
  • LIBCOMP/editor : des modes JFlex pour emacs ou vi (support non fourni)
  • LIBCOMP/proto* : des squeletes 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 les outils make ou ant
Utilisation simple de JFlex, Unité et catégorie lexicale, Règle-balai, ECHO()
Soit une spécification JFlex : et un exemple de données : Construire l'analyseur lexical, exécuter sur l'exemple, et expliquer le résultat java -jar LIBCOMP/lib/jflex.jar first0.jflex ## ou jflex first0.jflex javac -g Yylex.java java Yylex first.data Tout est reporté en sortie, mais on identifie les fragments reconnus 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 on écrira toujours une règle-balai explicite.

La commande Compil-new-jflex mon_projet crée un directory 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 pour le cours) et aller dans le projet.
  • Regarder les fichiers fournis et tester la commande make
  • Tester la spécification i.e : make first1 java Yylex < first.data # ou java Yylex first.data # ou make run < first.data java Yylex # et saisie au clavier # ou make run # et saisie au clavier make clean Pour la saisie interactive, le caractère de fin de fichier EOF s'obtient avec Ctrl-d

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

Exemple de résultat attendu : 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).
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.
É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 :

En asphyxiant un texte, c'est-à-dire en le privant de "R", on obtient un autre texte qui est dit anaérobie du premier.
Écrire un analyseur supprimant les "r".
Exemple :

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

Écrire un analyseur affichant la première lettre de chaque mot (Hint: 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 définir un mot à partir des caractères qu'il peut contenir ou bien à partir des caractères qui séparent les mots.

Exemple :
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. Rappel sur la gestion des lignes :
  • [^xyz] reconnaît \n
  • . ne reconnaît pas \n
  • ^ et $ reconnaissent \n sans le "manger"
  • ^ regexp $ est interdit, si l'expression regexp peut être vide

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,

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

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

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.

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,G (approximations de 0 1 2 5 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,G

Exemples : DEADBEEF, CAFEBABE, DICECA5E, B16B00B5
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 2 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 tout les mots de taille fixée. On donne le programme Astar.java qui génère ligne à ligne tout 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

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

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

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 Preuve mathématique dans les slides du cours
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 debugging, l'analyseur indiquera clairement les commentaires reconnus même si il n'en affiche pas obligatoirement le contenu.
Un exemple pour tester :
  • 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)

Reconnaître les commentaires en utilisant les super-états de JFlex (directive %state ou %xstate)

  • 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.
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 "blancs". 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
Gestion de lignes, Code Utilisateur, Ordre des règles Les questions sont indépendantes
Écrire un filtre qui supprime :
  • les lignes vides
  • les lignes blanches (uniquement espaces et tabulations)
  • les blancs inutiles en fin de ligne

Écrire un filtre qui remplace des lignes blanches ou vides consécutives par une seule ligne vide.
Comparer avec la commande unix cat -s.

Écrire l'équivalent des filtres cat -n et cat -b qui numérotent les lignes d'un fichier

É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 tout les 8 caractères, et qu'une tabulation aligne sur le prochain taquet du texte.

É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

CSC 4536, TELECOM SudParis, P. Hennequin,Last modified: Oct 2019