Compilation : De l'algorithme à la porte logique

Portail informatique

Exercices en vrac JFlex et CUP

Comment perdre une fusée ? (JFlex/CUP impossible !)

Un exemple de mauvaise séparation entre le niveau lexical et le niveau syntaxique.
Que signifient les 2 lignes suivantes en Fortran :
DO12i=1.25 DO12i=1,25
  1. Lexèmes [DO12i] [=] [1.25]. Affectation du réel 1.25 à la variable DO12i.
  2. Lexèmes[DO] [12] [i] [=] [1] [,] [25]. Boucle DO qui termine à l'étiquette 12, pour une variable i allant de 1 à 25.
Sur cet exemple, la mise en lexème est très difficile, puisqu'elle dépend de l'analyse syntaxique. C'est parce que la virgule ne sert que pour les boucles que l'on sait différencier le mot clé DO d'une boucle, de l'identificateur DO12i d'une affectation.
D’après la légende, on aurait perdu une fusée du projet Mercury à cause de cette petite erreur de typographie.

Ce problème que l'on appelle la reconnaissance contextuelle a largement disparu des langages de programmation moderne, sauf parfois pour des langages de script peu soucieux des concepts de la compilation !

L’excès de sucre syntaxique nuit gravement à la santé des compilateurs ! (JFlex/CUP impossible !)

Un problème de séparation entre le niveau lexical et syntaxique, "reconnaissance lexicale contextuelle"
Java 1.5 introduit les classes génériques, c'est à dire la possibilité d'ajouter à un nom de classe (ou type) des paramètres. Les caractères < et > sont utilisés comme parenthèses éventuellement récursives pour cela. On peut ainsi écrire :
void g(List<List<UnaryOperator<IntStream>>> l) { }

D'autre part, la spécification de Java définit les tokens d'opérateurs :
= > < ! ~ ? : -> == >= <= != && || ++ -- + - * / & | ^ % << >> >>> += -= *= /= &= |= ^= %= <<= >>= >>>=

N.B.: Les spécifications du langage Java sont disponibles ici (section 3.12 : opérateurs, section 8.1.2 : classes génériques).

Conflit lexical/Syntaxique


Expliquez le conflit produit par l'introduction des classes génériques dans Java 1.5. Pourquoi cela viole le principe de séparation entre le niveau lexical et le niveau syntaxique ?
">>" doit être un seul token en temps qu'opérateur de décalage binaire int i = 1024 >> 2; mais être deux tokens en temps que fermeture de parenthèses pour les classes génériques. Même problème pour ">>>", ">>=", ">>>=". Si l'on veut faire une analyse lexicale rigoureuse, le choix de la tokenisation dépend du contexte syntaxique dans lequel on se trouve. Cela viole le principe de séparation entre le niveau lexical et syntaxique puisque ici seule l'analyse syntaxique peut décider du découpage correct en tokens à chaque moment.

Solution dans javac OpenJdk


Expliquer la résolution faite dans javac à partir des extraits des sources  : Generic-javac-src.txt.
Le niveau lexical est conforme pour les tokens d'opérateurs, mais l'analyse syntaxique s'autorise à "guillotiner" les tokens "GT*" quand elle a besoin de manger un token "GT" au cours de l'analyse de type générique !!! Un token "GTGTGT" peut ainsi fournir successivement 3 tokens "GT" pour fermer 3 niveaux de parenthèses de classe générique.

Cette solution est utilisée ici avec un analyseur écrit à la main par descente récursive. Elle est sans doute applicable avec des outils d'analyse LL, mais la solution est inapplicable avec des outils d'analyse syntaxique LR.

Solution dans le compilateur JDT d'eclipse


Expliquer la solution par réécriture de la grammaire dans le compilateur incrémental d'eclipse : Generic-JDT-src.txt.
Oups!! La grammaire est incompréhensible.

