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

Portail informatique
La réalisation de cette partie est à faire à 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.


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

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 Proect
  • Donner un nom au projet
  • Désélectionner "Use default location", et sélectionner votre directory mon_projet comme "location".
  • Terminer avec "next"*, "accept"*, "finish" ...
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.

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 Refresf (F5), on peut activer la préference 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" du buildfile
Pour la compilation et l'exécution, on peut au choix :
  • Utiliser l'objectif "run" du buildfile dans la vue Ant. La lecture sur l'entrée standard dans la console Eclipse ne fonctionne pas obligatoirement dans ce cas. On peut définir un fichier d'entrée avec une ligne ARGS=mon_fichier.data dans le fichier "build.prop"
  • 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
  • Installer les plugins "Cup Support" et "Jflex Support" : IDEA/File/Settings/Plugins
  • Lier le type de fichier "*,jflex" au plugin JFlex : IDEA/File/Settings/Editor/FileType
  • Si besoin et pour chaque projet, adapter les librairies du projet de façon à inclure "./lib/java-cup-runtime.jar" et à exclure "./lib/jflex.jar" : IDEA/File/ProjectStructure/ProjectLibraries
  • ...
Couplage JFlex/CUP, Définition des symboles. Écriture de règles de grammaire
Soit les spécifications JFlex et CUP une classe Main() : et un fichier de test

