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

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

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 ?

Solution dans `javac OpenJdk`

Expliquer la résolution faite dans javac à partir des extraits des sources : Generic-javac-src.txt.

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.

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 ?

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

nombre_aere.data

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

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 :

Les "Constantes Entières" représentent des valeurs fixes pour les types primitifs : byte, short, int, et long.
Les "Constantes Entières" peuvent s'écrire en utilisant les systèmes de numération : décimal, hexadécimal, octal, et binaire.
Une "Constante Décimale" utilise les chiffres 0 à 9.
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.
Une "Constante Octal" utilise les chiffres 0 à 7. La notation commence alors par le préfixe 0.
Une "Constante Binaire" utilise les chiffres 0 et 1. La notation commence alors par le préfixe 0b ou 0B.
Une "Constante Entière" est analysée par défaut comme un int (valeur sur 4 octets).
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.
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".
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

JavaConst.java

et le résultat attendu en sortie de l'analyseur

JavaConst.resu

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

71mot.data

et le résultat attendu en sortie de l'analyseur

71mot.resu

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 :

commence par la séquence <!--,
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 -.
termine par la séquence -->,
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 :

<!-- VALIDES : --> 
<!---->
<!-- COM-MENT- -->
<!---CO-ME-NT- -->
<!-- -><!-COM->-->
<!-- >COM-
-MENT- -->

<!-- --NON-- --VALIDES :-- -->
<! COMMENT >
<!-- -COMMENT --->
<!--->COMMENT -->
<!--> COMMENT -->
<!-- COMMENT -- >
<!-- -->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é.

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

mail-petit.txt

ou un exemple plus long

mail.txt

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.

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", et en sanskrit योध (yoddha) "guerrier".

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.

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 ?

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

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; }
[^]           {}

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.

Nat0.cup

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.

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

langnat0.jflex

et

langnat0.cup
Tester l'analyseur.
Compléter les deux spécifications pour obtenir l'analyseur de l'exercice précédent.

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 L₀ = { aⁿb^pc^n+p | p≥0, n≥0}.

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

turingAdd.jflex

turingAdd.cup

Variations

Même question pour : L₁ = { aⁿba^pba^n+p | p≥0, n≥0}. L₂ = { aⁿb^pa^n+p | p≥1, n≥0}.

Piège

Même question pour : L₃ = { aⁿb^pa^n+p | p≥0, n≥0}. Piège : bien que très voisin de L₂, L₃ est une langage ambigüe ou non déterministe. pas de résolution possible avec CUP !!!

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.

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 :

log-calc.data

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

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 :

set-calc.data

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

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.

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 :

vect.data

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

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

AnalyseLL.java

CSC4251_4252, TELECOM SudParis, P. Hennequin,Last modified: Juillet 2022

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

Exercices en vrac JFlex et CUP

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

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

Conflit lexical/Syntaxique

Solution dans javac OpenJdk

Solution dans le compilateur JDT d'eclipse

Une Solution simple, mais incorrecte

Java Cold Case

Postscriptum de l'auteur

AEIOUY (JFlex seul)

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

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

Constantes entières Java (JFlex seul)

Mot de Passe (JFlex seul)

Nombres Romains (JFlex seul)

Nombre romain valide

Fonction Calculus

Commentaire HTML (JFlex seul)

Analyse lexicale

Entête de Mail RFC822 (JFlex seul)

Analyse lexicale sans super-état

Analyse lexicale avec super-état

Rapport synthétique

Kabbale (JFlex seul ou autre outil)

Quel est le secret ?

Variante de la même question

Analyseur lexical manuel (sans JFlex)

Prise en main

Bart tue un chasseur

Premiers pas CUP sans JFlex (CUP sans JFlex)

Exécuter l'analyse syntaxique

Exécuter correctement l'analyse syntaxique

Bart mange le lapin. le lapin tue un chasseur.

Pierre, Papier,... (Bonus)

Premiers pas CUP et JFlex (JFlex + CUP)

Addition selon Turing (JFlex+CUP)

L0 est algébrique ?

Variations

Piège

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

Calculatrice Logique (JFlex+CUP)

Calculatrice Logique

Calculatrice Logique avec variables et controle d'erreur

Calculatrice Ensembliste (JFlex+CUP)

Calculatrice ensembliste avec notation opérateur

Calculatrice ensembliste avec notation fonctionnelle (varargs)

Calculatrice Vectorielle (JFlex+CUP)

Calculatrice scalaire et vectorielle

Variations (Bonus)

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

Solution dans `javac OpenJdk`

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

L₀ est algébrique ?