Ce qu'il faut comprendre, c'est que l'on crée 3 niveaux de symbole (xxx1, xxx2, xxx3) pour reconnaitre séparément le contenu des paramètres génériques. Chaque niveaux correspond respectivement aux contenus dont la fermeture se fera par un "GT" simple, un "GT" double, ou un "GT" triple. En gros, la règle récursive de base "LT xxxx GT" devient 3 règles : "LT xxx1 GT" ou " LT ... LT xxx2 GTGT " ou "LT ... LT ... LT xxx3 GTGTGT". On obtient bien une récursivité complète de parenthésage mais avec une analyse qui agrège de 1 à 3 niveaux de parenthèses selon les besoins !!!

Contrairement à la question précédente, cette solution fonctionne avec des outils d'analyse syntaxique LR.

Une Solution simple, mais incorrecte


Une solution dans une grammaire java fournie avec l'outil (LL) AntLR:
// "Niveau lexical" // LSHIFT : '<<'; // RSHIFT : '>>'; // URSHIFT : '>>>'; // "Niveau syntaxique" shiftExpression : additiveExpression | shiftExpression '<' '<' additiveExpression | shiftExpression '>' '>' additiveExpression | shiftExpression '>' '>' '>' additiveExpression ;
La solution est simple mais incorrecte. Pourquoi ?
On reconnaît sans problèmes les types génériques et les opérateurs de décalage binaire conformément à la spécification de Java. Mais on accepte aussi des écritures non conformes des opérateurs binaires. Par exemple, l'énoncé correct "int i = 1024 >>> 2 ;" est aussi accepté sous la forme invalide :
int i = 1024 > /* pourquoi supérieur ? */ > /* non c'est shift !? */ > /* non c'est un shift unsigned !! */ 2 ;

Java Cold Case


Bien que présent depuis Java 5 (2004), le problème d'analyse lexical contextuelle des types génériques n'est signalé dans la spécification officielle du langage que depuis Java 17 (2021)(section 3.5) : Generic-JAVA-Lex-Spec.txt.

Postscriptum de l'auteur


Pour écrire l'énoncé de cet exercice, il a fallu remplacer à la main de l'ordre de 60 < ou > par des &lt; ou &gt;. Merci Html !

AEIOUY (JFlex seul)

Expressions régulières, contexte et gestion des lignes.
Écrire un analyseur reconnaissant les mots contenant les 6 voyelles dans l'ordre. On suppose qu'il y a un seul mot à reconnaître par ligne, et on peut tester sur le dictionnaire /usr/share/dict/words.
On reconnaitra en même temps, les mots qui contiennent exactement 6 voyelles dans le bon ordre, et les mots qui contiennent plus de voyelles dont 6 sont dans le bon ordre.

