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

Exercices d'utilisation couplée de CUP et JFlex

Prologue

Création d'un projet JFlex+CUP à partir de l'archétype

Le code du projet sur GitLabEnse a été récupéré dans le prologue des TP JFlex (seul) : les archétypes Maven.
Les archétypes pour les projets Maven du module ont été créés : enregistrement dans le fichier $HOME/.m2/repository/archetype-catalog.xml du dépôt local.
L'alias compil-nouveau-cup-jflex a été créé pour la création d'un projet JFlex+CUP. Utilisons l'alias pour créer le projet JFlex+CUP qui servira pour le premier exercice :

$ compil-nouveau-cup-jflex cup_exo1_premierspas
création d'un projet JFlex+CUP dans le repertoire cup_exo1_premierspas
...
[INFO] Installing /tmp/cup_exo1_premierspas/target/cup_exo1_premierspas-0.1.0-SNAPSHOT.jar to /home/denis/.m2/repository/eu/telecomsudparis/csc4251_4252/cup_jflex/cup_exo1_premierspas/0.1.0-SNAPSHOT/cup_exo1_premierspas-0.1.0-SNAPSHOT.jar
[INFO] Installing /tmp/cup_exo1_premierspas/pom.xml to /home/denis/.m2/repository/eu/telecomsudparis/csc4251_4252/cup_jflex/cup_exo1_premierspas/0.1.0-SNAPSHOT/cup_exo1_premierspas-0.1.0-SNAPSHOT.pom
[INFO] Installing /tmp/cup_exo1_premierspas/target/cup_exo1_premierspas-0.1.0-SNAPSHOT-tests.jar to /home/denis/.m2/repository/eu/telecomsudparis/csc4251_4252/cup_jflex/cup_exo1_premierspas/0.1.0-SNAPSHOT/cup_exo1_premierspas-0.1.0-SNAPSHOT-tests.jar
[INFO] ------------------------------------------------------------------------
[INFO] BUILD SUCCESS
[INFO] ------------------------------------------------------------------------
...
$ cd cup_exo1_premierspas/
$ ls
pom.xml  readme.md  src  target

Selon le processus de construction du compilateur défini dans le fichier pom.xml, les cibles principales suivantes sont disponibles (voir aussi la figure qui suit) :

mvn clean generate:sources : créer les analyseurs lexical et syntaxique, c'est-à-dire les classes Yylex et parser sans compiler ni exécuter les tests ;
mvn clean install : construire et exécuter les tests du compilateur ;
mvn test : une fois le compilateur construit (incluant aussi les classes de tests), exécuter les tests sur un nouveau contenu d'un des fichiers à analyser par le compilateur. Cette cible est utile lorsque l'on veut tester sans changer le compilateur mais sur un autre contenu d'un des fichiers à analyser.

Processus Maven de construction du compilateur avec l'exécution des tests

Quelques adaptations possibles simples :

changer le fichier de spécification JFlex dans le fichier pom.xml en modifiant le contenu de la balise <lexDefinition> ;
changer le fichier de spécification CUP dans le fichier pom.xml en modifiant le contenu de la balise <cupDefinition> ;
changer le fichier pour les tests dans la classe TestFileCompiler ;
créer un nouveau test avec un nouveau fichier en entrée en créant un nouveau test par mimétisme de la méthode TestFileCompiler::test1 ;
créer un nouveau test avec une nouvelle chaîne de caractères en entrée en créant une nouvelle méthode de test par mimétisme des méthodes TestStringCompiler::testOK1 et TestStringCompiler::testKO1 ;
ne tester que la génération des analyseurs lexical Yylex et syntaxique parser avec la commande mvn generate:sources.

Installation du greffon CUP pour Eclipse

Outre la fonction d'IDE JAVA, Eclipse fournit à travers un greffon CUP, un éditeur syntaxique de spécification CUP et une visualisation des conflits et de l'automate LR généré.

Ouvrir le menu Eclipse > Help > Install New Sofware.
Entrer l'URL http://www2.in.tum.de/projects/cup/eclipse (champ Work with:).
Sélectionner l'ensemble des items qui sont apparus.
Terminer avec next*, accept*, finish, restart Eclipse.

En cas de besoin, la documentation du greffon : http://www2.cs.tum.edu/projects/cup/eclipse.php.
Tester en ouvrant une spécification CUP, c.-à-d. le fichier src/main/resources/cup_exo1_premierspas/cup_exo1_premierspas.cup. Les différentes fonctionnalités du plugin CUP sont accessibles dans les onglets en bas de l'éditeur syntaxique CUP.

Utilisation de l'IDE Eclipse

Dans la question précédente, nous avons créé le nouveau projet JFlex+CUP de nom cup_exo1_premierspas à partir de l'archétype Maven pour un projet JFlex+CUP.
L'arborescence de base est similaire à celle d'un projet JFlex (seul) avec la spécification CUP en plus :

