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

Portail informatique

Exercices d'utilisation couplée de CUP et JFlex

Prologue : Utilisation d'un IDE

La réalisation de cette partie est à faire et à tester à l'intérieur de l'exercice "Premiers Pas"
L'utilisation d'un IDE Java n'est pas requise pour cette partie du cours, mais deviendra largement utile pour les phases suivantes de la compilation. Dans le cours, le support est fourni uniquement pour Eclipse, mais Intellij IDEA est aussi utilisable.

Installer le plugin CUP sous Eclipse


Outre la fonction d'IDE Java, Eclipse fournit à travers un plugin 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 (CUP, CupEclipsePluginFeature,..)
  • Terminer avec "next"*, "accept"*, "finish", "restart Eclipse"
  • En cas de besoin, la documentation du plugin : http://www2.cs.tum.edu/projekte/cup/eclipse.php

Nouveau projet CUP/JFlex


La création d'un nouveau projet se fait de manière externe à Eclipse avec la commande Compil-new-cup mon_projet. Le projet est ensuite intégré sous Eclipse comme un projet java avec :
  • Ouvrir le menu Eclipse/New/Project/Java Project
  • Désélectionner "Use default location", et sélectionner votre répertoire mon_projet comme "location".
  • Donner un nom au projet Eclipse
  • Terminer avec "next"*, "accept"*, "finish" en prenant soin de ne pas activer l'option "create module-info file".
Tester en ouvrant une spécification CUP (i.e. spec/sample.cup). Les différentes fonctionnalités du plugin CUP sont accessibles dans les onglets en bas de l'éditeur syntaxique CUP.

Génération


On peut réaliser la génération (CUP, JFlex, Javac,...) soit de façon externe à Eclipse avec les outils Make ou Ant, soit de façon intégrée (partiellement) sous Eclipse avec Ant. Dans les deux cas, la commande Eclipse/File/Refresh F5 est utile pour assurer la bonne synchronisation d'Eclipse. Pour limiter le recours au Refresh (F5), on peut activer la préférence Eclipse/Window/Preferences/General/Workspace "Refresh using native hooks".

Pour utiliser la génération Ant depuis Eclipse :
  • Ouvrir Eclipse/Window/Show View/Ant
  • Placer cette vue Ant à votre convenance dans la fenêtre Eclipse
  • Dans la vue Ant, sélectionner l'icône "Add BuildFiles", et sélectionner le fichier build.xml du projet désiré. L'opération est à faire pour chaque nouveau projet (faire aussi des "Remove BuildFiles" pour les anciens projets)
  • Éditer le fichier build.properties, pour indiquer le nom du couple de spécification à utiliser, par exemple NAME=spec/sample
  • La génération des classes Yylex, parser et sym s'obtient avec l'objectif par défaut "generate"

Exécution


Pour la compilation et l'exécution, il est préférable de ne pas utiliser Ant (objectif "run"), mais d'utiliser la fonction Run d'Eclipse sur la classe CupParse.
Pour exécuter sur un fichier de test plutôt que sur l'entrée standard, utiliser le menu Eclipse/Run/Run Configuration/Arguments pour mettre un nom fixe ou bien la valeur ${file_prompt} qui permet de sélectionner le fichier à chaque exécution

Pour les utilisateurs d'Intellij IDEA


  • Adapter les sections précédentes sur Eclipse au fonctionnement d'Intellij
  • Installer les plugins "Cup Support" et "Grammar-Kit" : IDEA/File/Settings/Plugins
  • Lier le type de fichier *.jflex à l'éditeur JFlex de "Grammar-Kit" : IDEA/File/Settings/Editor/FileType
  • Créer les projets de préférence comme "importation de projet Eclipse"
  • En cas de problème de compilation Java, vérifier que java-cup-runtime.jar est bien une librairie active du projet et éventuellement que jflex.jar ne l'est pas. N.B. :jflex.jar contient un java-cup-runtime non compatible (Oui, JFlex est un analyseur syntaxique utilisant CUP !).
  • ... faire remonter les autres adaptations utiles pour compléter ce mini HowTo.

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]
Soit les spécifications JFlex et CUP une classe Main() : et un fichier de test