Nombres "aérés" (JFlex seul)

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 "tiret bas" (_, 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 "tiret bas" autorisés uniquement pour les milliers et les puissances de milliers. On testera avec un analyseur JFlex ligne à ligne qui accepte les nombres aérés valides sur une ligne complète.
Un fichier d'exemples :

Caractères non imprimables, filtre cat -A (JFlex seul)

Analyse ASCII 8-bits, Ordre des règles.
JFlex (comme Java) ne lit pas l'ASCII 8-bits de manière naturelle mais utilise par défaut un Charset associé à la lecture de fichiers textes. Pour avoir une analyse lexicale 8-bits, 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 Jflex8bits.include.
É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 : filtreInvisible.data
Un équivalent de cat -A (et vive l'octal !) :

Constantes entières Java (JFlex seul)

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 Java 7, c'est-à-dire incluant la notation binaire et l'utilisation du caractère tiret bas (_) 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 tiret bas dans la représentation d'une "Constante Entière".
  10. En VO dans la spécification : 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

Mot de Passe (JFlex seul)

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. Wikipédia(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 JFlex 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, puis 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

Nombres Romains (JFlex seul)

Expression régulière, Code utilisateur.
Consulter les pages Wikipédia 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 :
I V X L C D M
1 5 10 50 100 500 1000

On a donc les premiers nombres :
I II III IV V VI VII VIII IX X XI
1 2 3 4 5 6 7 8 9 10 11

On fournit le code Java romGen.java qui génère les nombres romains de 1 à N.

Nombre romain valide


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

Fonction Calculus


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 calculus : calculus, calcule, calculum, calculi, calculo, calculo
et au pluriel calculi, calculi, calculos, calculorum, calculis, calculis.

Commentaire HTML (JFlex seul)

Traduction JFlex d'une vraie spécification.
On considère la syntaxe des commentaires dans un document HTML telle qu'elle est définie dans la spécification HTML 5.0, section 8.1.6 Comments.
La syntaxe des commentaires est différente entre SGML, HTML 4, HTML 5,... et aussi la pratique des navigateurs. L'exercice concerne uniquement et strictement la spécification HTML 5.0 ou HTML 5.1 (2014-2017).

Sous une forme plus claire, un commentaire HTML 5.0 :

  1. commence par la séquence <!--,
  2. se poursuit avec un text avec les contraintes :
    • text peut être vide,
    • text ne commence pas par >,
    • text ne commence pas par ->,
    • text ne contient pas --,
    • text ne termine pas par -.
  3. termine par la séquence -->,
  4. On ajoutera que text peut contenir n'importe quelle séquence de caractères ASCII, y compris les fin de ligne (\n, \r, \r\n).

    Exemples de commentaires valides ou non valides :

    1 <!-- VALIDES : --> 2 <!----> 3 <!-- COM-MENT- --> 4 <!---CO-ME-NT- --> 5 <!-- -><!-COM->--> 6 <!-- >COM- -MENT- -->
    11 <!-- --NON-- --VALIDES :-- --> 12 <! COMMENT > 13 <!-- -COMMENT ---> 14 <!--->COMMENT --> 15 <!--> COMMENT --> 16 <!-- COMMENT -- > 17 <!-- -->AMBIGUE -->

    Analyse lexicale


    Écrire une expression régulière qui reconnaît strictement les commentaires conformes à la spécification HTML 5.
    Écrire une spécification JFlex pour valider cette expression régulière. Pour chaque commentaire valide, on imprimera le commentaire clairement délimité.
    La spécification JFlex :

Entête de Mail RFC822 (JFlex seul)

Utilisation des Super-états, Code utilisateur (wc).
L'objectif est d'analyser la structure d'un mail Internet afin de produire un rapport sommaire sur les entêtes utilisées et les tailles des constituants du message.

La syntaxe d'un courriel est décrite dans le RFC 822 (Syntaxe BNF complète en annexe D, version simplifiée en annexe B).
Elle peut être synthétisée comme suit :

  • Un message complet est la concaténation d'un nombre quelconque de champs-entête, d'une ligne vide (\n\n), et d'un corps de message.
    Contrairement au RFC, on pourra supposer qu'il y a toujours au moins 1 champs-entêtes et que le corps est non vide.
  • Un champs-entête est la concaténation d'un nom-champs, du caractère :, est d'un corps-champs.
  • Un champs-entête commence sur un début de ligne et termine sur une fin de ligne, mais peut occuper plusieurs lignes. Pour éviter les ambiguïtés, les lignes de continuation dans un corps-champs doivent obligatoirement commencer par un caractère espace ou tabulation.
  • Le corps d'un message et les corps-champs sont constituées de caractères ASCII 7-bits quelconques.
  • Les nom-champs contiennent au moins un caractère et sont constituées des caractères imprimables (ASCII de 33 à 126) à l'exception du caractère espace et du caractère :.
Exemples de mails : un exemple court ou un exemple plus long

Analyse lexicale sans super-état


Écrire un analyseur lexical sans utiliser les super-états qui lit un mail, vérifie la syntaxe et identifie les unités lexicales champs-entête et corps de message.

Pour chaque unité lexicale, on imprimera le contenu multi-ligne de l'unité de manière clairement délimitée
N.B. Le choix est libre d'inclure ou pas dans les unités lexicales, les \n qui séparent ces unités.

Analyse lexicale avec super-état


Modifier l'analyseur avec 2 super-états (HEAD, CORPS) pour réaliser la même analyse lexicale.
Pour chaque champs-entête, on imprimera son nom et la taille de son contenu. Pour le corps, on imprimera la taille de son contenu.

Rapport synthétique


Modifier l'analyseur pour imprimer pour chaque champs d'entête et pour le corps de message le nombre de caractères, le nombre de mots et le nombre de lignes correspondant. La vérification de la syntaxe pourra être oubliée dans cette partie.
Les 3 versions successives de spécification JFlex :

Kabbale (JFlex seul ou autre outil)

Mystère de la théorie des automates et des expressions régulières, automate simple pour une expression régulière compliquée.
Parole de Maître Yoda dans la hutte de Dagobah :
Des trois composantes de la force, (0*|0*1(10*1)*10*|0*1(10*1)*0(1|0(10*1)*0)*0(10*1)*10*), (0*1(10*1)*|0*1(10*1)*0((1|0(10*1)*0))*0(10*1)*), et 0*1(10*1)*0(1|0(10*1)*0)*, le secret sont.
En grec οἶδα (oïda) "je sais", en hébreu יודע (yodé’a) "celui qui sait".

Quel est le secret ?


Cela ressemble à des expressions régulières sur l'alphabet Σ={0,1}. Peut être que cela reconnaît des nombres à partir de leur représentation binaire ?
Utiliser l'outil JFlex pour :
  • Obtenir et dessiner l'automate fini (déterministe et optimal) de chaque expression. Utiliser pour cela l'option --dump de JFlex (ou l'option --dot si elle n'est pas buguée !). Indication : les 3 automates ont 3 états et sont très semblables.
  • Valider le fait que les 3 langages reconnus sont disjoints et que la réunion des 3 langages est le langage Σ*. Les 3 expressions forment une partition disjointe de l'ensemble des chaînes binaires.
  • Tester la reconnaissance des 3 expressions (simultanées) sur les nombres de 1 à N écrits en binaire.
  • Conclure : quel calcul est réalisée par l'automate ?
  • Bonus : expliquer comment l'exercice a été construit, c'est à dire comment à partir du calcul réalisé, on peut facilement construire l'automate, et ensuite construire moins facilement mais mécaniquement les expressions régulières.
Au lieu d'utiliser JFlex, l'on peut préférer les outils en ligne : https://cyberzhg.github.io/toolbox/min_dfa, et http://ivanzuzak.info/noam/webapps/fsm2regex/ pour faire les conversions entre automates et expressions régulières.
  • Un squelette de spécification JFlex pour les différents tests :
  • Résultat de java -jar jflex.jar --dump mod3.jflex :
    ... CharClasses: class 0: { [0-'/']['2'-1114111] } class 1: { ['0'] } class 2: { ['1'] } ... 14 states before minimization, 3 states in minimized DFA Miniminal DFA is State [FINAL] 0: with 1 in 0 with 2 in 1 State 1: with 1 in 2 with 2 in 0 State 2: with 1 in 1 with 2 in 2
    Les 2 autres expressions donnent le même automate avec seulement le [FINAL] qui passe sur l'état 1 puis 2.
  • Graphiquement on a :
  • Le même automate (en réalité la machine de Moore) reconnaît donc tous les mots de façon disjointe en fonction des 3 états d'arrivée associés aux 3 expressions régulières.
  • Et oui, on calcule le modulo 3 !. La première expression régulière reconnaît les représentations binaires des nombres multiples de 3.
  • En fait, si l'on prend l'exercice à l'envers, faire de l'arithmétique dans ℤ/pℤ peut se faire avec un automate à p états (état i = ensemble des nombres congrus a i modulo p). Ici on considère le calcul d'un nombre en fonction de sa représentation en base B (foreach chiffre N=B*N+chiffre), on aura une transition de I vers J sur un chiffre si B*I+chiffre est congru a J modulo p.
  • Le calcul de l'expression régulière compliquée et très ésotérique, pour cet automate simple se fait ensuite mécaniquement par l'algorithme McNaughton et Yamada (récurrence à 3 variables).

Un petit script pour les tests sur les nombres de 1 à N :

Automate avec la syntaxe de "http://ivanzuzak.info/noam/webapps/fsm2regex/" :

#states s0 s1 s2 #initial s0 #accepting s0 #alphabet 0 1 #transitions s0:0>s0 s0:1>s1 s1:0>s2 s1:1>s0 s2:0>s1 s2:1>s2

Variante de la même question


Parole de YHWH sur le mont Sinaï :
A0 = [0369] A1 = [147] A2 = [258] R0 = {A0}|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1})|({A0}?|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))({A0}|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))*({A0}?|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1})) R1 = {A1}|{A2}{A0}*{A2}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A0}?|{A1}{A0}*{A2})|({A0}?|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))({A0}|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))*({A1}|{A2}{A0}*{A2}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A0}?|{A1}{A0}*{A2})) R2 = {A2}|{A2}{A0}*|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A1}|{A1}{A0}*{A0}?)|({A0}?|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))({A0}|{A2}{A0}*{A1}|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A2}|{A1}{A0}*{A1}))*({A2}|{A2}{A0}*({A0}?)|({A1}|{A2}{A0}*{A2})({A0}|{A1}{A0}*{A2})*({A1}|{A1}{A0}*{A0}?))