Construire l'analyseur syntaxique et tester sur l'exemple (NB : LIBCOMP désigne votre emplacement de l'arborescence du cours i.e. ~/Compil/LibCompil) java -jar LIBCOMP/lib/jflex.jar lang0.jflex #ou jflex lang0.jflex java -jar LIBCOMP/lib/java-cup.jar lang0.cup #ou cup lang0.cup javac -cp .:LIBCOMP/lib/java-cup-runtime.jar *.java java -cp .:LIBCOMP/lib/java-cup-runtime.jar CupParseMin # Interactif sur stdin java -cp .:LIBCOMP/lib/java-cup-runtime.jar CupParseMin < lang.c 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).

Quelle est la syntaxe acceptée par cet analyseur syntaxique ?
Corriger les spécifications pour que le fichier d'exemple soit 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

La commande Compil-new-cup mon_projet crée un directory 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 directory src pour les fichiers sources Java avec éventuellement gestion des packages
  • un directory bin pour les classes compilées Java
  • un directory lib pour les archives Java
On a de plus un directory spec pour les sources des spécifications CUP et JFlex. On peut librement créer d'autres directories comme spec pour ranger les analyseurs par version, par exercice, ... La seule contrainte est que les noms des spécifications soient couplés sous la forme XXX.jflex et XXX.cupXXX est un nom ou un chemin. On fournit la commande Compil-new-spec old new pour coiper 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 spec. :
  • Tester l'analyseur en mode interactif (make run ou javacup CupParse)
  • Consulter le help de CupParse javacup CupParse -help
  • Tester l'analyseur sur un fichier d'exemple (make run < file ou javacup CupParse < file ou javacup CupParse file1 file2 ...)
  • Tester le mode debug javacup CupParse -debug ...
  • Corriger l'analyseur comme dans la question précedente pour rendre le fichier de test valide

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

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 declaration (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 unique argument.
  • 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
    • ...

Cette question introduit quelques difficultés nouvelles qui seront traitées plus en détails dans l'exercice "Grammaire 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, mais on le calme avec une directive precedence nonassoc ELSE
  • ...

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

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.

Cette question peut être ignoré 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.

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.
Grammaire non ambiguë, Règles de grammaire récursives
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.

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.

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

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 meilleur définition de l'étoile (fermeture de Kleene) 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 qui au moment de choisir ne sait pas si tout les choix seront des solutions. Pour un analyseur LR, l'ambiguïté se traduit par un conflit shift/reduce. Dans le cas de CUP (contrairement a Bison), il n'y a pas de résolution par défaut.

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

É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; Ou le schéma de l'analyse "ligne à ligne"! Spécification pour l'ensemble de l'exercice :
Retranscrire une syntaxe BNF, Valeurs Sémantiques, PrettyPrint
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é.

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/,

La spécification de JSON en ABNF issue du RFC8259 : On donne de plus un guide rapide de la syntaxe ABNF (RFC5234) :
FonctionSyntaxeExplication
Règlename = elements crlfles éléments peuvent être séparés
par des blancs et des crlf (fin de ligne)
Terminaux%xHHcaractère ASCII défini en hexadécimal
%xHH.HH.HHchaîne par concaténation de caractères
%xHH-HHau choix 1 caractère de l'intervalle
ConcaténationE1 E2implicite
AlternativeE1 / E2"ou"
Groupage(E1 E2)application des opérateurs
Répétitions*EE répété N fois, N≥0
n*EE répété N fois, N≥n
nEE répété exactement n fois
Optionnel[ E ]E répété 0 ou 1 fois
Commentaires ; text crlfcommentaires libres

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.
Les étapes de cette question peuvent aussi être traitées en parallèle avec la question suivante. cf. question suivante.

Transformer l'analyseur précédent 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,float...), 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).

Le but du PrettyPtinter est de valider l'analyseur syntaxique. On testera ainsi que le résultat du PrettyPtinter est une entrée valide pour le PrettyPtinter. Le PrettyPtinter est idempotent!

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 gerer l'impression avec indentation, on peut 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(" "); } :};
Grammaire d'opérateurs, Valeurs Sémantiques, Interprétation à la volée Écrire une calculatrice qui analyse des expressions arithmétiques et les évalue (ou interprète) à la volée.

Les expressions sont définies par :
  • Les valeurs numériques sont des entiers
  • Les opérateurs arithmétiques sont : + - / * % (opérateurs binaires uniquement)
  • Les fonctions sont 
    • min(x.y) qui prend 2 arguments
    • max(x,...) qui prend n arguments avec n>0
  • Les expressions arithmétiques sont analysées ligne à ligne. Le résultat est imprimé pour chaque ligne syntaxiquement correcte.
  • Les blancs et commentaires sont ignorés

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 :
Priorité et associativité, Interprétation à la volée
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)

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érentes pour chaque opérateur binaire. Sinon comment différencier "2 + 3 * 4" et "2 * 3 + 4" ?

Le fichier de test précèdent et peut être complété avec :

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 doivent être traités au 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...
  • 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
  • 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.

Ajouter des variables dans la calculatrice :
  • Le nom des variables est libre (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é
  • (optionnel) Ajouter une instruction clear nom qui réinitialise une variable et clear qui réinitialise l'ensemble des variables

Exemple: a = 1 + 2 * 3 \\ = 7 b= 3 * a - 1 \\ = 20 2*b+2 \\ = 42 c= b = a-1 \\ =6 a*b \\ =42 c=(b=b+1)*(a=b-1) \\ =42 (ou 42 ) a \\ =6 (ou 7 !) b \\ =7 (ou 6 !) c=(b=b+1)*(a=b-1) \\ =56 (ou 42 !) d \\ error/warning variable non initialisée clear b b \\ error/warning variable non initialisée clear a \\ error/warning variable non initialisée

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. 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 en utilisant la classe java.util.HashMap<K,V>

Utilisation de HashMap : import java.util.HashMap; //... HashMap<String, Integer> symTab = new HashMap&<String, Integer >'() ; //... String nom; Integer val; //... symTab.put(nom,val); val=symTab.get(nom); if (val == null) /* nom absent! ... */ ; // et aussi symtab.remove(nom); symtab.clear();

Pour l'exercice, on a la choix entre :
  • Intégrer l'ensemble du code Java de la table de symbole dans la spécification CUP.
  • Créer une classe Java (dans le directory src) et limiter le code Java dans la spécification á l'instanciation et l'appel de méthodes sur la table de symboles.
    Un exemple de squelette :
Une spécification Jfleax : Une spécification CUP avec une classe Java annexe pour la table de symboles: Ou une spécification CUP autonome (table de symbole dans la spéc.)

Quelques propositions pour aller plus loin :
  • Ajouter des traitements d'erreurs. Par exemple : division par zero, 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.
Construction Arbre 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 avec la définition de boucles ou de fonctions. 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.
  • Réaliser un traducteur ou un compilateur plutôt qu'un interpréteur.
  • Rester dans une logique d'interprétation, mais avec une analyse sémantique plus poussées : portée des variables, typages des expressions,....

Dans la suite du cours, on réalisera des arbres de syntaxe en utilisant les classe Java suivantes (cf. directory src d'un projet JFlex+CUP)
  • ASTNode.java, classe abstraite pour construire des AST 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 : constrution 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 AST.
La documentation de ces classes est réduites, et il peut donc être utile de lire le source pour en faire une bonne utilisation. L'exercise peut ê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,...).
Modifier la calculatrice précédente pour réaliser la construction explicite d'un Arbre de Syntaxe Complet. On conserve le schéma ligne à ligne de la calculatrice, 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 héritée de ASTNode String toPrint(). La méthode toPrint() utilise par défaut une impression UTF8. En cas de problème modifier dans ASTNode.java la ligne String[] GR = GRAPH[3]

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 i",l1,l2,...ln) :} les symboles étant déclarés de type AST.

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, on a ainsi la construction : v::= v1:l1 ... T ... {: RESULT = new AST("Regle i",l1,...,new AST("Token T"),...) :}
La spécification lexicale La spécification syntaxique

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.
  • L'arbre contient des informations qui ne sont plus utiles Par exemple, des tokens de type parenthèses ou de type séparateur sont devnus 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 va donc être une adaptation de l'arbre de syntaxe avec une définition des nœuds adaptée à la convenance du développeur et aux contraintes des traitements futurs (sémantique, génération de code).
L'utilisation d'un langage Orienté Objet pour implanter l'arbre permet de créer facilement des nœuds typés adaptés à chaque production de la grammaire mais aussi avec l'héritage d'associer 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 sera la classe mère des difféntes productions possibles en membre droit.

Une classe concrète héritière de ASTNode doit:
  • Définir la méthode accept. Pour le moment, avec public void accept(ASTVisitor v) {} .
  • Appeler directement ou indirectement le constructeur "vararg" de ASTNode pour instancier la liste des fils. Ceci permet d'avoir toujours disponible un parcours de l'arbre sous la forme for (ASTNode fils : node) { ...}, ainsi que l'impression avec la méthode String toPrint().
  • Définir ses attributs pour gérer les informations utiles du nœud. On aura ainsi les valeurs sémantiques des tokens (feuilles), et en général les sous-arbres fils (la redondance avec ASTNode est volontaire).
  • Fournir un constructeur pour initialiser l'ensemble des attributs.
  • Eventuellement surcharger la méthode toString() pour adapter l'impression de l'étiquette du nœud.

Construire des classes Java qui héritent directement ou indirectement de la classe ASTNode et modifier la calculatrice pour construire et imprimer des Arbres de Syntaxe Abstraite. Tester au fur et à mesure en remplaçant les nœuds AST par les nouveaux nœuds typés.
  • Créer une classe abstraite Exp associée au symbole non terminal expr de la grammaire public abstract class Exp extends ASTNode{ Exp(ASTNode ... fils){ super(fils);} }
  • Créer des classes concrètes héritières de Exp pour gérer les différentes productions de expr (sauf pour la fonction max(...)). Par exemple public class ExpVar extends Exp{ /* nom de variable */ public String name; public ExpVar(String name) {this.name=name; } public void accept(ASTVisitor v) {} public String toString() { return super.toString() + "(" +name +")"; } } Par exemple public class ExpAff extends Exp{ /* affectation ExpVar = Expr */ public ExpVar v; public Exp e; public Expaff(ExpVar v, Exp e) { super(v,e);this.v=v; this.e=e; } public void accept(ASTVisitor v) {} } Encore ! faire une classe ExpOpBin avec comme attributs 2 Exp et un char pour l'opérateur
  • Créer une classe concrète pour la fonction max() en utilisant un attribut ASTList<Exp>. La construction de la liste des argments de la fonction maximum se fait de manière itérative en créant une liste vide (new ASTList<R>()) et en ajoutant ensuite chaque élément avec la méthode void add(R node)
cf. question suivante.

Notre Calculatrice "déssine des arbres" mais ne calcule plus !. Réintégrer l'évaluation numérique des expressions en ajoutant dans la classe 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'Arbre de Syntaxe et vérifier que l'on retrouve une calculette qui calcule en appelant la méthode eval() pour chaque AST correcte (ligne correcte). Pour pouvoir partager facilement la table de Symbole, en faire un attribut public static de la classe parser cf.question suivante.

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 lArbre de Syntaxe 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 : 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é 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.
  • Ajouter le token "for" dans la spécification lexicale
  • Ajouter la règle "for" dans la spécification syntaxique
  • Créer une classe "ExpFor" pour instancier et évaluer la règle "for"
  // 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=1
  for i 5 for j 5 k=k+i*j
  k  // ==15*15=225
cf question suivante !

Même question avec une boucle while : while expr1 expr2 // "while (expr1!=0) {expr2} "
  // 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écedente (boucle!!!) ou question suivante !

La réalisation de cette partie est un peu fastidieuse et sera reprise intensivement dans le compilateur Minijava. Il s'agit içi d'introduire les principes du pattern Visitor 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é et l'analyse du corrigé.

L'objectif est d'écrire la fonction "Evaluation" de la calculatrice non pas avec un bout de code dans chaque classe de l'AST, mais en regroupant l'ensemble du code dans une seule classe "Eval". 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 difficulté est maintenant dans la classe "Eval" 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 ) { visitTruc()} else .....
Une solution plus "classe" est d'écrire dans la classe "visiteuse" des méthodes visite(NODE node){} pour chaque type de nœud de l'AST. On definit de plus une méthode absttraite accept() sur l'AST avec une implementation 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 !))
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'içi 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érents pour chaque nouveau prototype du visiteur. Le choix du cours est de garder un unique 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();

Mettre en oeuvre le patron de conception "Visiteur", et créer une classe visiteuse Eval pour réaliser l'évaluation numérique de la calculette

  • Pour chaque classe concrète NODE de l'AST, rendre la classe "visitable" :
    • Définir dans la classe NODE : public void accept(ASTVisitor v) {v.visit(this); }
    • Ajouter dans la classe ASTVisitor, la méthode abstraite : public void visit(NODE n);
    • Ajouter dans la classe ASTVisitorDefault, la méthode : public void visit(NODE n) {defaultVisit(n);} ;
  • Ecrire la classe "Eval" qui hérite de ASTVisitorDefaut et qui surcharge les méthodes visit pour chaque type de nœud à évaluer.
  • Créer un constructeur dans la classe "Eval" qui prend en argument un ASTNode, réalise l'évaluation et imprime le résultat.
  • Remplacer lévaluation dans CUP par new Eval(...)
Enfin une solution complète avec les 2 modes d'évaluations : methode eval() dans les nœuds ou classe visiteuse Eval.

La paire de spécifications :

Le visiteur Eval :

Et les classes Java (directory src/) qui définissent l'AST visitable de la calculette :
un peu fastidieux, et utile uniquement pour du debugging Utiliser la méthode addPosition() de ASTNode et l'option -locations de CUP, pour ajouter dans l'AST, les localisations dans le source.

v ::= s1:l1 s2:l2 ... sn:ln {: RESULT = new AST(....); RESULT.addPosition(l1xleft,lnxright :}
La spécification CUP précédente avec gestion des localisations dans le source :
Paradoxe du Bootstrap, Comparaison Compilation/Interprétation, TP Bonus hors présentiel : Brainfuck En route vers le compilateur minijava Démarrer le projet Minijava en réalisant l'analyse lexicale et syntaxique du langage.