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

Portail informatique
Expressions régulières, Contexte et gestion des lignes Écrire un analyseur reconnaissant les mots contenant les 6 voyelles dans l'ordre. On supposera qu'il y a un seul mot à reconnaître par ligne et on testera sur le dictionnaire /usr/share/dict/share Expressions régulières (répétitions), analyse ligne à ligne Des langages de programmation comme Ada ou Java autorisent une écriture "aérée" des constantes entières avec l'utilisation possible du caractère underscore (_) entre des chiffres du nombre. Par exemple : 12345 ou 12_345 ou 1_23_45
Un usage courant dans le monde anglo-saxon est d'aérer l'écriture des grands nombres avec des séparateurs pour les milliers et les puissances de milliers.

Écrire une expression régulière qui reconnaît exactement les nombres entiers avec des séparateurs underscore autorisés uniquement pour les milliers et les puissances de milliers. On testera avec un analyseur ligne à ligne qui accepte les nombres aérés valides sur une ligne complète.
Un fichier d'exemples :
Analyse ASCII 8bits, Ordre des règles Jflex (comme Java) ne lit pas l'ASCII 8bits de manière naturelle mais utilise par défaut un Charset associé à la lecture de fichiers textes. Pour avoir une analyse lexicale 8bits, la moins mauvaise solution est d'utiliser le charset "iso-latin" == "ISO-8859-1".
Pour cet exercice, remplacer l'utilisation du fichier "Jflex.include" par la version adaptée
Écrire un filtre qui rend visible les caractères non imprimables d'un fichier texte en ASCII 8 bits. Ce filtre correspond à la commande Unix cat -A == cat -vTE. Utiliser le manuel de cat et le résultat de la commande cat -A pour préciser le fonctionnement du filtre.