L'alphabet sont les chiffres de 0 à 9. Que calculent ces 3 expressions pour un nombre écrit en notation décimal ?

Calcul du modulo 3 à partir de la représentation décimale.
L'automate est :

Analyseur lexical manuel (sans JFlex)

Analyseur lexical sans JFlex, Préparation du couplage avec un analyseur syntaxique.
On se donne une classe abstraite SimpleLex.java et une implémentation NatLex0.java qui réalise un analyseur lexical simple.

Prise en main


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.

Bart tue un chasseur


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 :

Premiers pas CUP sans JFlex (CUP sans JFlex)

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 : SimpleLex.java, NatLex0.java
On donne aussi une spécification CUP Nat0.cup pour produire un analyseur syntaxique qui utilise l'analyseur NatLex0 au niveau lexical.

Exécuter l'analyse syntaxique


Analyser le code de la spécification CUP ; Générer l'analyseur syntaxique ; et Tester l'analyseur :
java -jar $LIBCOMPIL/lib/java-cup.jar Nat0.cup ## ou cup Nat0.cup javac -cp .:$LIBCOMPIL/lib/java-cup-runtime.jar *.java java -cp .:$LIBCOMPIL/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

Exécuter correctement l'analyse syntaxique


Modifier l'analyseur lexical NatLex0 et la génération avec l'outil CUP pour obtenir une exécution correcte. Utiliser java -jar $LIBCOMPIL/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.

