Compilation : De l'algorithme à la porte logique (2023-2024)

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.
Terminer avec next*, accept*, finish, restart Eclipse.
En cas de besoin, la documentation du plugin : http://www2.cs.tum.edu/projects/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, Java,...) 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 de 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 !).
Pour la fenêtre Ant : invalider dans Ant/Build File properties les options "Make Build in background" et "Close message if no error occurred". Les messages de jflex et cup seront alors toujours accessibles.
... faire remonter les autres adaptations utiles pour compléter ce mini guide.

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 :

lang0.jflex

lang0.cup

et un fichier de test :

lang.c

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 Yylex.java sym.java parser.java
  alias MonCompilo='java  -cp .:$LIBCOMPIL/lib/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 ?
Corriger les spécifications pour que le fichier d'exemple devienne valide.

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.cup où XXX 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 :

lang1.jflex

lang1.cup

.
Tester l'analyseur en mode interactif (make run ou Compil-run-parse).
Consulter l'aide 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 débogage 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.
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 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.

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 gabu1.data.

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.

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

moyenne.jflex

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

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

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

Ambiguïté

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

liste  ::= ENTIER 
       | liste liste  
;

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   
;

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.

Analyse Syntaxique de JSON (A rendre)

[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.
A 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())); }

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 ?

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

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.

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

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

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

Bonus pour les amoureux de biodiversité sylvicole : La classe src-others/PrintAst.java fournit 15 modes d'impressions d'AST. Démonstration avec le main() de la classe. Utilisation avec la méthode statique PrintAst.print(AstNode n, int i) // i=0..14.

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 !", 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 :

calcAST.out

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

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

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

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

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é. 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 "compile" encore.

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.

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

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.

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