Construire l'analyseur syntaxique et tester sur l'exemple (N.B. : $LIBCOMPIL désigne votre emplacement de l'arborescence du cours i.e. ~/Compil/LibCompil)
java -jar $LIBCOMPIL/lib/jflex.jar lang0.jflex #ou jflex lang0.jflex java -jar $LIBCOMPIL/lib/java-cup.jar lang0.cup #ou cup lang0.cup javac -cp .:$LIBCOMPIL/lib/java-cup-runtime.jar *.java java -cp .:$LIBCOMPIL/lib/java-cup-runtime.jar CupParseMin < lang.c java -cp .:$LIBCOMPIL/lib/java-cup-runtime.jar CupParseMin # 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 ?
Corriger les spécifications pour que le fichier d'exemple devienne valide.
L'analyseur
  • ignore les blancs et les commentaires de style C++
  • accepte un nombre quelconque de déclarations "simples" de variables
  • une déclaration "simple" est de la forme nom_type nom_var;
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]
La commande Compil-new-cup mon_projet crée un répertoire mon_projet avec l'environnement adéquat pour utiliser CUP+JFlex. Le même projet peut être utilisé pour plusieurs analyseurs différents ou plusieurs versions du même analyseur.
Le projet créé suit un schéma classique d'IDE Java avec :
  • un répertoire src pour les fichiers sources Java avec éventuellement gestion des packages
  • un répertoire bin pour les classes compilées Java
  • un répertoire lib pour les archives Java
On a de plus :
  • un répertoire spec pour les sources des spécifications CUP et JFlex. Les noms des spécifications doivent être couplés sous la forme XXX.jflex et XXX.cupXXX est un nom ou un chemin
  • un répertoire src-others avec des classes Java éventuellement utiles pour certains exercices. En cas de besoin, il suffit de recopier une classe dans le répertoire src pour l'activer
On fournit la commande Compil-copy-spec old new pour copier un couple de spécification old.jflex, old.cup en new.jflex, new.cup

Reprendre la question précédente avec l'environnement du cours :
  • Créer un projet CUP+JFlex et aller dans le projet
  • Regarder les fichiers fournis
  • Tester la génération avec make : make, make spec/sample, make run
  • Tester la génération avec ant : ant -p, ant -DNAME=spec/sample, ant run
  • Choisir entre ant et make, ou pas
  • Construire l'analyseur de l'exercice avec le couple de spécifications :
  • Tester l'analyseur en mode interactif (make run ou Compil-run-parse)
  • Consulter le help de CupParse Compil-run-parse -help
  • Tester l'analyseur sur un fichier d'exemple (make run < file ou Compil-run-parse < file ou Compil-run-parse file1 file2...)
  • Tester le mode debug Compil-run-parse -debug...
  • Corriger l'analyseur comme dans la question précédente pour rendre le fichier de test valide.

Environnement IDE Eclipse (ou Intellij)


Configurer et tester l'environnement Eclipse sur le projet précédent (cf. Prologue).
Choisir votre mode de fonctionnement pour la suite entre :
  • Tout en ligne de commande avec son éditeur favori (emacs, vi,...)
  • En ligne de commande, mais avec Eclipse pour l'édition syntaxique CUP
  • Génération et Exécution sous Eclipse, et uniquement la création de projet en ligne de commande.

Grammaire du langage C