Bart mange le lapin. le lapin tue un chasseur.


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 diapositives 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 la resynchronisation sur POINT)

Pierre, Papier,... (Bonus)


Étendre l'analyseur pour accepter les énoncés possibles d'un jeu "Pierre, papier, ciseaux, lézard, Spock".
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.
Indication : remplacer "les ciseaux" par "le ciseau" pour tout avoir au singulier.

Premiers pas CUP et JFlex (JFlex + CUP)

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

Addition selon Turing (JFlex+CUP)

Grammaire non ambiguë, Règles de grammaire récursives.
Sur l'alphabet Σ={a,b,c}, on considère le langage
L0 = { anbpcn+p | p≥0, n≥0}.

L0 est algébrique ?


Prouver que ce langage est algébrique déterministe ! (Oups ! de la théorie !).
En pratique, construire une spécification CUP sans conflits qui reconnaît ce langage. Le langage est alors algébrique puisque décrit par une grammaire context-free, et déterministe puisque reconnaissable sans conflits par CUP.
On peut utiliser les spécifications suivantes pour l'analyse ligne à ligne d'un langage sur {a, b, c}*. Pour l'exercice, il convient juste de modifier la définition du symbole l0 dans la spécification CUP.
Une grammaire non ambigüe pour L0 dans CUP :
l0 ::= t0 | A l0 C ; t0 ::= /* */ | B t0 C ;