On donne le fichier de test : Un équivalent de "cat -A" (et vive l'octal !) :
Unité et catégorie lexicale, Expressions régulières On veut commencer l'écriture d'un compilateur Java en réalisant l'analyse de la catégorie lexicale "Constante Entière" (Integer Literal). On utilisera la définition valide à partir de Java7, c'est-à-dire incluant la notation binaire et l'utilisation du caractère underscore "_" pour aérer l'écriture.

De façon informelle, les "Constantes Entières" Java sont définies par :
  1. Les "Constantes Entières" représentent des valeurs fixes pour les types primitifs : byte, short, int, et long.
  2. Les "Constantes Entières" peuvent s'écrire en utilisant les systèmes de numération : décimal, hexadécimal, octal, et binaire.
  3. Une "Constante Décimale" utilise les chiffres "0" à "9".
  4. Une "Constante Hexadécimal" utilise les chiffres "0" à "9" et les lettres "a" à "f" et "A" à "F". La notation commence alors par le préfixe "0x" ou "0X".
  5. Une "Constante Octal" utilise les chiffres "0" à "7". La notation commence alors par le préfixe "0".
  6. Une "Constante Binaire" utilise les chiffres "0" et "1". La notation commence alors par le préfixe "0b" ou "0B".
  7. Une "Constante Entière" est analysée par défaut comme un int (valeur sur 4 octets)
  8. Une "Constante Entière" peut aussi être analysée comme un long (valeur sur 8 octets). Pour cela, on ajoute le suffixe "l" ou "L" à la représentation de la constante.
  9. Pour la lisibilité, on peut insérer, éventuellement de façon consécutive, des caractères underscore "_" dans la représentation d'une "Constante Entière".
  10. You can place underscores only between digits; you cannot place underscores in the following places:
    • At the beginning or end of a number
    • Adjacent to a decimal point in a floating point literal
    • Prior to an F or L suffix
    • In positions where a string of digits is expected

On précise que :
  • Le "0" qui sert de préfixe à la notation octale est aussi considéré comme le premier chiffre de cette notation. Il peut donc être directement suivi par des caractères "_".
  • La seule constante décimale commençant par "0" est le nombre "0". (sinon conflit avec l'octal)
  • "+" et "-" n'apparaissent pas dans la notation des "Constante Entières" mais sont gérés par Java comme des opérateurs au niveau syntaxique. Ainsi, une "Constante Décimal" n'est jamais négative.
  • Typo. : les "0" dans l'énoncé sont toujours des chiffres zéro et pas des lettres O.

Écrire une expression régulière pour reconnaître les "Constantes Entières" de Java et tester avec un analyseur qui :
  • Reconnaît séparément chacune des sous-catégories : Décimal, Octal, Hexadécimal et Binaire.
  • Reconnaît les commentaires de style C++ (// ... fin_ligne) et ainsi ignore les constantes entières à l'intérieur des commentaires.
  • Reconnaît les identificateurs et ainsi ignore les constantes entières à l'intérieur d'un identificateur.
  • Reporte l'ensemble du source en sortie avec un marquage claire des constantes entières reconnues.
On fournit un exemple de code Java valide et le résultat attendu en sortie de l'analyseur
Ordre des règles, Négation par règle balai, Analyse ligne à ligne, Expressions régulières, Automate de grande taille. On veut réaliser un "durcisseur de mots de passe", c'est-à-dire un outil qui lit un mot de passe et refuse si le mot semble trop facile à casser avec une "attaque par force brute". Cf. wikipedia(fr)/Attaque_par_force_brute

On considère comme "robuste" un mot de passe qui :
  • contient au moins six caractères,
  • contient au moins une minuscule, une majuscule, un chiffre et une ponctuation (Catégorie Unicode \p{Punctuation})
  • ne contient pas comme sous-mot : "mot", "pass", "666", "qwer", "azer"
  • contient au moins un chiffre hors d'une séquence de chiffres en fin de mot
  • contient au moins un chiffre hors d'une séquence de chiffres en début de mot

De plus, des contraintes applicatives imposent de refuser un mot de passe qui :
  • contient plus de 15 caractères,
  • contient des caractères de fin de ligne,
  • contient des caractères blancs,
  • contient des caractères 8 bits (non 7 bits),
  • contient des caractères de contrôle. ([\x00-\x1F\x7F])

Écrire un analyseur lexical avec Flex qui accepte les mots de passe "robustes". Pour chaque ligne en entrée l'analyseur indiquera si la ligne est un mot de passe "robuste" ou bien une raison de la non robustesse. La gestion de la taille maximum par une expression régulière du type . {16} .* peut rapidement faire exploser la taille de l'automate Jflex et le temps de compilation. On pourra tester cette explosion combinatoire et remplacer la gestion de la taille au niveau du code utilisateur Java plutôt que par une expression régulière.
Un fichier d'exemple et le résultat attendu en sortie de l'analyseur
Expression régulière, Code utilisateur Consulter les pages Wikipedia Numération Romaine ou Roman numerals pour une description détaillée des nombres romains.

On considère l'usage "classique" des nombres romains entre 1 et 4999 construits à partir des chiffres :
IVXLCDM
1510501005001000

, avec les premiers nombres :
IIIIIIIVVVIVIIVIIIIXXXI
1234567891011

On fournit le code Java qui génère les nombres romains de 1 à N.
Écrire un analyseur lexical qui reconnaît ligne à ligne les nombres romains entre 1 et 4999. Tester avec les nombres valides (romGen) et un fichier de contre-exemples bien choisis.

On appellera calculus d'un nombre, le nombre de chiffres utilisés dans son écriture romaine. calculus(CXXIV)=5.
Modifier l'analyseur pour :
  • écrire la valeur maximum du calculus des nombres du fichier
  • écrire les Maxima Locaux de calculus, c'est à dire la première entrée qui a un calculus de 1, puis de 2,..
  • écrire la fréquence de chaque valeur de calculus, c'est à dire combien d'entrées ont pour calculus 1, 2,...

Un exemple de résultat : # java romGen 5000 | java Yylex Maximum Locaux : I II III VIII XVIII XXVIII XXXVIII LXXXVIII CLXXXVIII CCLXXXVIII CCCLXXXVIII DCCCLXXXVIII MDCCCLXXXVIII MMDCCCLXXXVIII MMMDCCCLXXXVIII MMMMDCCCLXXXVIII Maximum global : 16 Frequences : 7 31 93 216 395 597 753 814 753 597 395 216 93 31 7 Et le graphe de la fonction calculus :

Déclinaison latine de calculcus: "calculus, calcule, calculum, calculi, calculo, calculo"
et au pluriel "calculi, calculi, calculos, calculorum, calculis, calculis".
Analyseur lexical sans jflex, Préparation du couplage avec un analyseur syntaxique On se donne une classe abstraite "SimpleLex"" et une implémentation "NatLex0" qui réalise un analyseur lexical simple : ,

Analyser les sources fournies, identifier les catégories lexicales reconnues par l'analyseur et tester le fonctionnement (javac *.java; java NatLex0; java NatLex0 testfile ). L'analyseur correspond à une spécification Jflex : %% [:jletter:]+ { return MOT; } [^] {} il reconnaît les catégories MOT et EOF, et ignore les autres caractères en entrée.

Compléter l'analyseur pour reconnaître les catégories :
  • POINT : "."
  • ARTICLE : "le" , "un"
  • NOM_C : "lapin", "chasseur", "gnou"
  • NOM_P : "Bart", "Jeannot", "Obi-Wan"
  • VERBE : "tue", "mange"
Options :
  • La catégorie MOT peut être conservée pour les mots qui n'appartiennent pas aux autres catégories.
  • La catégorie NOM_P peut aussi être définie comme les MOT commençant par une majuscule

L'analyseur a écrire correspond donc à une spécification Jflex de la forme : %% "." { return DOT; } un|le { return ARTICLE; } //... [:uppercase:][:jletter:]* {return NOM_P; } [:jletter:]+ { return MOT; } [^] {} La classe "Natlex" pour l'analyseur lexical étendu :
Première utilisation de l'outil Cup, Problématique du couplage entre analyse syntaxique et lexical. On utilise l'analyseur lexical écrit à la main dans l'exercice précédent : ,
On donne aussi une spécification Cup pour produire un analyseur syntaxique qui utilise l'analyseur "NatLex0" au niveau lexical.

Analyser le code de la spécification Cup; Générer l'analyseur syntaxique; et Tester l'analyseur : java -jar LIBCOMP/lib/java-cup.jar Nat0.cup ## ou cup Nat0.cup javac -cp .:LIBCOMP/lib/java-cup-runtime.jar *.java java -cp .:LIBCOMP/lib/java-cup-runtime.jar Nat0 #interactif Pourquoi cela ne marche pas ? Analyser la classe "sym.java" générée par l'outil Cup. L'analyseur syntaxique devrait accepter comme syntaxiquement correcte n'importe quelle séquence produite par l'analyseur lexicale. Il n'accepte visiblement que le fichier vide en entrée (c'est déjà quelque chose !).
Le problème est que l'analyseur syntaxique et l'analyseur lexical ont deux définitions différentes pour les catégories lexicales

Modifier l'analyseur lexical "NatLex0" et la génération avec l'outil Cup pour obtenir une exécution correcte.
Utiliser java -jar LIBCOMP/lib/java-cup.jar -interface Nat0.cup ## ou cup -interface Nat0.cup pour produire l'interface "sym.java" contenant la définition des catégories lexicales par Cup.
Intégrer cette définition dans la définition de la classe "NatLex0.java" avec implements sym

Tester que l'analyseur syntaxique accepte maintenant toutes séquence de mots suivies d'une fin de fichier.

En reprenant le corrigé de l'exercice précédent pour le niveau lexical, et en complétant l'analyseur syntaxique Nat0.cup, produire un analyseur syntaxique pour la grammaire "langage Naturel Simple" des slides du cours.
Compléter la grammaire pour accepter une séquence de phrases.
Compléter enfin pour avoir une reprise sur erreur en cas de phrases incorrectes (utilisation du token error pour laresynchronisation sur POINT)

Étendre l'analyseur pour accepter les règles de "Pierre, papier, ciseaux, lézard, Spock !". C'est-à-dire : " les ciseaux coupent le papier, le papier bat la pierre, la pierre écrase le lézard, le lézard empoisonne Spock, Spock écrabouille les ciseaux, les ciseaux décapitent le lézard, le lézard mange le papier, le papier repousse Spock, Spock détruit la pierre, La pierre bat les ciseaux."
Premiers pas Cup, Couplage Jflex/Cup, Environnement du cours Reprendre l'exercice précédent en utilisant l'environnement du cours et en générant l'analyseur lexical à partir d'une spécification Jflex :
  • Créer un projet CUP+JFlex ($ Compil-new-cup mon_projet) et aller dans le projet
  • Analyser les fichiers fournis et tester le fonctionnement sur spec/sample (....)
  • Intégrer dans le dossier spec les squelettes de spécification et
  • Tester l'analyseur
  • Compléter les deux spécifications pour obtenir l'analyseur de l'exercice précédent.
Le couple de spécification : et