$ $ tree --charset=ascii
.
|-- pom.xml
|-- readme.md
|-- src
|   |-- main
|   |   |-- java
|   |   |   `-- compil
|   |   |       |-- Compiler.java
|   |   |       `-- util
|   |   |           |-- CompilerException.java
|   |   |           `-- Debug.java
|   |   `-- resources
|   |       |-- cup_exo1_premierspas
|   |       |   |-- cup_exo1_premierspas.cup
|   |       |   `-- cup_exo1_premierspas.jflex
|   |       |-- Jflex8bits.include
|   |       |-- JflexCup.include
|   |       `-- Jflex.include
|   `-- test
|       |-- java
|       |   `-- main
|       |       |-- TestFileCompiler.java
|       |       `-- TestStringCompiler.java
|       `-- resources
|           `-- cup_exo1_premierspas
|               `-- cup_exo1_premierspas.txt
`-- target
    |-- classes
...

On peut réaliser la génération JFlex+CUP soit de façon externe à Eclipse avec les commandes Maven, soit de façon intégrée sous Eclipse avec le menu contextuel du projet Eclipse Run as.... Dans les deux cas, la commande Eclipse > File > Refresh (F5) est utile pour assurer la bonne synchronisation d'Eclipse avec le système de fichiers. Pour limiter le recours au Refresh (F5), on peut activer la préférence Eclipse > Window > Preferences > General > Workspace avec « Refresh using native hooks ».
Pour créer le projet, Eclipse demande deux fichiers de configuration : .project et .classpath. Voici la manière de procéder :

il s'agit d'utiliser le greffon m2e (Maven to Eclipse) de Eclipse : au lieu de créer le projet dans Eclipse comme un projet JAVA, importez-le comme un projet Maven (menu File > Import > Maven > Existing Maven Projects > Next puis Browse > ~/CSC4251_4252/cup_exo1_premierspas et enfin Finish). Dans ce cas, c'est Eclipse qui crée les fichiers de configuration .project et .classpath. Dans la vue « package explorer » de Eclipse, un « M » est ajouté à côté du « J » sur l'icone du projet et les cibles Maven sont disponibles dans le menu contextuel : clic droit > Run As :
- Maven clean : supprimer le répertoire target pour effacer tout ce qui a été généré et compilé. Un effet de bord est de voir des erreurs de compilation dans Eclipse : en effet, les classes des analyseurs lexical Yylex et syntaxique parser ont disparu ;
- Maven generate-sources : exécuter JFlex puis CUP pour générer la classe de l'analyseur lexical Yylex puis la classe de l'analyseur syntaxique parser. Comme Eclipse s'aperçoit que le code a changé, le projet est re-compilé et l'erreur de compilation disparaît lorsque la génération JFlex+CUP s'est bien passée ;
- Maven test : exécuter les tests JUnit selon les classes dans l'arborescence src/test/java et qui comportent dans leur nom la chaîne de caractères Test ;
- Maven install : construire le compilateur en enchaînant generate-sources, compile, test-compile, test, etc.

Premier Pas : analyse syntaxique d'un langage de programmation

Couplage JFlex/CUP, Définition des symboles. Écriture de règles de grammaire.

Exécution manuelle

[Lire les sections 1 et 2 du mémento CUP]
Avant d'utiliser uniquement les modules Maven, regardons une exécution manuelle sans Maven, c'est-à-dire uniquement à l'aide de commandes JAVA avec les bibliothèques et des archives java-cup.jar et java-cup-runtime.jar (à télécharger).
Soit les spécifications JFlex et CUP :

lang0.jflex

lang0.cup

et un fichier de test :

lang.c

Construire l'analyseur syntaxique et tester sur l'exemple qui suit :

# générer l'analyse lexical Yylex.java
$ java -jar jflex.jar lang0.jflex
# générer l'analyseur syntaxique parser.java
$ java -jar java-cup.jar lang0.cup
# compiler les fichiers *.java des analyseurs pour créer le compilateur
$ javac -cp .:java-cup-runtime.jar Yylex.java sym.java parser.java
$ alias MonCompilo='java  -cp .:java-cup-runtime.jar parser'
$ echo "int i;" | MonCompilo
$ echo "integer j;" | MonCompilo
$ MonCompilo < lang.c
$ MonCompilo  # Interactif sur stdin

Dans le mode interactif, la fin de fichier EOF s'obtient en tapant ctrl-d. Avec CUP, il est nécessaire d'avoir deux fois EOF pour obtenir une terminaison correcte (lookahead systématique de CUP).

L'exécution de base de l'analyseur syntaxique termine sans rien dire si le fichier est syntaxiquement correct, ou affiche un message Syntax error... et termine sur une Exception JAVA, si une erreur de syntaxe est détectée.

Quelle est la syntaxe acceptée par cet analyseur syntaxique ? L'analyseur : (1) ignore les espaces et les commentaires de style C++, (2) accepte un nombre quelconque de déclarations « simples » de variables, et (3) une déclaration « simple » est de la forme nom_type nom_var;.
En guise d'expérience, corrigeons les spécifications pour que le fichier d'exemple devienne valide. Pour accepter le fichier de test, il faut ajouter char aux noms de type reconnus dans la spécification lexicale.

Environnement du cours

[Lire les sections 3 et 4 du mémento CUP]
Dans le prologue de cette page, vous avez créé le nouveau projet JFlex+CUP cup_exo1_premierspas.
Refaire la question précédente avec l'environnement du cours :

Construire l'analyseur de l'exercice avec le couple de spécifications (à adapter) :

lang1.jflex

lang1.cup
Tout d'abord, retrouver en particulier la définition des méthodes ECHO(), WARN() et WHERE() dans le fichier src/main/resources/Jflex.include. Ensuite, trouver la définition des méthodes TOKEN, avec respectivement un et deux arguments.
Remplacer le contenu du fichier de test src/main/resources/jflex_exo1_premierspas/jflex_exo1_premierspas.txt par le contenu du fichier lang.c
Tester la spécification, c.-à-d. :
- dans un terminal, avec la commande mvn clean install ;
- dans Eclipse, avec l'utilisation par le menu contextuel du projet Maven, Run As > Maven clean puis Run As > Maven install.
Corriger les spécifications JFlex+CUP comme dans la question précédente pour rendre le fichier de test valide.

Grammaire du langage C

Compléter pas à pas, l'analyseur pour reconnaître la syntaxe du langage C.
À chaque étape, il faut :

Ajouter ou compléter les règles de grammaire dans la spécification syntaxique.
Déclarer les nouveaux symboles non-terminaux et terminaux.
Ajouter la reconnaissance des nouveaux symboles terminaux dans la spécification lexicale.
Tester en adaptant le fichier de test (dé-commenter ou ajouter).

De façon informelle, on définit la syntaxe C par :

Un programme est une séquence quelconque de déclaration (déjà fait).
Une déclaration est soit une déclaration de variable, soit une déclaration de fonction de la forme nom_type nom_fonction(nom_type nom_variable) bloc.
Pour le moment, les fonctions ont toujours un argument unique.
Un bloc est une séquence quelconque d'instruction entourée par des accolades { }.
Une instruction peut être :
- un bloc,
- une instruction vide : ;,
- une expression suivie de ;,
- une instruction_while : while (expression) instruction,
- ...
une expression peut être :
- une valeur littérale,
- une variable,
- une expression entre (&nbps;),
- une affectation nom_variable = expression,
- un appel de fonction nom_fonction(expression),
- une opération binaire expression OPBIN expression.
  Ici, CUP va hurler (plein de conflits !). On calme CUP en ajoutant une directive precedence left OPBIN. Pas d'explications pour le moment.
- ...

Pour tester votre solution, vous pouvez utiliser le fichier suivant : exo1c_premierspas.txt

À venir

Encore plus loin (Bonus)

Cette question introduit quelques difficultés nouvelles qui seront traitées plus en détails dans l'exercice "Grammaires de Liste"

Continuer d'étendre la syntaxe avec :

une fonction peut avoir 0 argument,
une fonction peut avoir n arguments avec n>0,
une déclaration de variables peut contenir plusieurs variables de même type,
une variable peut être initialisée dans sa déclaration,
l'instruction if (expression) instruction ou if (expression) instruction else instruction.
CUP va encore hurler aux conflits, mais on le calme avec une directive precedence nonassoc ELSE.
...

Pour tester votre solution, vous pouvez utiliser le fichier suivant : exo1d_premierspas.txt

À venir

le Graal

Pour obtenir une syntaxe complète et conforme du langage C, il faut de l'ordre de 150 lignes pour la spécification lexicale et 500 lignes pour la spécification syntaxique : spécification Lex/Yacc pour ISO-C 2011.
Dans l'exercice, on a fait de l'ordre de 15% du travail !

GaBuZoMeu, ou le langage de Dyck

Écrire une grammaire non ambiguë,

Le peuple Shadok ne connaît que quatre syllabes : Ga, Bu, Zo et Meu. L'usage des majuscules ou des minuscules est indifférent (directive %caseless dans JFlex).
Les mots de la langue Shadok sont obtenus par concaténation de ces syllabes. Selon Wikipédia, on a par exemple : ZoGa signifie pomper, ZoBuGa signifie pomper avec une petite pompe, et ZoBuBuGa signifie pomper avec une grosse pompe.

Le professeur Shadoko a défini la famille des mots « MeuMeu » comme suit :

GaMeu et Buzo sont des mots MeuMeu.
En ajoutant, en même temps, Ga au début et Meu à la fin d'un mot MeuMeu, on obtient un mot MeuMeu.
En ajoutant, en même temps, Bu au début et Zo à la fin d'un mot MeuMeu, on obtient un mot MeuMeu.
La concaténation de deux mots MeuMeu est un mot MeuMeu.
Précisions du rédacteur : le mot vide inconnu des Shadoks est aussi MeuMeu.

Quelques exemples :

Mots MeuMeu : "", GaMeuGaMeu, GaGaMeuMeu, GaBuZoMeu, GaBuZoGaMeuMeu,...
Mots pas MeuMeu : GaBuMeuZo, MeuMeu !, GaGaMeuMeuMeu, GaGaGaMeuMeu,...

MeuMeu est algébrique déterministe !

Prouver que le langage MeuMeu est algébrique déterministe (oups de la théorie !). En pratique, écrire un analyseur lexical et syntaxique pour reconnaître un mot MeuMeu. L'analyse syntaxique doit être sans conflits pour prouver que le langage est déterministe.

À venir

MeuMeu ligne à ligne (Bonus)

Cette question peut être ignorée dans un premier temps. La section "Traitement d'erreur" du mémento CUP est pré-requise.

Modifier l'analyseur pour utiliser un schéma ligne à ligne avec récupération d'erreur : L'entrée contient un mot par ligne et l'analyseur indique pour chaque ligne si le mot est valide ou non. On donne le fichier d'exemple suivant : exo2b_gabuzomeu_dyck.txt.

À venir

Langage de Dyck

Le peuple Gibi, ennemi des Shadoks, possède un langage similaire, mais à la place des syllabes Ga, Bu, Zo et Meu, ils utilisent des symboles ésotériques : {, [, ], }.
Comment est connu le langage MeuMeu chez les terriens ?
cf. Wikipédia ou Solution sur l'importance du langage de Dyck.

À venir

La moyenne selon Turing (Bonus)

Grammaire non ambiguë, Règles de grammaire récursives.

IMFO la moyenne !

Sur l'alphabet

Σ={a,b}

, on considère le langage

L = { a

ⁿb^(n+p)/2a^p | p≥0, n≥0, n pair et p pair} .

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 algébrique, et déterministe puisque reconnaissable sans conflits par CUP.

Par étape, rechercher des grammaires algébriques pour :

$L$ ₀ = { xⁿyⁿ | n≥0 },
$L$ ₁ = { x²ⁿyⁿ | n≥0 },
$L$ ₂ = { z^pt^2p | p≥0 },
$L$ ₃ = { x²ⁿyⁿz^pt^2p| n≥0, p≥0 } ,
et obtenir $L$ en faisant $x=a, y=z=b, t=a$ .

On validera la grammaire en vérifiant la propriété :

Le nombre de mots dans $L$ de taille $N$ vaut $N/3+1$ si N est un multiple de 3, et 0 sinon.

On donne le programme Astar.java qui génère tous les mots de taille

N

sur un alphabet de taille

M

.
On donne de plus, un couple de spécification de départ pour reconnaître et compter les mots d'un langage en suivant un schéma ligne à ligne :

moyenne.jflex

moyenne.cup

À venir

Bonus

Compléter la grammaire précédente, pour traiter le langage

LBonus = { a

ⁿb^(n+p)/2a^p | p≥0, n≥0, n+p pair}.
On a ajouté au langage

L

les mots avec n impair et p impair. Le nombre de mots dans

LBonus

de taille

N

vaut

2N/3+1

N

est un multiple de 3, et 0 sinon. « impair = pair + 1 » : les nouveaux mots de

LBonus

sont donc obtenus en ajoutant un

a

, un

b

et un

a

dans un mot de

L

À venir

Super Bonus

Compléter la grammaire précédente, pour traiter le langage

LSuperBonus = { a

ⁿb^moy(n,p)a^p | p≥0, n≥0}.
où

moy(n,p)

est la moyenne

(n+p)/2

arrondie à l'entier supérieur.
On a ajouté au langage

LBonus

les mots avec

n+p

impair. Le nombre de mots dans

LSuperBonus

de taille

N

vaut

2M+1

N=3M

0

N=3M+1

2M+2

N=3M+2

À venir

Grammaires de liste

[Lire les sections 5 et 6 du mémento CUP]

Règles de grammaire récursives, Mot vide, Éviter des conflits, Valeur sémantique.

On désire tester différentes grammaires de listes. On donne un squelette de départ qui utilise un schéma d'analyse ligne à ligne et valide pour le moment des listes d'un élément entier :

list.jflex

list.cup

Analyser et tester.

Récursivité droite ou gauche

Écrire et tester les grammaires pour :

lista : liste non vide récursive gauche,
listb : liste non vide récursive droite,
listc : liste éventuellement vide récursive gauche,
listd : liste éventuellement vide récursive droite.

Tracer l'ordre dans lequel les entiers sont analysés. Préciser quand est-ce que les actions sur le mot vide sont exécutées.

Quelle est la nature de ces grammaires (linéaires, régulières,...) ?

À venir

Ambiguïté

Quel est le comportement de CUP pour une définition de la forme suivante ?

liste  ::= ENTIER 
       | liste liste  
;

À venir

Liste avec séparateur

Écrire et tester des grammaires pour une liste d'entiers séparés par des virgules :

listf : liste non vide récursive gauche,
listg : liste non vide récursive droite,
listh : liste éventuellement vide récursive gauche,
listi : liste éventuellement vide récursive droite.

C'est par exemple le schéma pour reconnaître les arguments d'une fonction, ou une liste de déclarations de variables de même type (cf. Exercice « Premiers pas »).

Pourquoi les grammaires suivantes sont-elles incorrectes ?

listh1  ::= /* vide */ 
       | listh1 COMMA ENTIER   
;
listh2  ::= /* vide */ 
	| ENTIER
	| listh2 COMMA ENTIER   
;

À venir

Liste avec terminateur

Écrire et tester des grammaires pour une liste d'entiers séparés et terminés par des points-virgules (= chaque entier est suivi d'un point-virgule) :

listj : liste éventuellement vide récursive gauche,
listk : liste éventuellement vide récursive droite.

C'est par exemple le schéma d'un programme défini comme une séquence d'instructions. c'est aussi le schéma de l'analyse « ligne à ligne » régulièrement utilisé dans les exercices.

À venir

Analyse Syntaxique de JSON

[Lire la section 7 du mémento CUP]

Retranscrire une syntaxe BNF, Valeurs Sémantiques, PrettyPrinter.

Le langage JSON

JSON, JavaScript Object Notation, est un format d'échange de données (sérialisation/dé-sérialisation) au même titre que quelques illustres prédécesseurs : XDR, ASN1, XML. La syntaxe de transfert est sous forme de texte directement lisible utilisant éventuellement les caractères du standard Unicode.

L'objectif de l'exercice est d'écrire un analyseur syntaxique pour vérifier la validité de données JSON. On utilisera pour cela la spécification ABNF (Augmented Backus-Naur Form) de la RFC 8259, que l'on transcrira en expressions régulières dans JFlex et en règles de grammaire algébrique dans CUP. Il conviendra de choisir correctement les symboles de la grammaire BNF qui doivent être gérés au niveau lexical ou au niveau syntaxique.

Les références normatives pour la spécification du format JSON sont :

Spécification par l'ECMA (grammaire "graphique") : [ECMA-404] The JSON Data Interchange Format.
Spécification par l'IETF (grammaire ABNF) : [RFC 8259] The JavaScript Object Notation (JSON) Data Interchange Format.
Définition de la syntaxe ABNF de l'IETF : [RFC 5234] Augmented BNF for Syntax Specifications: ABNF.

L'utilisation de ces documents n'est pas indispensable pour l'exercice. Toutes les informations nécessaires sont a priori reprises dans l'énoncé.

Quelques exemples d'objets JSON

Des exemples valides JSON-Example.txt, des exemples invalides JSON-Example-Invalid.txt, et des exemples "vivants" : http://ip.jsontest.com/, http://date.jsontest.com/, http://headers.jsontest.com/.

Autre exemple : firefox:Bookmarks/Show All Bookmarks/Import and Backup/Backup.

Spécification JSON

La spécification de JSON en ABNF issue du RFC 8259 :

JSON-RFC

On donne de plus un guide rapide de la syntaxe ABNF (RFC 5234) :

Fonction	Syntaxe	Explication
Règle	Nom = Éléments crlf	les éléments peuvent être séparés par des espaces et des crlf (fin de ligne)
Terminaux	%xHH	caractère ASCII défini en hexadécimal
	%xHH.HH.HH	chaîne par concaténation de caractères
	%xHH-HH	au choix 1 caractère de l'intervalle
Concaténation	E1 E2	implicite
Alternative	E1 / E2	"ou"
Groupage	(E)	application des opérateurs
Répétitions	*E	E répété N fois, N≥0
	n*E	E répété N fois, N≥n
	nE	E répété exactement n fois
Optionnel	[ E ]	E répété 0 ou 1 fois
Commentaires	; text crlf	commentaires libres

Analyseur Syntaxique

Faire un analyseur syntaxique de JSON avec JFlex et CUP.
On pourra par étape :

traiter le symbole number de la spécification BNF,
traiter le symbole string de la spécification BNF,
traiter tous les symboles sauf array et object,
traiter l'ensemble de la spécification.

Il convient de respecter rigoureusement (sans réinterprétations) la spécification de JSON.
Pas de schéma "ligne à ligne" pour cet exercice.
Le symbole ws peut être traité simplement en ignorant (pas de token) les "espaces" au niveau lexical.
Les étapes de cette question peuvent aussi être traitées en parallèle avec la question suivante.

PrettyPrinter

Afin de valider l'analyseur syntaxique JSON, transformer l'analyseur en un PrettyPrinter. Pour cela ajouter des actions sémantiques dans la spécification CUP pour produire en sortie un texte JSON valide et équivalent à l'entrée.

On pourra par étape :

Ajouter la gestion des valeurs sémantiques pour les symboles number et string. Pour éviter des problèmes sur les types numériques, la valeur d'un number peut rester sous une forme chaîne de caractères.
Ajouter les actions sémantiques, pour produire en sortie un texte JSON valide. On utilisera la possibilité avec CUP de mettre des actions sémantiques en milieu de règle (cf. memento CUP).
Vérifier la validité sur des exemples.
Vérifier que le PrettyPrinter est idempotent ! Le résultat du PrettyPrinter doit être une entrée valide pour le PrettyPrinter.

L'aspect esthétique (Pretty) de la sortie n'est pas la préoccupation principale de l'exercice ; les détails de l'impression (alignement, indentation,...) sont laissés libres.
À titre d'exemple, l'entrée

JSON-EX.json

pourra donner une sortie plutôt Pretty :

JSON-EX.resu

Pour gérer l'impression avec indentation, on peut rapidement intégrer dans la spécification le code :

action code {: /* helpers pour indentation */
   int indent=0;
   void INDENT()  { indent++; }
   void OUTDENT() { indent--; }
   void OUT(String s) { System.out.print(s); }
   void NL() { OUT("\n"); for(int i=0; i<2*indent; i++) OUT(" "); }
:}

Calculatrice sans ambiguïté

[Relire les sections 5 et 6 du mémento CUP]

Grammaire d'opérateurs, Valeurs Sémantiques, Interprétation à la volée.

Écrire une calculatrice qui analyse des expressions arithmétiques et les évalue à la volée. Les expressions arithmétiques sont analysées suivant le schéma ligne à ligne et le résultat est imprimé pour chaque ligne syntaxiquement correcte.
Réaliser le travail de manière incrémentale en ajoutant au fur et à mesure les différentes définitions de la calculatrice et en testant sur des exemples adéquats.

Les expressions sont définies par :

Les constantes numériques (litterals) sont des entiers.
Les opérateurs arithmétiques sont : + - / * % (opérateurs binaires uniquement).
Les fonctions sont :
- min(x, y) qui prend 2 arguments,
- (Bonus) max(x,...) qui prend n arguments avec n>0.
Les espaces et commentaires sont ignorés. Commentaires #.* ou //.*.

Pour l'exercice, on décide de plus que :

Les expressions sont entièrement parenthésées pour supprimer toutes ambiguïtés dans l'application des opérateurs binaires.
Les opérateurs sont regroupés dans une catégorie lexicale OPBIN associée à des valeurs de type Character pour chacun des opérateurs binaires.
La règle centrale de la grammaire est donc de la forme : expr ::= '(' expr OPBIN expr ')';.

Un exemple de test :

calc-par.data

Bonus Lexical :

l'octal et l'hexa pas chère dans jflex

0[x|X][0-9a-fA-F]+ |
[0-9]+ { return TOKEN(ENTIER,Integer.decode(yytext())); }

À venir

Calculatrice avec priorité

[Lire la section 8 du mémento CUP]

Grammaire ambiguë, priorité et associativité, interprétation à la volée, table de symboles.

Préliminaires

Remplacer dans la calculatrice de l'exercice précèdent la règle « centrale » par expr = expr OPBIN expr. Que dit l'analyseur ? Pourquoi ?

À venir

Associativité et Priorité

Réécrire la calculatrice de l'exercice précédent en levant la contrainte de parenthésage obligatoire autour des opérateurs.
Mettre en œuvre dans CUP (directives precedence) les règles usuelles d'associativité et de priorité pour permettre une analyse syntaxique sans conflit.
Pour pouvoir appliquer les règles de priorité, il faut utiliser une catégorie lexicale différente pour chaque opérateur binaire. Sinon comment différencier « 2 + 3 * 4 » et « 2 * 3 + 4 ?

On peut compléter le fichier de test précèdent avec :

calc1.data

À venir

Calculer avec des réels (Bonus, question ouverte)

Intégrer des valeurs numériques flottantes dans la calculatrice. Il semble facile d'ajouter une catégorie lexicale FLOAT et de l'intégrer dans la grammaire.
Quels sont les problèmes ensuite ? Comment essayer de les résoudre ou de les contourner ?

La question est ouverte, mais la réponse finale est que le niveau syntaxique n'est pas le bon endroit pour gérer ces problèmes qui sont par nature du niveau de l'analyse sémantique.

À venir

Variables et Table de symboles

Ajouter des variables dans la calculatrice :

Les noms de variables sont libres (selon les usages courants).
La portée des variables est globale.
Pas de déclarations de variable.
La valeur d'une variable est accédée par son nom.
La politique pour l'initialisation des variables est libre : initialisation implicite à zéro, ou Warning, ou Error, ou...
Affectation sous la forme : nom = expr.
Comme en C ou en Java, l'affectation est une expression. On peut écrire a=b=2*c+1, ou encore a=3*(b=2)+(c=3).
Pour la grammaire, l'affectation est un opérateur avec son associativité et sa priorité.
(Bonus) Ajouter une instruction clear nom qui réinitialise une variable et clear qui réinitialise l'ensemble des variables.

Exemple :

calc2.data

Pour gérer des variables, il est nécessaire d'utiliser une Table de Symboles, c'est-à-dire une structure de données qui fait le lien entre le nom de la variable et l'ensemble des informations utiles sur la variable. De manière générale, on y trouve par exemple : type, valeur, est_initialisée, est_déclarée, visibilité,....
En Java, on peut réaliser rapidement une table de symboles simple en utilisant la classe java.util.HashMap<K,V>.
Utilisation de HashMap pour une table de symboles :

 // Table de symboles rapide dans une spécification CUP
parser code {:
  public java.util.Map<String, Integer> symTab = new java.util.HashMap<>();
:}
// avec dans des actions
// String nom; Integer val;
  symTab.put(nom, val);
  val = symTab.get(nom); if (val == null) {... /* nom absent */ }
  symtab.remove(nom);
  symtab.clear();

À venir

Pour aller plus loin (Bonus)

Quelques propositions pour aller plus loin :

Ajouter des traitements d'erreurs. Par exemple : division par zéro, variable non initialisée...
Ajouter le traitement de la puissance a^b et du MOINS unaire. Utiliser la directive %pred de CUP pour avoir une priorité différente entre le MOINS unaire et le moins binaire.
YASH (Yet Another Shell) : Donner une apparence de shell à la calculatrice :
- Imprimer un prompt.
- Autoriser plusieurs expressions par ligne avec un point-virgule comme séparateur.
- ...
Ajouter des expressions booléennes et une instruction IF.
Ajouter une boucle ou une fonction. A priori très pénible avant de faire l'exercice suivant.
...

Calculatrice et accrobranche

Construction d'arbres de syntaxe, évaluation sur arbre, interprétation sur arbre (boucles).

Pour aller plus loin avec la calculatrice, il devient vite utile ou nécessaire de construire explicitement l'Arbre de Syntaxe. Aller plus loin peut être :

Continuer l'interprétation mais en ajoutant des boucles ou des fonctions dans le langage. On doit alors exécuter plusieurs fois la même partie de programme et donc mémoriser sous une forme ou une autre les parties à ré-exécuter.
Rester dans une logique d'interprétation, mais avec une analyse sémantique plus poussée : portée des variables, typages des expressions,...
Réaliser un traducteur ou un compilateur plutôt qu'un interpréteur.

Dans la suite du cours, on réalisera des arbres de syntaxe en utilisant les classes Java suivantes :

AstNode.java, classe abstraite pour construire des ASTs d'arité quelconque.
Ast.java, classe minimale pour implémenter AstNode avec des nœuds non typées. Les nœuds sont étiquetés par un label. Utilisations : construction de CST ou débogage.
AstList.java, classe générique pour créer des nœuds typés, avec des fils homogènes (Liste de...).
AstVisitor.java et AstVisitorDefault.java, classes pour utiliser un patron de conception « Visiteur » sur les ASTs (cf. exercice suivant).

Il peut être utile de lire le source de ces classes ou le javadoc, pour en faire une bonne utilisation.

Préparation

Il est recommandé de créer un nouveau projet JFlex+CUP.
Recupérer les classes pré-cités dans le nouveau projet.
Recopier les spécifications finales de la calculatrice de l'exercice précèdent.

Cet exercice et l'exercice suivant peuvent être long et parfois répétitif. On peut dans un premier temps limiter les fonctionnalités de la calculatrice en ignorant les opérations : soustraction, division, modulo et max(x,...).

Arbre de Syntaxe Complet : Concrete Syntax Tree

Dans cette question et la suivante, notre calculatrice va uniquement « dessiner des arbres, mais ne calcule plus. La fonction de calcul sera réintégrée ensuite en travaillant sur l'AST complètement construit.

Modifier la calculatrice pour réaliser la construction explicite d'un Arbre de Syntaxe Complet. On conserve le schéma ligne à ligne, avec pour chaque ligne correcte, l'impression de l'arbre de syntaxe correspondant. On utilisera ici la classe Ast.java à travers son constructeur, et la méthode String toPrint() héritée de la classe AstNode.

La méthode toPrint() utilise par défaut une impression Unicode. En cas de problème d'affichage modifier dans AstNode.java, la ligne private static final String[] CS = CSS[1]; // Unicode

Sur le principe, on ne change rien à la grammaire, et on remplace toutes les actions sémantiques par une action « générique » de la forme :

nonterminal Ast v, s1, s2....;
v ::= s1:l1 s2:l2... sn:ln  {: RESULT = new Ast("Regle V", l1, l2..., ln); :}

En pratique, on gère de façon différente les symboles non terminaux (nœuds internes) et les symboles terminaux (feuilles). Seuls les symboles non terminaux sont déclarés de type Ast. Pour les symboles terminaux, on ignore leurs éventuelles valeurs sémantiques et l'on construit les feuilles de l'arbre sous la forme new Ast("Token i").
Pour un symbole terminal T dans un règle, on a ainsi la construction :

 v::= s1:l1... T... {: RESULT = new Ast("Regle V", l1..., new Ast("Token T"),...); :}

Un exemple de résultat :

calcCST.out

À venir

Arbre de Syntaxe Réduit : Abstract Syntax Tree

L'Arbre de Syntaxe Complet est adapté comme preuve de l'analyse syntaxique, mais présente quelques défauts pour les traitements futurs :

Les valeurs sémantiques des tokens qui étaient inutiles pour l'analyse syntaxique doivent maintenant être intégrées dans l'arbre pour la suite.
L'arbre contient des informations qui ne sont plus utiles. Par exemple, des tokens de type parenthèses ou séparateurs sont devenus implicites dans la structure de l'arbre.
Le formalisme des grammaires algébriques a imposé de gérer une liste comme une longue branche (ou droite ou gauche) de nœuds binaires alors que pour la suite, on peut préférer représenter une liste avec un unique nœud d'arité n.
La gestion des priorités a imposé de séparer les opérateurs binaires, mais il peut être plus simple de les regrouper pour la suite.
...

L'Arbre de Syntaxe Réduit (Abstract Syntax Tree) va donc être une adaptation de l'Arbre de Syntaxe Complet avec une définition des nœuds adaptée à la convenance du développeur et aux contraintes des traitements futurs (analyse sémantique, génération de code).
L'utilisation d'un langage Orienté Objet pour implanter l'AST, permet de créer facilement des nœuds typés adaptés à chaque production de la grammaire. De plus, l'héritage permet d'associer ensemble les différentes productions avec le même symbole en membre gauche. Potentiellement, on définit une classe abstraite pour chaque symbole non terminal de la grammaire qui servira de classe mère pour les différentes règles de production de ce symbole.

Réaliser un AST pour la calculatrice :

Définir les différents nœuds de l'AST, c'est-à-dire créer dans src/, des classes Java qui héritent directement ou indirectement de la classe AstNode.
Adapter la calculatrice pour construire dans les actions sémantiques l'arbre de syntaxe en utilisant ces nouveaux nœuds typés.
Imprimer l'Arbre de Syntaxe Abstraite pour chaque expression correcte.
Tester au fur et à mesure du remplacement des nœuds Ast de la question précédente par les nouveaux nœuds de l'AST.

Une classe concrète héritière de AstNode doit :

Définir la méthode accept().
Pour le moment, on n'utilise pas le patron Visitor, et on utilisera la définition : public void accept(AstVisitor v) {}.
Définir les attributs spécifiques du nœud pour gérer les informations utiles du nœud. On aura en général les valeurs sémantiques des tokens (feuilles) directement attachés au nœud, et les sous-arbres fils.
Fournir un constructeur pour initialiser l'ensemble des attributs.
Appeler directement ou indirectement le constructeur varargs de AstNode pour instancier la liste des fils. On a volontairement une redondance entre les fils déclarés comme attributs spécifiques du nœud et les fils déclarés dans la classe ancêtre AstNode. Ceci permet d'avoir toujours disponible un parcours générique de l'arbre sous la forme for (AstNode fils : node) {...}, ainsi que l'impression récursive réalisée par la méthode String toPrint().
Redéfinir la méthode toString() de la classe AstNode pour adapter l'impression de l'étiquette du nœud. (N.B. ne pas utiliser le code autogénéré par votre IDE favori pour toString())

Créer une classe abstraite Exp associée au symbole non terminal expr de la grammaire. On choisit de rendre la méthode accept() concrète dans la classe Exp pour éviter de le faire pour chaque nœud (ce n'est pas très « classe !&nbsp», et à supprimer dès que l'on veut utiliser un « Visiteur »).
/** Expressions, classe abstraite pour Exp*. */ public abstract class Exp extends AstNode { Exp(AstNode... fils) { super(fils); } public void accept(AstVisitor v) {} }
Créer des classes concrètes héritières de Exp pour gérer les différentes productions de expr.
Par exemple avec les noms : ExpEntier, ExpOpBin, ExpFmin, ExpVar, ExpAff. On oublie la fonction max pour le moment. Par exemple&nbps;:
/** Nom de variable. */ public class ExpVar extends Exp { public String name; public ExpVar(String name) { this.name = name; } public String toString() { return super.toString() + "(" + name + ")"; } }
Par exemple :
/** Affectation, ExpVar = Exp. */ public class ExpAff extends Exp { public ExpVar v; public Exp e; public ExpAff(ExpVar v, Exp e) { super(v, e); this.v = v; this.e = e; } }
N.B. : tester dès maintenant la construction et l'impression de l'AST pour l'expression a=b=c.
Encore ! faire une classe ExpOpBin avec 2 attributs Exp et un attribut char pour l'opérateur. Et tester a=a*b+c...
Créer une classe concrète ExpFmax pour la fonction max() en utilisant un attribut AstList<Exp>. La construction de la liste des arguments de la fonction maximum se fait de manière itérative en créant une liste vide avec new AstList<R>(), et en ajoutant itérativement les éléments avec la méthode void add(R node).

Un exemple de résultat :

calcAST.out

À venir

Évaluation sur l'arbre

Maintenant que l'on maîtrise l'art de la sylviculture pour produire un AST en sortie de l'analyse syntaxique, redonnons à notre calculatrice sa vocation initiale de calcul. Il s'agit donc de réintégrer les actions de calcul à la volée de l'exercice précédent dans une fonction d'évaluation par parcours récursif de l'AST.

Réintégrer l'évaluation numérique des expressions en ajoutant dans la classe abstraite Exp une méthode public abstract Integer eval();.
En conséquence, définir concrètement la méthode eval() pour chacun des nœuds de l'AST. Les méthodes eval() réalisent une évaluation récursive dans l'AST. Chaque nœud calcule sa valeur en fonction de la valeur des fils et de la nature du nœud.
Vérifier que l'on retrouve une calculatrice qui calcule en appelant la méthode eval() pour chaque AST correct (ligne correcte).

Pour pouvoir partager facilement la table de Symbole avec les nœuds de l'AST, en faire un attribut public static de la classe parser.

À venir

Boucler la boucle (Bonus)

Nous avons maintenant retrouvé notre calculatrice de l'exercice précédent, mais en remplaçant l'interprétation à la volée par une construction explicite de l'Arbre de Syntaxe Abstraite et une interprétation sur l'arbre. Il devient alors facile (?!?) de rajouter dans le langage de la calculatrice des boucles ou des définitions de fonctions.

Ajouter à la calculatrice, une boucle sous la forme :

while expr1 expr2 // "while (expr1!=0) {expr2} "

On choisit arbitrairement de donner comme valeur à la boucle, la dernière valeur de expr2, ou à défaut -1. Dans la vraie vie, une boucle n'est pas une expression, mais une instruction sans valeur !

Ajouter le token while dans la spécification lexicale.
Ajouter la règle while dans la spécification syntaxique.
Créer une classe ExpWhile pour instancier et évaluer la règle while.

Exemple :

  // Test de la boucle while
  j=0
  i=11
  while i j=j+(i=i-1)
  j   // n(n+1)/2 =55

À venir

Boucle (Bonus, et solution finale)

Même question avec une boucle for :

for VAR ENTIER expr // "for(VAR=1; VAR<=ENTIER; VAR++) { expr }"

ENTIER est une constante entière et VAR est un nom de variable considérée comme globale. La valeur de VAR est écrasée en début de boucle, mais est utilisable dans la boucle et après. On décide arbitrairement que l'évaluation de la boucle retourne la valeur de VAR.

Exemple :

  // Test de la boucle for
  j=1
  for i 5 j=j*i
  j   // 5! = 120
  j=0
  for i 10 j=j+i
  j   // n(n+1)/2 =55
  k=0
  for i 10 for j 10 k=k+i*j
  k  // ==55^2=3025

À venir

Retour aux sources (Bonus)

Très fastidieux, mais outillage utile pour le débogage. Le test sur quelques nœuds ou la lecture du corrigé peut suffire.

Utiliser la méthode addPosition() de AstNode pour ajouter dans l'AST, les localisations dans le source (NB : option -locations de CUP requise dans le fichier pom.xml). Le schéma de base est :

v ::= s1:l1 s2:l2... sn:ln
  {: RESULT = new Astxxx(...);
     RESULT.addPosition(l1xleft,lnxright); :} 

Un exemple de résultat :

calcASTeval_loc.out

À venir

Calculatrice et première visite

La réalisation de cette partie sera reprise intensivement dans le compilateur Minijava. Il s'agit ici d'introduire les principes du patron de conception « Visiteur » (Visitor pattern) et son utilisation pour réaliser des fonctions (sémantiques) sur un Arbre de Syntaxe. Si le temps manque, on peut se limiter à la lecture de l'énoncé, à l'analyse et au test du corrigé. On peut aussi limiter la calculatrice aux constantes entières et aux opérateurs binaires.

Patron de conception Visiteur

L'objectif de l'exercice est d'écrire la fonction Evaluation de la calculatrice de l'exercice précédent, non pas avec un bout de code dans chaque classe de l'AST, mais en regroupant l'ensemble des codes dans une seule classe Evaluation. L'utilité principale pour la compilation est de pouvoir définir différentes fonctions sur l'AST sans modifier à chaque fois la définition de l'AST. La réalisation de la fonction, ou de son algorithme, est aussi plus claire et plus facile, si on la regroupe dans une seule classe avec des attributs et des méthodes spécifiques pour la fonction. La difficulté est alors de pouvoir profiter de l'usage de la liaison dynamique dans les langages Orientés Objets, c'est à dire le fait de pouvoir appeler une méthode liée au type concret d'un objet (this) plutôt qu'a son type déclaré.

La difficulté est maintenant dans la classe Evaluation d'écrire une méthode qui prend en argument un AST mais qui doit exécuter du code différent suivant le type concret du nœud.
Une solution un peu « lourde » peut être d'imbriquer des if (node instanceof Truc) { EvalTruc(node)} else.....
Une solution plus « classe » est d'écrire, dans la classe « visiteuse », des méthodes visit(NODE node){} pour chaque type de nœud NODE de l'AST. On définit de plus une méthode abstraite accept() sur l'AST avec une implémentation dans chaque nœud sous la forme public void accept(AstVisitor v) { v.visit(this); }. Ainsi, dans la classe « visiteuse », pour un AstNode node, l'appel node.accept(this); exécute la méthode accept() de la classe concrète de node qui exécute la méthode visit de la classe visiteuse avec le type concret du nœud en argument.

CQFD., ou pas !, ou cf. aussi diapositives de cours.

Préparer la visite

N.B. : Commencer par supprimer le accept « vide » de la classe abstraite Exp. Cette définition servait juste à ignorer le patron de conception visiteur dans l'exercice précédent.

Pour rendre l'AST visitable, Il faut que pour chaque classe concrète NODE de l'AST :

La méthode accept soit définie dans NODE sous la forme :
public void accept(AstVisitor v) { v.visit(this); }
La méthode abstraite visit soit définie dans l'interface AstVisitor sous la forme :
public void visit(NODE n);
La méthode de visite par défaut soit définie dans le visiteur par défaut AstVisitorDefault sous la forme :
public void visit(NODE n) { defaultVisit(n); } ;

Rendre l'AST de l'exercice précédent visitable et vérifier que cela «&nbps;compile » encore.

À venir

Visite gratuite

Écrire un visiteur Gratos qui parcours récursivement l'AST de la calculatrice et affiche le nombre d'opérateurs binaires des expressions correctes.

La classe Gratos hérite du visiteur AstVisitorDefaut qui fournit le parcours récursif.
La redéfinition (overriding) dans Gratos de méthodes visit(NODE n) permet de définir le traitement particulier de notre visiteur pour chaque type de NODE. En cas de redéfinition, attention de ne pas écraser le parcours récursif fourni par défaut par la méthode defautVisit(n).
Définir un constructeur pour la classe Gratos qui prend en argument un AST et imprime le résultat.
Tester sur la calculatrice en ajoutant un appel new Gratos(e) pour chaque ligne syntaxiquement correcte.

À venir

Visiteur Evaluation

Écrire un visiteur Evaluation qui parcours récursivement l'AST de la calculatrice et réalise l'évaluation des expressions correctes.

La classe Evaluation hérite du visiteur AstVisitorDefaut.
Les méthodes visit(NODE n) sont redéfinies pour réaliser l'évaluation sur chaque nœud. Ne pas oublier de conserver le parcours récursif des fils avec defautVisit(n), ou fils1.accept(this); fils2.accept(this);....
Définir un constructeur pour la classe Evaluation qui prend en argument un AST, l'évalue, et imprime le résultat.
Tester dans la calculatrice avec un appel à new Evaluation(e) pour chaque ligne syntaxiquement correcte.

Le schéma que l'on utilise n'a pas prévu de valeurs de retour ou de paramètres dans la visite alors qu’ici une valeur de retour entière serait pratique pour l'évaluation. Il est facile de réaliser des visiteurs avec paramètres et valeurs de retour mais cela impose d'avoir un accept() différent pour chaque nouveau prototype du visiteur. Le choix du cours est de garder un unique prototype de visiteur et de « simuler » les éventuelles paramètres et valeurs de retour.
Pour « simuler » une valeur de retour entière, il suffit de :

Déclarer une variable globale Integer Resu;
Faire dans l'appelé Resu=xxx; return; à la place de return xxx;
Faire dans l'appelant appel(); xxx=Resu; à la place de xxx=appel();

À venir

Bootstrap et Brainfuck (Hors Présentiel)

Paradoxe du Bootstrap, Comparaison Compilation/Interprétation.

TP Bonus hors présentiel : Brainfuck

CSC4251_4252, Télécom SudParis, Pascal Hennequin, J. Paul Gibson, Denis Conan Last modified: Septembre 2024