Variations


Même question pour :
L1 = { anbapban+p | p≥0, n≥0}.
L2 = { anbpan+p | p≥1, n≥0}.
Les grammaires non ambigüe :
l1 ::= B t1 | A l1 A ; t1 ::= B | A t1 A ; l2 ::= t2 | A l2 A ; t2 ::= B A | B t2 A ;

Piège


Même question pour :
L3 = { anbpan+p | p≥0, n≥0}.
Piège : bien que très voisin de L2, L3 est une langage ambigüe ou non déterministe. pas de résolution possible avec CUP !!!
L3 est l'union de L2 et de L4={ a2n, n≥0 }. Mais L4 est algébrique non déterministe au même titre que les palindromes. Der Teufel steckt im Detail F. Nietzsche (le diable se cache dans les détails).
Grammaire ambigüe pour L4 et L3
l4 ::= /**/ | A l4 A ; //Ambigue (non deterministe) l3 ::= l2 | l4 ;

Spécification CUP pour l'ensemble de l'exercice :

Hotelterminus, 1ère légion, 3ème cohorte, 2ème manipule, 1ère centurie (JFlex+CUP)

Actions sémantiques, valeurs sémantiques, calcul à la volée.
L'exercice consiste à écrire sous forme d'un analyseur syntaxique, un traducteur de la numération romaine en numération décimal. On se reportera à l'exercice "Nombres Romains" pour la définition des nombres romains et la classe romGen.java qui génère des nombres romains pour les tests.

On se donne un couple de spécification rom2dec0.jflex et rom2dec0.cup qui réalise l'analyse ligne à ligne de nombres romains entre 1 et 4999.
  • Tester cet analyseur en mode interactif ou avec la classe romGen.
  • Ajouter des valeurs sémantiques et des actions sémantiques dans la spécification CUP, pour que l'analyseur réalise et imprime la conversion décimale de chaque nombre romain correct. Aucun besoin de modifier la grammaire.
Les spécification CUP et JFlex :

Calculatrice Logique (JFlex+CUP)

Variation sur la calculatrice arithmétique.

(source Michel Meynard)

L'objectif de cet exercice est d'écrire une calculette capable de reconnaître et d'évaluer des expressions logiques d'ordre 0.

De manière similaire aux expressions arithmétiques, les expressions logiques d'ordre 0 sont construites à partir des composants suivants :

  • Constantes : 0 ou false ou faux et 1 ou true ou vrai.
  • Opérateurs binaires : conjonction & ou et ou and, disjonction | ou or ou ou, implication =>, équivalence <=>, et le OU exclusif ^.
  • Opérateur unaire : négation ! ou not ou non.
  • Parenthèses : ( et ).

Les expressions logiques sont évaluées de gauche à droite. L'ordre de priorité des opérateurs est : {|, =>, <=>, ^} << & << !. Les associativités droites ou gauches des opérateurs sont à préciser.

Pour la lisibilité des expressions, on ajoutera :

  • Écriture ligne à ligne : une expression est écrite sur une même ligne et on a au plus une expression par ligne.
  • Espaces : les espaces ou les tabulations sont possibles et sans effet.
  • Commentaires : tout texte commençant par # et se terminant à la fin de la même ligne est sans effet.

Exemples :

Calculatrice Logique


Écrire un analyseur syntaxique qui évalue (imprime VRAI ou FAUX) des expressions logiques d'ordre 0 écrites ligne à ligne.

Calculatrice Logique avec variables et controle d'erreur


Ajouter à cette calculette la fonctionnalité suivante :
  • Utilisation de variables avec une table de symbole rudimentaire pour conserver le résultat de calculs précédents.
  • L'affectation et l'utilisation de ces variables ressemblera à la syntaxe C ; par exemple a = 0 | 1 => 0 puis b = a => (0|1).
  • Initialisation par défaut des variables à Faux.
  • Ajouter enfin le traitement des erreurs de syntaxe (ligne incorrecte) et sémantique (variable non initialisée).