Compléter pas à pas, l'analyseur pour reconnaître la syntaxe du langage C.
A 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 ()
    • 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
    • ...

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

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

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.
Les spécifications et un fichier d'exemple :

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. Wikipedia ou Solution sur l'importance du langage de Dyck.
Le langage "MeuMeu" est connu comme le langage des mots bien parenthésés, ou langage de Dyck avec 2 paires de parenthèses.
Ce langage joue un rôle particulier en informatique théorique dans la mesure où il apparaît comme l'exemple générique ou générateur de tout les langages algébriques.
Soit Dn, le langage de Dyck sur n paires de parenthèses, on a les énoncés équivalents du théorème de Chomsky-Schützenberger :
  • D2 est un générateur du "cône rationnel" des langages algébriques.
  • Tout langage algébrique est une "transduction rationnelle" du langage D2.
  • Tout langage algébrique L est une image homomorphe de l'intersection d'un langage rationnel K et d'un langage de Dyck Dn
    L = h(K ∩ Dn) avec h morphisme alphabétique.
  • Tout langage algébrique L est une image homomorphe de l'intersection d'un langage rationnel K et d'une image homomorphe inverse de D2
    L = h(K ∩ g-1 (D2)) avec h et g morphismes alphabétiques.

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 = { anb(n+p)/2ap | 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 context-free, et déterministe puisque reconnaissable sans conflits par CUP.
Par étape, rechercher des grammaires context-free pour :
  • L0 = { xnyn | n≥0 }
  • L1 = { x2nyn | n≥0 }
  • L2 = { zpt2p | p≥0 }
  • L3 = { x2nynzpt2p| 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 tout 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 :
cf. question suivante.

Bonus


Compléter la grammaire précédente, pour traiter le langage
LBonus = { anb(n+p)/2ap | 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 si 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
cf. question suivante.

Super Bonus


Compléter la grammaire précédente, pour traiter le langage
LSuperBonus = { anbmoy(n,p)ap | p≥0, n≥0}.
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 si N=3M, 0 si N=3M+1 et 2M+2 si N=3M+2.

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 :

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,...) ?
lista ::= ENTIER:n {: PRN(n); :} | lista ENTIER:n {: PRN(n); :} ; listb ::= ENTIER:n {: PRN(n); :} | ENTIER:n listb {: PRN(n); :} ; listc ::= /* vide */ {: PRN(); :} | listc ENTIER:n {: PRN(n); :} ; listd ::= /* vide */ {: PRN(); :} | ENTIER:n listd {: PRN(n); :} ;
Pour une entrée 0 1 2 3, on a les exécutions
lista : 0 1 2 3 OK
listb : 3 2 1 0 OK
listc : vide 0 1 2 3 OK
listd : vide 3 2 1 0 OK
Les valeurs entières sont analysés dans l'ordre pour des règles récursives gauches et en ordre inverse pour les règles récursives droites. Dans les deux cas, l'action sur le mot vide sera exécutée en premier.
Les règles récursives gauches sont interdites pour des analyses LL mais sont préférables (performances) pour des analyseurs LR.

Les grammaires sont linéaires droites ou gauches et donc régulières. Les langages reconnus sont (ENTIER)+NL et (ENTIER)*NL

Ambiguïté


Quel est le comportement de CUP pour une définition de la forme suivante ?
liste ::= ENTIER | liste liste ;
La définition de liste est correcte sur le plan théorique. Pour le mathématicien, c'est même la meilleure définition de la fermeture de Kleene (l'étoile) comme fermeture transitive pour la concaténation.
Cette définition produit toutefois une grammaire ambiguë !!!.
Par exemple, pour l'entrée "ENTIER ENTIER ENTIER", on a deux analyses possibles : "[[ENTIER ENTIER] ENTIER]" ou "[ENTIER [ENTIER ENTIER]]".
Cette ambiguïté engendre de l'indéterminisme au niveau d'un analyseur syntaxique qui ne sait pas décider quelle est la "bonne" solution ou pas si les choix sont équivalents.
Pour un analyseur LR, l'ambiguïté se traduit par un conflit shift/reduce. Dans le cas de CUP (contrairement à Bison), il n'y a pas de résolution par défaut.

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 ;
listf ::= ENTIER:n {: PRN(n); :} | listf COMMA ENTIER:n {: PRN(n); :} ; listg ::= ENTIER:n {: PRN(n); :} | ENTIER:n COMMA listg {: PRN(n); :} ; listh ::= /* vide */ | listf ; listi ::= /* vide */ | listg ;

listeh1 reconnaît ",1,2" et pas "1,2" !
listeh2 reconnaît "1,2" mais aussi ",1,2".

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éfinit comme une séquence d'instructions. c'est aussi le schéma de l'analyse "ligne à ligne" régulièrement utilisé dans les exercices.
Spécification pour l'ensemble de l'exercice :

Analyse Syntaxique de JSON (A rendre)

[Lire la section 7 du mémento CUP]
Retranscrire une syntaxe BNF, Valeurs Sémantiques, PrettyPrint

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 human-readable utilisant éventuellement les caractères Unicodes (UTF8/UTF16/UTF32).

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 RFC8259, 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 :
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 RFC8259 : On donne de plus un guide rapide de la syntaxe ABNF (RFC5234) :
Fonction Syntaxe Explication
Règle name = elements crlf les éléments peuvent être séparés
par des blancs 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 tout 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 "blancs" au niveau lexical.
  • Les étapes de cette question peuvent aussi être traitées en parallèle avec la question suivante.
cf. 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 (int, long, double...), 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.
A titre d'exemple, l'entrée pourra donner une sortie plutôt pretty :
Pour gérer proprement l'impression avec indentation, on peut utiliser la classe src-others/IndentWriter.java ou de manière plus simple intégrer dans la spécification le code :
action code {: /* helpers pour indentation */ int indent=0; void OUT(String s) { System.out.print(s); } void NL() { /* newline et indentation */ OUT("\n"); for(int i=0; i<3*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 blancs 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 :

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 ?
La grammaire est devenue fortement ambiguë, ce qui est signalé dans CUP par des conflits shift/reduce (cf. cours et mémento CUP)

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 :

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.
Quelques difficultés :
  • Le modulo n'accepte pas un réel comme argument
  • La division euclidienne n'est pas la division des réels
  • Quel type pour les valeurs sémantiques ? Entier, Réel, ou une union des deux
  • Comment gérer "Entier + Entier -> Entier", "Entier + Réel -> Réel"... ?
  • ...
Quelques solutions ou contournements :
  • Séparer dans la grammaire les expressions entières et les expressions réelles. Cela résout largement les différents problèmes mais augmente énormément le nombre de règle dans la grammaire (croissance quadratique)... Ingérable...
  • Utiliser un type "union" pour les valeurs sémantiques. La grammaire reste inchangée et c'est uniquement dans chaque action sémantique que l'on va valider la conformité des types et les opérations de transtypage (cast) nécessaires. C'est conceptuellement la bonne solution, car le problème est de nature sémantique et trouve peu d'utilité dans l'utilisation des grammaires algébriques.
  • Transformer les Entiers en Réels le plus tôt possible. On perd sans doute la division euclidienne et le modulo mais on modifie au minimum la calculette existante. On a par exemple l'adaptation rapide de la calculatrice avec : et

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 :

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();
On trouvera aussi dans le dossier src-other/ d'un projet CUP, une classe SymbolTable qui encapsule l'utilisation d'une HashMap pour faire une table de symboles rapide. Cette classe peut être utilisée pour l'exercice en la recopiant dans le dossier src/.
Une spécification JFlex : et une spécification CUP (avec table de symbole dans la spéc.)

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 (cf. répertoire src-others/ d'un projet JFlex+CUP) :
  • 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 debug
  • 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 (Compil-new-cup nomProjet).
  • Recopier les classes src-others/Ast*.java dans le répertoire src/
  • 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 : MOINS, DIV, MOD et max(x,...).

Arbre de Syntaxe Complet : Concrete Syntax Tree


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 UTF8. En cas de problème d'affichage modifier dans AstNode.java, la ligne final String[] cs = charsets[1];
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 :
La spécification lexicale est la même que pour l'exercice précédent (calcCST.jflex==calc2.jflex).
La spécification syntaxique avec les nouvelles actions sémantiques et l'impression des CST :

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().
  • Surcharger la méthode toString() pour adapter l'impression de l'étiquette du nœud.

  • 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 !", 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
    /** 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 :
La spécification lexicale est inchangée (calcAST.jflex==calcCST.jflex==calc2.jflex).
La spécification syntaxique est adaptée en utilisant les nouveaux nœuds de l'AST :
Et les nœuds de l'AST src/Exp*.java :

Évaluation sur l'arbre


Notre Calculatrice "dessine des arbres" mais ne calcule plus !
  • 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
Pour la spécification CUP, on modifie juste l'action pour les lignes syntaxiquement correcte :
| lignes expr:e {: System.out.println("AST Eval=" + e.eval()); System.out.println(e.toPrint()); :} NL
Le reste de la solution (méthodes eval() dans src/Exp*.java) est à suivre dans la question suivante.

Boucler la boucle


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
cf. question précédente (on tourne en rond !) ou question suivante.

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
La solution complète avec impression des ASTs et évaluation sur l'arbre.

Les 2 spécification JFlex et CUP intégrant les boucles for et while :

L'AST (src/Exp*.java) avec la méthode eval() dans chaque nœud :

Retour aux sources (Bonus)

Très fastidieux, mais outillage utile pour le debugging. Le test sur quelques nœuds ou la lecture du corrigé peut suffire.
Utiliser la méthode addPosition() de AstNode et l'option -locations de CUP, pour ajouter dans l'AST, les localisations dans le source. 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 :
La spécification CUP précédente, complétée avec la gestion des localisations dans le source :

Calculatrice et première visite

La réalisation de cette partie est un peu fastidieuse et 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é.

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 du code 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. L'inconvénient est que l'on perd 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 slides de cours.

Préparer la visite


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 "compile" encore. N.B. : Commencer par supprimer le accept "vide" de la classe abstraite Exp.
L'interface AstVisitor, et le visiteur par défaut AstVisitorDefault : Les classes src/Exp*.java avec un "vrai" accept() :

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 surcharge 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 surcharge, 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.
Adaptation de la spécification CUP :
| lignes expr:e {: new Gratos(e); System.out.println("AST Eval=" + e.eval()); System.out.println(e.toPrint()); :}
Et le visiteur gratuit :

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 surchargées 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();
Le visiteur Evaluation et la spécification CUP avec le test de Gratos et Evaluation

Bootstrap et Brainfuck (Hors Présentiel)

Paradoxe du Bootstrap, Comparaison Compilation/Interprétation,
TP Bonus hors présentiel : Brainfuck

Minijava : on y va !!!

En route vers le compilateur Minijava
Démarrer le projet Minijava en réalisant l'analyse lexicale et syntaxique du langage.

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