Les spécification CUP et JFlex :

Calculatrice Ensembliste (JFlex+CUP)

Yet Another calculatrice, et rappel sur les structures de données Java.
Le but de l'exercice est d'écrire un interpréteur capable de reconnaître et d'évaluer des expressions ensemblistes.

Les expressions ensemblistes que l'on désire reconnaître sont construites à partir des composants suivants :
  • Constantes : {} (ensemble vide), {i} (singleton), ou de façon générale {i, j, k, ... } avec i, j, k... des valeurs entières. L'ordre des éléments ou l'unicité des éléments est indifférent.
  • 3 Opérations ensemblistes : Union, Intersection, Différence. On utilise les mots clés : union, inter, diff.
  • Nom et Affectation de Variables.
  • Des parenthèses : ( et ).
Pour la lisibilité des expressions, on ajoutera :
  • Écriture ligne à ligne : une expression est écrite sur une même ligne et on a au plus une expression par ligne.
  • Blancs : les espaces ou les tabulations sont possibles et sans effet.
  • Commentaires : tout texte commençant par # et se terminant à la fin de la même ligne est sans effet.

Un exemple commun pour les 2 questions :

Calculatrice ensembliste avec notation opérateur


Les opérations sont écrites sous forme d'opérateurs en notation infixe et les parenthèses servent à gérer l'ambigüité et la priorité entre les opérateurs. N.B. : union et inter sont totalement associatifs et inter est usuellement prioritaire sur union.

Écrire l'interpréteur ligne à ligne pour les expressions ensemblistes. Utiliser la classe Java HashSet avec les méthodes add(),remove(),addAll(),removeAll,retainAll()
Cf. question suivante

Calculatrice ensembliste avec notation fonctionnelle (varargs)


Ajouter dans l'interpréteur précédent la reconnaissance des opérations ensemblistes avec une notation fonctionnelle union(xxx, yyy,...). Les "fonctions" union et inter ont un nombre d'arguments quelconque non nul, la fonction diff a 2 arguments.
La paire de spécification JFlex/CUP

Calculatrice Vectorielle (JFlex+CUP)

Yet Another calculatrice.

(source Michel Meynard)

L'exercice consiste à écrire un interpréteur capable de reconnaître et d'évaluer des expressions arithmétiques et vectorielles.

Les expressions sont construites à partir des composants suivants :
  • Constantes Scalaires : des valeurs entières signées selon la notation usuelle.
  • Constantes Vecteurs : un vecteur contient un nombre fini de composantes scalaires, il sera noté entre crochets [ ], avec une virgule , entre chaque composante scalaire. Ex: [3,-2,4,5] ou [2,1].
  • Les composantes d'un vecteur peuvent être des expressions Scalaires.
  • Le vecteur vide à zéro composante noté [].
  • L'opérateur noté + qui réalise l'addition usuelle de valeurs scalaires.
  • L'opérateur noté + qui réalise l'addition de 2 vecteurs. L'addition suppose que les vecteurs soient de même taille, l'addition se fait alors composante par composante. Ex : [3,5,7]+[1,-2,-5]==[4,3,2].
  • L'opérateur noté * qui réalise la multiplication usuelle de valeurs scalaires.
  • L'opérateur noté * qui réalise la multiplication d'un vecteur et d'un scalaire. On autorise la multiplication dans les 2 sens. Ex : 4*[1,2,3]==[1,2,3]*4==[4,8,12].
  • L'opérateur noté . qui réalise le produit scalaire de deux vecteurs de même taille. Ex : [1,2].[1,2]==5.
  • La fonction dim(...) qui prend en argument une expression vectorielle et retourne le nombre de composantes du vecteur. Ex : dim([])==0 , dim([1,3])==2.
  • Des parenthèses ( et ) pour imposer l'ordre d'évaluation des opérateurs.
  • On définira les règles d'associativité et de priorité selon les "usages courants".
Pour la lisibilité et le confort d'utilisation, on ajoutera :
  • Écriture ligne à ligne : une expression est écrite sur une même ligne et on a au plus une expression par ligne.
  • Blancs : les espaces ou les tabulations sont possibles et sans effet.
  • Commentaires : tout texte commençant par # et se terminant à la fin de la même ligne est sans effet.

Un exemple de fichier de test :

Calculatrice scalaire et vectorielle


Écrire l'interpréteur ligne à ligne pour les expressions scalaires et vectorielles. Chaque ligne correcte contient une expression scalaire ou une expression vectorielle dont on imprime la valeur. On prendra soin de signaler les erreurs lexicales (i.e. caractère invalide), les erreurs syntaxiques (i.e. vect*vect), et les erreurs sémantiques (i.e. tailles de vecteurs non compatibles). Utiliser la classe ArrayList avec le constructeur new java.util.ArrayList<>() et les méthodes add(Integer i) et size().
La paire de spécification JFlex/CUP

Variations (Bonus)


Quelques extensions ouvertes :
  • Ajouter des matrices définies comme vecteur de vecteur. On peut définir des vecteurs "horizontaux" avec [ ] et des vecteurs "verticaux" avec { } et avoir 2 écritures pour une même matrice ( {[1,2,3],[3,4,5]} == [{1,3},{2,4},{3,5}] )...
  • Ajouter des variables dans la calculatrice. Ces variables doivent être typées pour différentier les expressions de type scalaire ou de type vecteur. Pour simplifier, on peut décider d'avoir des noms de variable séparées au niveau lexical pour réaliser le typage implicite (i.e noms S* et V*). ...
  • Ajouter d'autres opérations : produit vectoriel, fonction Norme, projection, vecteur unitaire, ...
  • ...

Analyse syntaxique LL manuelle (sans JFlex et sans CUP !)

Analyse syntaxique sans outils, Analyse LL par descente récursive.
Le but de cette exercice est de montrer comment on peut écrire un analyseur syntaxique pour un langage simple sans utiliser les outils compiler's compiler. De manière naturelle, l'analyseur écrit ainsi suivra un schéma d'analyseur LL. La difficulté de cette approche n'est pas dans l'écriture du code qui est une traduction assez directe de la grammaire, mais dans l'écriture de la grammaire qui doit respecter un certain nombre de règles pour rendre possible l'analyse LL : pas de récursivité gauche, factorisation gauche systématique des règles,...

On donne une grammaire algébrique non ambiguë pour des expressions arithmétiques sous la forme :
Axiome = Exp EOF Exp = Terme SuiteTerme ; Terme = Facteur SuiteFacteur ; SuiteTerme = Epsilon | '+' Terme SuiteTerme| '-' Terme SuiteTerme SuiteFacteur = Epsilon | '*' Facteur SuiteFacteur | '/' Facteur SuiteFacteur Facteur = IDENT | INT | '(' Exp ')'
Cette grammaire réalise la priorité usuelle des opérateurs, mais elle fournit une associativité droite pour chaque opérateur, ce qui est invalide pour la soustraction et la division. Ceci découle directement de la contrainte LL qui interdit les récursivités gauches. Le problème peut se résoudre "à la main" par une transformation de récursivité en une boucle... mais ce n'est pas le but de l'exercice.

Écrire une classe Java qui réalise l'analyse syntaxique en suivant cette grammaire. On donne un squelette de la classe qui contient l'analyse lexicale pour une chaîne de tokens fixée dans le code. Compléter cette classe en définissant l'ensemble des méthodes récursives LireX() pour chaque symbole non-terminal X de la grammaire.
  • Le lookahead de 1 est réalisé par la méthode Tok aheadTok().
  • les méthodes LireX() pour les symboles terminaux X sont réalisées sous la forme LireTok(Tok.X).
Et pour vérification de la grammaire, un équivalent JFlex/CUP :

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