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

Exercices d'utilisation couplée de CUP et JFlex

Prologue

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

Le code du projet sur GitLabEnse a été récupéré dans le prologue des TP JFlex (seul) : les archétypes Maven.

Les archétypes pour les projets Maven du module ont été créés : enregistrement dans le fichier $HOME/.m2/repository/archetype-catalog.xml du dépôt local.

L'alias compil-nouveau-cup-jflex a été créé pour la création d'un projet JFlex+CUP. Utilisons l'alias pour créer le projet JFlex+CUP qui servira pour le premier exercice :

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

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

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

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

Quelques adaptations possibles simples :

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

Utilisation de l'IDE Eclipse

Dans la question précédente, nous avons créé le nouveau projet JFlex+CUP de nom cup_exo1_premierspas à partir de l'archétype Maven pour un projet JFlex+CUP.

L'arborescence de base est similaire à celle d'un projet JFlex (seul) avec la spécification CUP en plus :

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

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

Pour créer le projet, Eclipse demande deux fichiers de configuration : .project et .classpath. Voici la manière de procéder :

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

Premier Pas : analyse syntaxique d'un langage de programmation

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

Exécution manuelle (optionnelle)

[Lire les sections 1 et 2 du mémento CUP]

Avant d'utiliser uniquement les modules Maven, regardons une exécution manuelle sans Maven, c'est-à-dire uniquement à l'aide de commandes JAVA avec les bibliothèques et des archives java-cup.jar et java-cup-runtime.jar (à télécharger).

Soit les spécifications JFlex et CUP (lang0.jflex et lang0.cup), et un fichier de test (lang.c), construire l'analyseur syntaxique et tester sur l'exemple qui suit :

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

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

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

Quelle est la syntaxe acceptée par cet analyseur syntaxique ? L'analyseur : (1) ignore les espaces et les commentaires de style C++, (2) accepte un nombre quelconque de déclarations « simples » de variables, et (3) une déclaration « simple » est de la forme nom_type nom_var;.

En guise d'expérience, corrigeons les spécifications pour que le fichier d'exemple devienne valide. Pour accepter le fichier de test, il faut ajouter char aux noms de type reconnus dans la spécification lexicale.

Environnement du cours

[Lire les sections 1, 2, 3 et 4 du mémento CUP]

Dans le prologue de cette page, vous avez créé le nouveau projet JFlex+CUP cup_exo1_premierspas.

Refaire la question précédente avec l'environnement du cours selon les consignes suivantes.

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

lang1.jflex

lang1.cup

Tout d'abord, retrouver en particulier la définition des méthodes ECHO(), WARN() et WHERE() dans le fichier src/main/resources/Jflex.include. Ensuite, trouver la définition des méthodes TOKEN, avec respectivement un et deux arguments.

Remplacer le contenu du fichier de test src/main/resources/jflex_exo1_premierspas/jflex_exo1_premierspas.txt par le contenu du fichier lang.c

Tester la spécification, c.-à-d. :

dans un terminal, avec la commande mvn clean install ;
dans Eclipse, avec l'utilisation par le menu contextuel du projet Maven, Run As > Maven clean puis Run As > Maven install.

Corriger les spécifications JFlex+CUP comme dans la question précédente pour rendre le fichier de test valide.

Grammaire du langage C

Compléter pas à pas, l'analyseur pour reconnaître la syntaxe du langage C.

À chaque étape, il faut :

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

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

Un programme est une séquence quelconque de déclarations (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'instructions 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,
- une opération binaire expression OPBIN expression.
  Ici, CUP va hurler (plein de conflits !). On calme CUP en ajoutant une directive precedence left OPBIN (en considérant que l'on a rassemblé tous les opérateurs binaires dans une unité lexicale (token). Pas d'explications pour le moment : la section 8 du Mémento CUP sur la gestion des priorités sera l'objet d'un exercice spécifique avec la calculatrice.

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

exo1c_premierspas.txt

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

TYPE = "int"|"long"|"char"|"void"|"float"
IDENT = [a-zA-Z] [a-zA-Z0-9]*
IGNORE = \R | [ \t\f] | "//".*
DIGIT = [0-9]
LITTERAL =  {DIGIT}+ \.? | {DIGIT}* \. {DIGIT}+ |  \' [^\'] \' | \" [^\"]* \" 
OPBIN = [-+*/%<>] | "==" | "!=" | "&&" | "||" | "<=" | ">=" 
AFFECT = [-+*/]?"="

%%
{TYPE}       { return TOKEN(TYPE);   }
"while"      { return TOKEN(WHILE);  }
{IDENT}      { return TOKEN(IDENT);  }
{AFFECT}     { return TOKEN(AFFECT); }
{OPBIN}      { return TOKEN(OPBIN);  }
"("          { return TOKEN(LPAR);   }
")"          { return TOKEN(RPAR);   }
"{"          { return TOKEN(LBRACE); }
"}"          { return TOKEN(RBRACE); }
";"          { return TOKEN(SEMI);   }
{LITTERAL}   { return TOKEN(LITTERAL); }
{IGNORE}     { }
[^]          { WARN("Unknown caractere : " + yytext()); return TOKEN(UNK); }

Attention aux potentiels « ... » dans le code inséré !

...
init with   {: System.out.println("Début de l'analyse syntaxique"); :}
...
...
action code {: void DEBUG(String s) {System.out.println(s);} :}

terminal TYPE, IDENT, SEMI, UNK;
nonterminal programme, declaration;

terminal LPAR, RPAR, LBRACE, RBRACE;
terminal LITTERAL, AFFECT, OPBIN;
terminal WHILE;
nonterminal bloc, list_instr, instr;
nonterminal instr_while, expr;

precedence left OPBIN;

programme ::= /* vide */
          | programme declaration {: :}
;
declaration ::= TYPE IDENT SEMI                   {: DEBUG("Variable"); :}
            |   TYPE IDENT LPAR TYPE IDENT RPAR bloc
                     {: DEBUG("fonction"); :}
;
bloc ::= LBRACE list_instr RBRACE {: DEBUG("bloc"); :} 
;
list_instr ::= /* vide */
         | list_instr instr {: DEBUG("instruction"); :}
;
instr ::= bloc
      | SEMI
      | expr SEMI
      | instr_while
;
expr ::= LITTERAL
     | IDENT
     | expr OPBIN expr
     | LPAR expr RPAR
     | IDENT AFFECT expr
     | IDENT LPAR expr RPAR
;
instr_while ::= WHILE LPAR expr RPAR instr  {: DEBUG("while"); :} 
;
...

Encore plus loin (optionnel)

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

Continuer d'étendre la syntaxe avec :

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

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

exo1d_premierspas.txt

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

TYPE = "int"|"long"|"char"|"void"|"float"
IDENT = [a-zA-Z] [a-zA-Z0-9]*
IGNORE = \R | [ \t\f] | "//".*
DIGIT = [0-9]
LITTERAL =  {DIGIT}+ \.? | {DIGIT}* \. {DIGIT}+ |  \' [^\'] \' | \" [^\"]* \" 
OPBIN = [-+*/%<>] | "==" | "!=" | "&&" | "||" | "<=" | ">=" 
AFFECT = [-+*/]?"="

%%
{TYPE}       { return TOKEN(TYPE);   }
"while"      { return TOKEN(WHILE);  }
"if"         { return TOKEN(IF);     }
"else"       { return TOKEN(ELSE);   }
"for"        { return TOKEN(FOR);    }
{IDENT}      { return TOKEN(IDENT);  }
{AFFECT}     { return TOKEN(AFFECT); }
{OPBIN}      { return TOKEN(OPBIN);  }
"("          { return TOKEN(LPAR);   }
")"          { return TOKEN(RPAR);   }
"{"          { return TOKEN(LBRACE); }
"}"          { return TOKEN(RBRACE); }
";"          { return TOKEN(SEMI);   }
","          { return TOKEN(COMMA);  }
"++" | "--"  { return TOKEN(INCREMENT); }
{LITTERAL}   { return TOKEN(LITTERAL); }
{IGNORE}     { }
[^]          { WARN("Unknown caractere : " + yytext()); return TOKEN(UNK); }

Attention aux potentiels « ... » dans le code inséré !

...
init with   {: System.out.println("Début de l'analyse syntaxique."); :}
...
...
action code {: void DEBUG(String s) {System.out.println(s);} :}

terminal TYPE, IDENT, SEMI, UNK;
nonterminal programme, declaration;

terminal LPAR, RPAR, LBRACE, RBRACE;
terminal LITTERAL, AFFECT, OPBIN;
terminal WHILE;
nonterminal bloc, list_instr, instr;
nonterminal instr_while, expr;

terminal COMMA, INCREMENT, IF, ELSE, FOR;
nonterminal list_var, var_dec, formal, params;
nonterminal instr_if, instr_for;

precedence left OPBIN;
precedence nonassoc ELSE;

programme ::= /* vide */
          | programme declaration {: :}
;
declaration ::= TYPE list_var SEMI                {: DEBUG("variables"); :}  
            |   TYPE IDENT LPAR formal RPAR bloc  {: DEBUG("fonction"); :}    
            |   TYPE IDENT LPAR RPAR bloc         {: DEBUG("fonction0"); :}    
;
list_var ::= var_dec
         | list_var COMMA var_dec
; 
var_dec ::= IDENT | IDENT AFFECT expr
;
formal ::= TYPE IDENT
       | formal COMMA TYPE IDENT
;
bloc ::= LBRACE list_instr RBRACE {: DEBUG("bloc"); :} 
;
list_instr ::= /* vide */
         | list_instr instr {: DEBUG("instruction"); :}
;
instr ::= bloc
      | SEMI
      | expr SEMI
      | instr_while
      | instr_if
      | instr_for
;
expr ::= LITTERAL
     | IDENT
     | expr OPBIN expr
     | LPAR expr RPAR
     | IDENT AFFECT expr
     | IDENT LPAR params RPAR
     | IDENT LPAR RPAR
     | IDENT INCREMENT
;
params ::= expr
       | params COMMA expr
; 
instr_while ::= WHILE LPAR expr RPAR instr  {: DEBUG("while"); :} 
;
instr_if ::= IF LPAR expr RPAR instr
                  {: DEBUG("if"); :}
          |  IF LPAR expr RPAR instr ELSE instr
                  {: DEBUG("ifelse"); :} 
;
instr_for ::= FOR LPAR expr SEMI expr SEMI expr RPAR instr
                  {: DEBUG("for"); :} 
;
...

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup2, que l'on importe dans son IDE (Eclipse).

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.

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include
%caseless

%%
Ga      { ECHO(); return TOKEN(GA);  }
Bu      { ECHO(); return TOKEN(BU);  }
Meu     { ECHO(); return TOKEN(MEU); }
Zo      { ECHO(); return TOKEN(ZO);  }
\R      { return TOKEN(EOF); } /* pour ceux qui ne pratiquent pas le ctrl-d ! */
[^]     { WARN("Unknown caractere : " + yytext()); return TOKEN(error); }

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.out.println("GaBuZoMeu (Langage de Dyck)"); :}
...
...
terminal GA, BU, ZO, MEU;
nonterminal exp;

exp  ::= /* mot vide */
     | exp GA exp MEU 
     | exp BU exp ZO
;
...

MeuMeu ligne à ligne (Bonus)

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

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

exo2b_gabuzomeu_dyck.txt

Les deux spécifications :

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include
%caseless

%%
Ga      { return TOKEN(GA);  }
Meu     { return TOKEN(MEU); }
Bu      { return TOKEN(BU);  }
Zo      { return TOKEN(ZO);  }
"//".*  { }
\R      { return TOKEN(NL); }
[^]     {WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.out.println("GaBuZoMeu ligne a ligne"); :}
...
...
terminal GA, BU, ZO, MEU;
terminal NL;
nonterminal ligne, exp;

ligne ::= /* mot vide */  {: :}
      | ligne exp   {: System.out.println(" Syntaxe OK"); :}
                 NL
      | ligne error {: Compiler.incrementFailures(); System.out.println(" Syntaxe BAD"); :}
                 NL
;        
exp  ::= /* mot vide */
     | exp GA exp MEU 
     | exp BU exp ZO
;
...

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.

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 tous les langages algébriques.
Soit D_n, le langage de Dyck sur n paires de parenthèses, on a les énoncés équivalents du théorème de Chomsky-Schützenberger :

D₂ est un générateur du « cône rationnel » des langages algébriques.
Tout langage algébrique est une « transduction rationnelle » du langage D₂.
Tout langage algébrique L est une image homomorphe de l'intersection d'un langage rationnel K et d'un langage de Dyck D_n
L = h(K ∩ D_n) 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 D₂
L = h(K ∩ g^-1 (D₂)) avec h et g morphismes alphabétiques.

La moyenne selon Turing

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup3, que l'on importe dans son IDE (Eclipse).

IMFO la moyenne !

Sur l'alphabet $Σ={a,b}$ , on considère le langage

L = { a

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

Prouver que ce langage est algébrique déterministe (Oups ! de la théorie !).

En pratique, construire une spécification CUP sans conflits qui reconnaît ce langage. Le langage est alors algébrique puisque décrit par une grammaire algébrique, et déterministe puisque reconnaissable sans conflits par CUP.

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

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

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

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

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

N

sur un alphabet de taille

M

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

moyenne.jflex

moyenne.cup

cf. question suivante.

Optionnel

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$

cf. question suivante.

Du rêve

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

À venir

Grammaires de liste

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

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup4, que l'on importe dans son IDE (Eclipse).

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

Voici la proposition pour lista :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, lista;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= lista ;

lista  ::= ENTIER:n     {:  PRN(n); :}
       | lista ENTIER:n {:  PRN(n); :}
;
...

Pour une entrée 0 1 2 3, on a l'exécution suivante :

0 1 2 3 OK

Voici la proposition pour listb :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listb;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listb ;

listb  ::= ENTIER:n     {:  PRN(n); :}
       | ENTIER:n listb {:  PRN(n); :}
;
...

Pour une entrée 0 1 2 3, on a l'exécution suivante :

3 2 1 0 OK

Voici la proposition pour listc :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listc;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listc ;

listc  ::= /* vide */   {:  PRN();  :}
       | listc ENTIER:n {:  PRN(n); :} 
;
...

Pour une entrée 0 1 2 3, on a l'exécution suivante :

vide 0 1 2 3 OK

Voici la proposition pour listd :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listd;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listd ;

listd  ::= /* vide */   {:  PRN();  :}
       | ENTIER:n listd {:  PRN(n); :}
;
...

Pour une entrée 0 1 2 3, on a l'exécution suivante :

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   
;

Voici la proposition pour listf :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listf;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listf ;

listf  ::= ENTIER:n           {:  PRN(n); :}
       | listf COMMA ENTIER:n {:  PRN(n); :}
;
...

Voici la proposition pour listg :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listg;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listg ;

listg  ::= ENTIER:n           {:  PRN(n); :}  
       | ENTIER:n COMMA listg {:  PRN(n); :}  
;
...

Voici la proposition pour listh :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listf, listh;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listh ;

listh  ::= /* vide */  |   listf ;

listf  ::= ENTIER:n           {:  PRN(n); :}
       | listf COMMA ENTIER:n {:  PRN(n); :}
;
...

Voici la proposition pour listi :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listg, listi;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listi ;

listi  ::= /* vide */  |   listg ;

listg  ::= ENTIER:n           {:  PRN(n); :}  
       | ENTIER:n COMMA listg {:  PRN(n); :}  
;
...

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

Voici la proposition pour listj :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listj;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listj ;

listj  ::= /* vide */         {:  PRN();  :}  
       | listj ENTIER:n SEMI  {:  PRN(n); :}  
;
...

Voici la proposition pour listk :

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.err.println("Grammaires de Liste"); :}
...
...
action code {:
       void PRN(int n) {  System.out.print(n+" "); }   
       void PRN()      {  System.out.print(" vide "); }
:}

terminal NL,COMMA, SEMI;
terminal Integer ENTIER;
nonterminal lines, list, listk;

lines ::= /* vide */
      | lines list  {: System.out.println("OK");  :}  NL
      | lines error {: System.out.println("BAD"); Compiler.incrementFailures(); :}  NL
;

list ::= listk ;

listk  ::= /* vide */         {:  PRN();  :}  
       | ENTIER:n SEMI listk  {:  PRN(n); :}  
;
...

Analyse Syntaxique de JSON

[Lire la section 7 du mémento CUP]

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup5, que l'on importe dans son IDE (Eclipse).

Le langage JSON

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

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

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

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

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

Quelques exemples d'objets JSON

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

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

Spécification JSON

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

JSON-RFC

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

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

Analyseur Syntaxique

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

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

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

PrettyPrinter

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

On pourra par étape :

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

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

JSON-EX.json

pourra donner une sortie plutôt Pretty :

JSON-EX.resu

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

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

Calculatrice sans ambiguïté

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

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup6, que l'on importe dans son IDE (Eclipse).

É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,
- (optionnel) 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 ')';. (Dans l'exercice suivant, la discussion discutera de l'ambiguïté introduite par cette règle sans les parenthèses.)

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

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
[-+*/%]  { return TOKEN(OPBIN,yytext().charAt(0)); }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.out.println("Calculatrice non ambiguë"); prompt(); :}
parser code {:
...
...
  static void prompt() { System.out.print("> "); }

  static int eval( Integer e1, Character op, Integer e2) {
    switch (op) {
      case '+' : return e1 + e2;
      case '-' : return e1 - e2;
      case '*' : return e1 * e2;
      case '/' : return e1 / e2;
      case '%' : return e1 % e2;
      default : System.out.println("Operateur inconnu :" +op); Compiler.incrementFailures(); return 0;
    }
  }
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal Integer ENTIER;
terminal Character OPBIN;

nonterminal lignes, ligne;
nonterminal Integer expr, args;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println(" = " + e); :}
       |   /* vide */   {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
expr   ::= ENTIER:e              {: RESULT = e; :}
       |   LPAR expr:e RPAR      {: RESULT = e; :}
       |   LPAR expr:e1 OPBIN:op expr:e2 RPAR
                                 {: RESULT = eval(e1, op, e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = (e1>e2)?e2:e1; :} 
       |   FMAX LPAR args:e RPAR {: RESULT = e; :}
;
args   ::= expr:e                {: RESULT = e; :}
       |   args:e1 COMMA expr:e2 {: RESULT = (e1>e2)?e1:e2; :}
;
...

Calculatrice avec priorité

[Lire la section 8 du mémento CUP]

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup7, que l'on importe dans son IDE (Eclipse).

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 :

calc1.data

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
"+"      { return TOKEN(PLUS);  }
"-"      { return TOKEN(MOINS); }
"*"      { return TOKEN(MULT);  }
"/"      { return TOKEN(DIV);   }
"%"      { return TOKEN(MOD);   }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.out.println("Calculatrice avec priorité");  prompt(); :}

parser code {:
...
...
  static void prompt() { System.out.print("> "); }
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal Integer ENTIER;

nonterminal lignes, ligne;
nonterminal Integer expr, args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println(" = " + e); :}
       |   /* vide*/    {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
expr   ::= ENTIER:e              {: RESULT = e; :}
       |   LPAR expr:e RPAR      {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = e1 + e2; :}
       |   expr:e1 MOINS expr:e2 {: RESULT = e1 - e2; :}
       |   expr:e1 MULT expr:e2  {: RESULT = e1 * e2; :}
       |   expr:e1 DIV expr:e2   {: RESULT = e1 / e2; :}
       |   expr:e1 MOD expr:e2   {: RESULT = e1 % e2; :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = (e1>e2)?e2:e1; :} 
       |   FMAX LPAR args:e RPAR {: RESULT = e; :}
;
args   ::= expr:e                {: RESULT = e; :}
       |   args:e1 COMMA expr:e2 {: RESULT = (e1>e2)?e1:e2; :}
;
...

Calculer avec des réels (optionnel, 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, etc ?
...

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ègles dans la grammaire (croissance quadratique) ; on considère donc que c'est 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 valide 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 :
Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter %% %include Jflex.include %include JflexCup.include IGNORE = [ \t\f] | "#" .* | "//" .* DIGIT = [0-9] %% {DIGIT}+ { return TOKEN(ENTIER,Integer.decode(yytext())); } {DIGIT}+\.{DIGIT}* | {DIGIT}*\.{DIGIT}+ { return TOKEN(DOUBLE,Double.parseDouble(yytext())); } "+" { return TOKEN(PLUS); } "-" { return TOKEN(MOINS); } "*" { return TOKEN(MULT); } "/" { return TOKEN(DIV); } "%" { return TOKEN(MOD); } "(" { return TOKEN(LPAR); } ")" { return TOKEN(RPAR); } "," { return TOKEN(COMMA); } "min" { return TOKEN(FMIN); } "max" { return TOKEN(FMAX); } \R { return TOKEN(NL); } {IGNORE} { } [^] { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

... init with {: System.out.println("Calculatrice avec priorité et flottants"); prompt(); :} parser code {: ... ... static void prompt() { System.out.print("> "); } :} terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX; terminal PLUS, MOINS, MULT, DIV, MOD; terminal Integer ENTIER; terminal Double DOUBLE; nonterminal lignes, ligne; nonterminal Double expr, args; precedence left PLUS,MOINS; precedence left MULT,DIV,MOD; lignes ::= /* vide */ {: :} | lignes ligne {: prompt(); :} NL ; ligne ::= expr:e {: System.out.println(" = " + e); :} | /* vide*/ {: :} | error {: Compiler.incrementFailures(); :} ; expr ::= ENTIER:e {: RESULT = Double.valueOf(e); :} | DOUBLE:e {: RESULT = e; :} | LPAR expr:e RPAR {: RESULT = e; :} | expr:e1 PLUS expr:e2 {: RESULT = e1 + e2; :} | expr:e1 MOINS expr:e2 {: RESULT = e1 - e2; :} | expr:e1 MULT expr:e2 {: RESULT = e1 * e2; :} | expr:e1 DIV expr:e2 {: RESULT = e1 / e2; :} | ENTIER:e1 MOD ENTIER:e2 {: RESULT = Double.valueOf(e1 % e2); :} | FMIN LPAR expr:e1 COMMA expr:e2 RPAR {: RESULT = (e1>e2)?e2:e1; :} | FMAX LPAR args:e RPAR {: RESULT = e; :} ; args ::= expr:e {: RESULT = e; :} | args:e1 COMMA expr:e2 {: RESULT = (e1>e2)?e1:e2; :} ; ...

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éclaration de variable (uniquement des affectations et des utilisations) ;
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) ». Donc, 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 :

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é, etc.

En JAVA, on peut réaliser rapidement une table de symboles simple en utilisant la classe java.util.HashMap<K,V> . Voici l'utilisation de HashMap pour une table de symboles avec la possibilité d'écrire « symTab.put(v,e); », « symTabGet(v); », « symTab.remove(v); », « symTab.clear(); » dans les actions des règles :

parser code {:
  static void prompt() { System.out.print("> "); }

// Table de symboles (static et classe parser pour visibilité)
  public static java.util.Map<String, Integer> symTab = new java.util.HashMap() ;

// Gestion des variables non initialisées
  public static Integer symTabGet(String v) {
    Integer val = symTab.get(v);
    if (val!=null) return val ;
    System.out.println("Warning : " + v + " non initialisé");
    Compiler.incrementFailures();
    symTab.put(v,0);  // initialisation implicite 
    return 0;
  }
:}

Une spécification JFlex, puis une spécification CUP (avec table de symbole dans la spécification) :

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
IDENT = [:jletter:] [:jletterdigit:]*
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
"+"      { return TOKEN(PLUS);  }
"-"      { return TOKEN(MOINS); }
"*"      { return TOKEN(MULT);  }
"/"      { return TOKEN(DIV);   }
"%"      { return TOKEN(MOD);   }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
"clean"  |
"clear"  { return TOKEN(CLEAR); }
"="      { return TOKEN(AFFECT); }
{IDENT}  { return TOKEN(VAR, yytext()); }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

...
init with {: System.out.println("Calculatrice avec priorité et variables"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }

// Table de symboles (static et classe parser pour visibilité)
  public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;

// Gestion des variables non initialisées
  public static Integer symTabGet(String v) {
    Integer val = symTab.get(v);
    if (val!=null) return val ;
    System.out.println("Warning : " + v + " non initialisé");
    Compiler.incrementFailures();
    symTab.put(v,0);  // initialisation implicite 
    return 0;
  }
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;

nonterminal lignes, ligne, inst;
nonterminal Integer expr, args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println(" = " + e); :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = e; :}
       |   LPAR expr:e RPAR      {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = e1 + e2; :}
       |   expr:e1 MOINS expr:e2 {: RESULT = e1 - e2; :}
       |   expr:e1 MULT expr:e2  {: RESULT = e1 * e2; :}
       |   expr:e1 DIV expr:e2   {: RESULT = e1 / e2; :}
       |   expr:e1 MOD expr:e2   {: RESULT = e1 % e2; :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = (e1>e2)?e2:e1; :} 
       |   FMAX LPAR args:e RPAR {: RESULT = e; :}
       |   VAR:v AFFECT expr:e   {: RESULT = e; symTab.put(v,e); :}
       |   VAR:v                 {: RESULT = symTabGet(v); :}
;
args   ::= expr:e                {: RESULT = e; :}
       |   args:e1 COMMA expr:e2 {: RESULT = (e1>e2)?e1:e2; :}
;
...

Pour aller plus loin (optionnel)

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup8, que l'on importe dans son IDE (Eclipse).

Pour aller plus loin avec la calculatrice, il devient vite utile ou nécessaire de construire explicitement l'Arbre de Syntaxe Abstrait. 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, etc. ;
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 abstrait en utilisant les classes JAVA suivantes :

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

Il est utile de lire le source de ces classes ou le JavaDoc, pour en faire une bonne utilisation.

Préparation

Recupérer les classes pré-cités dans le nouveau projet.

Recopier les spécifications finales de la calculatrice de l'exercice précèdent.

Cet exercice et l'exercice suivant peuvent être longs et parfois répétitifs. 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 Concret/Complet : Concrete Syntax Tree

Dans cette question et la suivante, notre calculatrice ne fait que « dessiner des arbres, c'est-à-dire sans calcul (des valeurs des expressions). 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"),...); :}

Voici un exemple de résultat :

calcCST.out

La spécification lexicale est la même que pour l'exercice précédent :

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
IDENT = [:jletter:] [:jletterdigit:]*
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
"+"      { return TOKEN(PLUS);  }
"-"      { return TOKEN(MOINS); }
"*"      { return TOKEN(MULT);  }
"/"      { return TOKEN(DIV);   }
"%"      { return TOKEN(MOD);   }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
"clean"  |
"clear"  { return TOKEN(CLEAR); }
"="      { return TOKEN(AFFECT); }
{IDENT}  { return TOKEN(VAR, yytext()); }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

La spécification syntaxique avec les nouvelles actions sémantiques et l'impression des CST :

Attention aux potentiels « ... » dans le code inséré !

...
package compil;
import ast.exo8.*;

init with {: System.out.println("Calculatrice et arbre CST");  prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }

// Table de symboles (static et classe parser pour visibilité)
  public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
  public static Integer symTabGet(String v) {
    Integer val = symTab.get(v);
    if (val!=null) return val ;
    System.out.println("Warning : " + v + " non initialisé");
    symTab.put(v,0);  // initialisation implicite 
    return 0;
  }
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;

nonterminal lignes, ligne, inst;
nonterminal Ast expr, args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println(e.toPrint()); :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new Ast("Litteral", new Ast("ENTIER")); :}
       |   LPAR expr:e RPAR      {: RESULT = new Ast("Par", new Ast("LPAR"), e, new Ast("RPAR")); :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new Ast("Plus", e1, new Ast("PLUS"), e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new Ast("Moins", e1, new Ast("MOINS"), e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new Ast("Mult", e1, new Ast("MULT"), e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new Ast("Div", e1, new Ast("DIV"), e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new Ast("Mod", e1, new Ast("MOD"), e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new Ast("Min", new Ast("FMIN"), new Ast("LPAR"),
                                                 e1, new Ast("COMMA"), e2, new Ast("RPAR")); :} 
       |   FMAX LPAR args:e RPAR {: RESULT = new Ast("Max", new Ast("FMAX"), new Ast("LPAR"), e, new Ast("RPAR")); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new Ast("Aff", new Ast("VAR"), new Ast("AFFECT"), e); :}
       |   VAR:v                 {: RESULT = new Ast("Var", new Ast("VAR")); :}
;
args   ::= expr:e                {: RESULT = new Ast("Arg", e) ; :}
       |   args:e1 COMMA expr:e2 {: RESULT = new Ast("Arglist", e1, new Ast("COMMA"), e2); :}
;
...

Arbre de Syntaxe Réduit/Abstrait : 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 (liste de nœuds homogènes, cf. classe AstList ci-après) ;
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 est donc 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 le paquetage compil.ast des classes JAVA qui héritent directement ou indirectement de la classe AstNode ;
adapter la calculatrice pour construire, dans les actions sémantiques, l'AST en utilisant ces nouveaux types de nœuds ;
imprimer l'AST 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.

Pour ce faire, remarquer qu'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 de conception Visiteur, et on utilise une méthode « vide&nbps;>, c'est-à-dire 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() 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() !)

Plus précisément, pour l'AST de la grammaire de la calculatrice :

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 + ")"; } }
Autre 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.
Puis, 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).

Voici un exemple de résultat :

calcAST.out

La spécification lexicale est inchangée.
La spécification syntaxique est adaptée en utilisant les nouveaux nœuds de l'AST :

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo8.*;
import ast.exo8.exo8c.*;

init with {: System.out.println("Calculatrice et AST de base"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
  
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println(e.toPrint()); :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new ExpEntier(e); :}
       |   LPAR  expr:e RPAR     {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new ExpOpBin(e1, '+',  e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new ExpOpBin(e1, '-',  e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new ExpOpBin(e1, '*',  e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new ExpOpBin(e1, '/',  e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new ExpOpBin(e1, '%',  e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new ExpFmin(e1, e2); :} 
       |   FMAX LPAR args:l RPAR {: RESULT = new ExpFmax(l); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new ExpAff(new ExpVar(v), e); :}
       |   VAR:v                 {: RESULT = new ExpVar(v); :}
;
args   ::= expr:e                {: RESULT = new AstList<Exp>(); RESULT.add(e); :}
       |   args:e1 COMMA expr:e2 {: RESULT = e1; RESULT.add(e2); :}
;

Et les nœuds de l'AST src/Exp*.java :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

import ast.exo8.AstNode;
import ast.exo8.AstVisitor;

/**
 * Expressions, classe abstraite pour Exp*.
 */
public abstract class Exp extends AstNode {
	Exp(AstNode... enfants) {
		super(enfants);
	}

	public void accept(AstVisitor v) {
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

/**
 * 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;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

/**
 * Constante entière.
 */
public class ExpEntier extends Exp {
	public Integer value;

	public ExpEntier(Integer value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + value.toString() + ")";
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

import ast.exo8.AstList;

/**
 * Fonction maximum, max( AstList<Exp> )
 */
public class ExpFmax extends Exp {
	public AstList<Exp> args;

	public ExpFmax(AstList<Exp> args) {
		super(args);
		this.args = args;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

/**
 * Fonction minimum, min( Exp, Exp).
 */
public class ExpFmin extends Exp {
	public Exp e1, e2;

	public ExpFmin(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

/**
 * Opération binaire, Exp char Exp.
 */
public class ExpOpBin extends Exp {
	public Exp e1, e2;
	public char op;

	public ExpOpBin(Exp e1, char op, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.op = op;
		this.e2 = e2;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + op + ")";
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8c; // nom du paquetage à adapter

/**
 * Nom de variable.
 */
public class ExpVar extends Exp {
	public String name;

	public ExpVar(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + name + ")";
	}
}

É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 enfants et de la nature du nœud ;
modifier la spécification pour appeler la méthode eval() pour chaque AST correct, c'est-à-dire chaque ligne correcte.

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 Exp*.java) est à suivre dans la question suivante.
Voici le fichier CUP :

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo8.*;
import ast.exo8.exo8d.*;

init with {: System.out.println("Calculatrice et AST de base"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
  
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println("AST Eval=" + e.eval()); 
                           System.out.println(e.toPrint());            :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new ExpEntier(e); :}
       |   LPAR  expr:e RPAR     {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new ExpOpBin(e1, '+',  e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new ExpOpBin(e1, '-',  e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new ExpOpBin(e1, '*',  e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new ExpOpBin(e1, '/',  e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new ExpOpBin(e1, '%',  e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new ExpFmin(e1, e2); :} 
       |   FMAX LPAR args:l RPAR {: RESULT = new ExpFmax(l); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new ExpAff(new ExpVar(v), e); :}
       |   VAR:v                 {: RESULT = new ExpVar(v); :}
;
args   ::= expr:e                {: RESULT = new AstList<Exp>(); RESULT.add(e); :}
       |   args:e1 COMMA expr:e2 {: RESULT = e1; RESULT.add(e2); :}
;

Et voici les fichiers JAVA des nœuds de l'AST Exp*.java :

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

import ast.exo8.AstNode;
import ast.exo8.AstVisitor;

/**
 * Expressions, classe abstraite pour Exp*.
 */
public abstract class Exp extends AstNode {
	Exp(AstNode... enfants) {
		super(enfants);
	}

	public abstract Integer eval();

	public void accept(AstVisitor v) {
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

import compil.parser;

/**
 * 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;
	}

	@Override
	public Integer eval() {
		Integer res = e.eval();
		parser.symTab.put(v.name, res);
		return res;
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

/**
 * Constante entière.
 */
public class ExpEntier extends Exp {
	public Integer value;

	public ExpEntier(Integer value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + value.toString() + ")";
	}

	@Override
	public Integer eval() {
		return value;
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

import ast.exo8.AstList;
import ast.exo8.AstNode;

/**
 * Fonction maximum, max( AstList<Exp> )
 */
public class ExpFmax extends Exp {
	public AstList<Exp> args;

	public ExpFmax(AstList<Exp> args) {
		super(args);
		this.args = args;
	}

	@Override
	public Integer eval() {
		Integer res = Integer.MIN_VALUE;
		Integer v;
		for (AstNode e : args) {
			v = ((Exp) e).eval();
			if (v > res)
				res = v;
		}
		return res;
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

/**
 * Fonction minimum, min( Exp, Exp).
 */
public class ExpFmin extends Exp {
	public Exp e1, e2;

	public ExpFmin(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		return (i1 < i2) ? i1 : i2;
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

/**
 * Opération binaire, Exp char Exp.
 */
public class ExpOpBin extends Exp {
	public Exp e1, e2;
	public char op;

	public ExpOpBin(Exp e1, char op, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.op = op;
		this.e2 = e2;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + op + ")";
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		switch (op) {
		case '+':
			return i1 + i2;
		case '-':
			return i1 - i2;
		case '*':
			return i1 * i2;
		case '/':
			return i1 / i2;
		case '%':
			return i1 % i2;
		}
		return 0;
	}
}
...

Attention aux potentiels « ... » dans le code inséré !

...
package ast.exo8.exo8d; // nom du paquetage à adapter

import compil.parser;

/**
 * Nom de variable.
 */
public class ExpVar extends Exp {
	public String name;

	public ExpVar(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + name + ")";
	}

	@Override
	public Integer eval() {
		return parser.symTabGet(name);
	}
}
...

Boucler la boucle (optionnel)

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

Voici les fichiers JFlex et CUP :

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
IDENT = [:jletter:] [:jletterdigit:]*
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
"+"      { return TOKEN(PLUS);  }
"-"      { return TOKEN(MOINS); }
"*"      { return TOKEN(MULT);  }
"/"      { return TOKEN(DIV);   }
"%"      { return TOKEN(MOD);   }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
"while"  { return TOKEN(WHILE); }
"clean"  |
"clear"  { return TOKEN(CLEAR); }
"="      { return TOKEN(AFFECT); }
{IDENT}  { return TOKEN(VAR, yytext()); }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo8.*;
import ast.exo8.exo8e.*;

init with {: System.out.println("Calculatrice et AST de base"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
  
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;
terminal WHILE;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println("AST Eval=" + e.eval()); 
                           System.out.println(e.toPrint());            :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new ExpEntier(e); :}
       |   LPAR  expr:e RPAR     {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new ExpOpBin(e1, '+',  e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new ExpOpBin(e1, '-',  e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new ExpOpBin(e1, '*',  e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new ExpOpBin(e1, '/',  e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new ExpOpBin(e1, '%',  e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new ExpFmin(e1, e2); :} 
       |   FMAX LPAR args:l RPAR {: RESULT = new ExpFmax(l); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new ExpAff(new ExpVar(v), e); :}
       |   VAR:v                 {: RESULT = new ExpVar(v); :}
       |   WHILE expr:e1 expr:e2 {: RESULT = new ExpWhile(e1, e2); :}
;
args   ::= expr:e                {: RESULT = new AstList<Exp>(); RESULT.add(e); :}
       |   args:e1 COMMA expr:e2 {: RESULT = e1; RESULT.add(e2); :}
;

Et voici le fichier JAVA du nouveau type de nœud ExpWhile de l'AST :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8e; // nom du paquetage à adapter

/**
 * Boucle while, while ( Exp !=0) { Exp }.
 */
public class ExpWhile extends Exp {
	public Exp e1, e2;

	public ExpWhile(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	public Integer eval() {
		Integer res = -1;
		while (e1.eval() != 0) {
			res = e2.eval();
		}
		return res;
	}
}

Boucle (optionnel, 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 :

Attention aux potentiels « ... » dans le code inséré !

package compil; // nom du paquetage à adapter
%%
%include Jflex.include
%include JflexCup.include

IGNORE = [ \t\f] |  "#" .* | "//" .*
NUMBER = [0-9]+ | 0[x|X][0-9a-fA-F]+
IDENT = [:jletter:] [:jletterdigit:]*
%%
{NUMBER} { return TOKEN(ENTIER,Integer.decode(yytext())); }
"+"      { return TOKEN(PLUS);  }
"-"      { return TOKEN(MOINS); }
"*"      { return TOKEN(MULT);  }
"/"      { return TOKEN(DIV);   }
"%"      { return TOKEN(MOD);   }
"("      { return TOKEN(LPAR);  }
")"      { return TOKEN(RPAR);  }
","      { return TOKEN(COMMA); }
"min"    { return TOKEN(FMIN);  }
"max"    { return TOKEN(FMAX);  }
"while"  { return TOKEN(WHILE); }
"for"    { return TOKEN(FOR); }
"clean"  |
"clear"  { return TOKEN(CLEAR); }
"="      { return TOKEN(AFFECT); }
{IDENT}  { return TOKEN(VAR, yytext()); }
\R       { return TOKEN(NL);    }
{IGNORE} { }
[^]      { WARN("Unknown caractere : " + yytext()); return ERROR(); }

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo8.*;
import ast.exo8.exo8f.*;

init with {: System.out.println("Calculatrice et AST de base"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
  
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;
terminal FOR, WHILE;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e       {: System.out.println("AST Eval=" + e.eval()); 
                           System.out.println(e.toPrint());            :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new ExpEntier(e); :}
       |   LPAR  expr:e RPAR     {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new ExpOpBin(e1, '+',  e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new ExpOpBin(e1, '-',  e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new ExpOpBin(e1, '*',  e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new ExpOpBin(e1, '/',  e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new ExpOpBin(e1, '%',  e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new ExpFmin(e1, e2); :} 
       |   FMAX LPAR args:l RPAR {: RESULT = new ExpFmax(l); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new ExpAff(new ExpVar(v), e); :}
       |   VAR:v                 {: RESULT = new ExpVar(v); :}
       |   WHILE expr:e1 expr:e2 {: RESULT = new ExpWhile(e1, e2); :}
       |   FOR VAR:v ENTIER:n expr:e
                                 {: RESULT = new ExpFor(new ExpVar(v), new ExpEntier(n), e); :}
;
args   ::= expr:e                {: RESULT = new AstList<Exp>(); RESULT.add(e); :}
       |   args:e1 COMMA expr:e2 {: RESULT = e1; RESULT.add(e2); :}
;

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

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

import ast.exo8.AstNode;
import ast.exo8.AstVisitor;

/**
 * Expressions, classe abstraite pour Exp*.
 */
public abstract class Exp extends AstNode {
	Exp(AstNode... enfants) {
		super(enfants);
	}

	public abstract Integer eval();

	public void accept(AstVisitor v) {
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

import compil.parser;

/**
 * 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;
	}

	@Override
	public Integer eval() {
		Integer res = e.eval();
		parser.symTab.put(v.name, res);
		return res;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

/**
 * Constante entière.
 */
public class ExpEntier extends Exp {
	public Integer value;

	public ExpEntier(Integer value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + value.toString() + ")";
	}

	@Override
	public Integer eval() {
		return value;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

import ast.exo8.AstList;
import ast.exo8.AstNode;

/**
 * Fonction maximum, max( AstList<Exp> )
 */
public class ExpFmax extends Exp {
	public AstList<Exp> args;

	public ExpFmax(AstList<Exp> args) {
		super(args);
		this.args = args;
	}

	@Override
	public Integer eval() {
		Integer res = Integer.MIN_VALUE;
		Integer v;
		for (AstNode e : args) {
			v = ((Exp) e).eval();
			if (v > res)
				res = v;
		}
		return res;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

/**
 * Fonction minimum, min( Exp, Exp).
 */
public class ExpFmin extends Exp {
	public Exp e1, e2;

	public ExpFmin(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		return (i1 < i2) ? i1 : i2;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

/**
 * Opération binaire, Exp char Exp.
 */
public class ExpOpBin extends Exp {
	public Exp e1, e2;
	public char op;

	public ExpOpBin(Exp e1, char op, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.op = op;
		this.e2 = e2;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + op + ")";
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		switch (op) {
		case '+':
			return i1 + i2;
		case '-':
			return i1 - i2;
		case '*':
			return i1 * i2;
		case '/':
			return i1 / i2;
		case '%':
			return i1 % i2;
		}
		return 0;
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8d; // nom du paquetage à adapter

import compil.parser;

/**
 * Nom de variable.
 */
public class ExpVar extends Exp {
	public String name;

	public ExpVar(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + name + ")";
	}

	@Override
	public Integer eval() {
		return parser.symTabGet(name);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

import compil.parser;

/**
 * Boucle for, for ( Integer v =1 ; v<=n; v++) { e }.
 */
public class ExpFor extends Exp {
	public ExpVar v;
	public ExpEntier n;
	public Exp e;

	public ExpFor(ExpVar v, ExpEntier n, Exp e) {
		super(v, n, e);
		this.v = v;
		this.n = n;
		this.e = e;
	}

	public Integer eval() {
		for (int i = 1; i <= n.eval(); i++) {
			parser.symTab.put(v.name, i);
			e.eval();
		}
		return v.eval();
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo8.exo8f; // nom du paquetage à adapter

/**
 * Boucle while, while ( Exp !=0) { Exp }.
 */
public class ExpWhile extends Exp {
	public Exp e1, e2;

	public ExpWhile(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	public Integer eval() {
		Integer res = -1;
		while (e1.eval() != 0) {
			res = e2.eval();
		}
		return res;
	}
}

Retour aux sources (optionnel)

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

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

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

Un exemple de résultat :

calcASTeval_loc.out

La spécification CUP précédente, complétée avec la gestion (presque complète) des localisations dans le source :

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo8.*;
import ast.exo8.exo8f.*;
init with {: System.out.println("Calculatrice avec évaluation sur AST (et location)"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;
terminal WHILE, FOR;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e        {:
                  System.out.println("AST Eval=" + e.eval()); 
                  System.out.println(e.toPrint());
                         :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e               {: RESULT = new ExpEntier(e);
                                     RESULT.addPosition(exleft, exright); :}
       |   LPAR:aa expr:e RPAR:zz {: RESULT = e ;
                                     RESULT.addPosition(aaxleft,zzxright); :}
       |   expr:e1 PLUS expr:e2   {: RESULT = new ExpOpBin(e1 , '+',  e2); 
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MOINS expr:e2  {: RESULT = new ExpOpBin(e1 , '-',  e2); 
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MULT expr:e2   {: RESULT = new ExpOpBin(e1, '*',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 DIV expr:e2    {: RESULT = new ExpOpBin(e1 , '/',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MOD expr:e2    {: RESULT = new ExpOpBin(e1, '%',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   FMIN:aa LPAR expr:e1 COMMA expr:e2 RPAR:zz
                                  {: RESULT = new ExpFmin(e1,e2);
                                     RESULT.addPosition(aaxleft, zzxright); :} 
       |   FMAX:aa LPAR args:l RPAR:zz
                                  {: RESULT = new ExpFmax(l); 
                                     RESULT.addPosition(aaxleft, zzxright); :} 
       |   VAR:v AFFECT expr:e    {: RESULT = new ExpAff(new ExpVar(v), e); 
                                     RESULT.addPosition(vxleft, exright); :}
       |   VAR:v                  {: RESULT = new ExpVar(v); 
                                     RESULT.addPosition(vxleft, vxright); :}
       |   WHILE:aa expr:e1 expr:e2
                                  {: RESULT = new ExpWhile(e1, e2); 
                                     RESULT.addPosition(aaxleft, e2xright); :}
       |   FOR:aa VAR:v ENTIER:n expr:e
                                  {: RESULT=new ExpFor(new ExpVar(v), new ExpEntier(n),e); 
                                     RESULT.addPosition(aaxleft, exright); :}
;
args   ::= expr:e                 {: RESULT = new AstList<Exp>(); RESULT.add(e);
                                     RESULT.addPosition(exleft, exright); :}
       |   args:e1 COMMA expr:e2  {: RESULT = e1; RESULT.add(e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
;

Calculatrice et première visite

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

On commence par créer un nouveau projet Maven JFlex+CUP en exécutant la commande compil-nouveau-cup-jflex exocup9, que l'on importe dans son IDE (Eclipse).

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.

L'interface AstVisitor, et le visiteur par défaut AstVisitorDefault :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import ast.exo9.Ast;
import ast.exo9.AstList;
import ast.exo9.AstNode;

/**
 * Interface Visiteur pour l'AST Minijava.
 */
public interface AstVisitor {
	/**
	 * Visite une liste de nœuds homogénes.
	 * 
	 * @param <T> le type commun des enfants.
	 * @param n   le nœud visité.
	 */
	<T extends AstNode> void visit(AstList<T> n);

	/**
	 * Visite Ast générique.
	 * 
	 * @param n Le nœud visité
	 */
	void visit(Ast n);

	// AST calculette
	void visit(ExpAff n);

	void visit(ExpEntier n);

	void visit(ExpFor n);

	void visit(ExpFmax n);

	void visit(ExpFmin n);

	void visit(ExpOpBin n);

	void visit(ExpVar n);

	void visit(ExpWhile n);
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import ast.exo9.Ast;
import ast.exo9.AstList;
import ast.exo9.AstNode;

/**
 * Visiteur générique de l'AST avec parcours en profondeur.
 */
public class AstVisitorDefault implements AstVisitor {
	/**
	 * Parcours récursif en profondeur de l'arbre de syntaxe.
	 * 
	 * @param node le nœud à visiter
	 */
	public void defaultVisit(final AstNode node) {
		for (AstNode f : node)
			f.accept(this);
	}

	// Liste homogène
	public <T extends AstNode> void visit(final AstList<T> n) {
		defaultVisit(n);
	}

	/** Ast générique. */
	public void visit(final Ast n) {
		defaultVisit(n);
	}

	// AST calculette
	public void visit(final ExpAff n) {
		defaultVisit(n);
	}

	public void visit(final ExpFor n) {
		defaultVisit(n);
	}

	public void visit(final ExpEntier n) {
		defaultVisit(n);
	}

	public void visit(final ExpFmax n) {
		defaultVisit(n);
	}

	public void visit(final ExpFmin n) {
		defaultVisit(n);
	}

	public void visit(final ExpOpBin n) {
		defaultVisit(n);
	}

	public void visit(final ExpVar n) {
		defaultVisit(n);
	}

	public void visit(final ExpWhile n) {
		defaultVisit(n);
	}
}

Les classes Exp*.java avec un « vrai » accept() :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import ast.exo9.AstNode;

/**
 * Expressions, classe abstraite pour Exp*.
 */
public abstract class Exp extends AstNode {
	Exp(AstNode... enfants) {
		super(enfants);
	}

	public abstract Integer eval();
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import compil.parser;

/**
 * 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;
	}

	@Override
	public Integer eval() {
		Integer res = e.eval();
		parser.symTab.put(v.name, res);
		return res;
	}

	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

/**
 * Constante entière.
 */
public class ExpEntier extends Exp {
	public Integer value;

	public ExpEntier(Integer value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + value.toString() + ")";
	}

	@Override
	public Integer eval() {
		return value;
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import ast.exo9.AstList;
import ast.exo9.AstNode;

/**
 * Fonction maximum, max( AstList<Exp> )
 */
public class ExpFmax extends Exp {
	public AstList<Exp> args;

	public ExpFmax(AstList<Exp> args) {
		super(args);
		this.args = args;
	}

	@Override
	public Integer eval() {
		Integer res = Integer.MIN_VALUE;
		Integer v;
		for (AstNode e : args) {
			v = ((Exp) e).eval();
			if (v > res) {
				res = v;
			}
		}
		return res;
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

/**
 * Fonction minimum, min( Exp, Exp).
 */
public class ExpFmin extends Exp {
	public Exp e1, e2;

	public ExpFmin(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		return (i1 < i2) ? i1 : i2;
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import compil.parser;

/**
 * Boucle for, for ( Integer v =1 ; v<=n; v++) { e }.
 */
public class ExpFor extends Exp {
	public ExpVar v;
	public ExpEntier n;
	public Exp e;

	public ExpFor(ExpVar v, ExpEntier n, Exp e) {
		super(v, n, e);
		this.v = v;
		this.n = n;
		this.e = e;
	}

	public Integer eval() {
		for (int i = 1; i <= n.eval(); i++) {
			parser.symTab.put(v.name, i);
			e.eval();
		}
		return v.eval();
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

/**
 * Opération binaire, Exp char Exp.
 */
public class ExpOpBin extends Exp {
	public Exp e1, e2;
	public char op;

	public ExpOpBin(Exp e1, char op, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.op = op;
		this.e2 = e2;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + op + ")";
	}

	@Override
	public Integer eval() {
		int i1 = e1.eval();
		int i2 = e2.eval();
		switch (op) {
		case '+':
			return i1 + i2;
		case '-':
			return i1 - i2;
		case '*':
			return i1 * i2;
		case '/':
			return i1 / i2;
		case '%':
			return i1 % i2;
		}
		return 0;
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import compil.parser;

/**
 * Nom de variable.
 */
public class ExpVar extends Exp {
	public String name;

	public ExpVar(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return super.toString() + "(" + name + ")";
	}

	@Override
	public Integer eval() {
		return parser.symTabGet(name);
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

/**
 * Boucle while, while ( Exp !=0) { Exp }.
 */
public class ExpWhile extends Exp {
	public Exp e1, e2;

	public ExpWhile(Exp e1, Exp e2) {
		super(e1, e2);
		this.e1 = e1;
		this.e2 = e2;
	}

	public Integer eval() {
		Integer res = -1;
		while (e1.eval() != 0) {
			res = e2.eval();
		}
		return res;
	}

	@Override
	public void accept(AstVisitor v) {
		v.visit(this);
	}
}

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.

Adaptation de la spécification CUP :

       |  lignes expr:e      {:
                  new Gratos(e);
                  System.out.println("AST Eval=" + e.eval());
                  System.out.println(e.toPrint());
                             :}

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo9.*;
import ast.exo9.exo9b.*;
init with {: System.out.println("Calculatrice avec évaluation sur AST (et location)"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;
terminal WHILE, FOR;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e        {:
                  new Gratos(e);
                  System.out.println("AST Eval=" + e.eval()); 
                  System.out.println(e.toPrint());
                         :}
       |   inst         {: :}
       |   error        {: Compiler.incrementFailures(); :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e               {: RESULT = new ExpEntier(e);
                                     RESULT.addPosition(exleft, exright); :}
       |   LPAR:aa expr:e RPAR:zz {: RESULT = e ;
                                     RESULT.addPosition(aaxleft,zzxright); :}
       |   expr:e1 PLUS expr:e2   {: RESULT = new ExpOpBin(e1 , '+',  e2); 
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MOINS expr:e2  {: RESULT = new ExpOpBin(e1 , '-',  e2); 
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MULT expr:e2   {: RESULT = new ExpOpBin(e1, '*',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 DIV expr:e2    {: RESULT = new ExpOpBin(e1 , '/',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   expr:e1 MOD expr:e2    {: RESULT = new ExpOpBin(e1, '%',  e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
       |   FMIN:aa LPAR expr:e1 COMMA expr:e2 RPAR:zz
                                  {: RESULT = new ExpFmin(e1,e2);
                                     RESULT.addPosition(aaxleft, zzxright); :} 
       |   FMAX:aa LPAR args:l RPAR:zz
                                  {: RESULT = new ExpFmax(l); 
                                     RESULT.addPosition(aaxleft, zzxright); :} 
       |   VAR:v AFFECT expr:e    {: RESULT = new ExpAff(new ExpVar(v), e); 
                                     RESULT.addPosition(vxleft, exright); :}
       |   VAR:v                  {: RESULT = new ExpVar(v); 
                                     RESULT.addPosition(vxleft, vxright); :}
       |   WHILE:aa expr:e1 expr:e2
                                  {: RESULT = new ExpWhile(e1, e2); 
                                     RESULT.addPosition(aaxleft, e2xright); :}
       |   FOR:aa VAR:v ENTIER:n expr:e
                                  {: RESULT=new ExpFor(new ExpVar(v), new ExpEntier(n),e); 
                                     RESULT.addPosition(aaxleft, exright); :}
;
args   ::= expr:e                 {: RESULT = new AstList<Exp>(); RESULT.add(e);
                                     RESULT.addPosition(exleft, exright); :}
       |   args:e1 COMMA expr:e2  {: RESULT = e1; RESULT.add(e2);
                                     RESULT.addPosition(e1xleft, e2xright); :}
;

Et le visiteur gratuit :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9b; // nom du paquetage à adapter

import ast.exo9.AstNode;

/**
 * Compter le nombre d'opérateurs
 */
public class Gratos extends AstVisitorDefault {
	/**
	 * Nombre d'opérateur.
	 */
	private int nbOp;

	/**
	 * constructeur.
	 */
	public Gratos(AstNode n) {
		nbOp = 0;
		n.accept(this);
		System.out.println("Nombre d'op. binaire = " + nbOp);
	}

	/* visites : */
	@Override
	public void visit(ExpOpBin n) {
		nbOp++;
		defaultVisit(n);
	}
}

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

Le visiteur Evaluation :

Attention aux potentiels « ... » dans le code inséré !

package ast.exo9.exo9c; // nom du paquetage à adapter

import ast.exo9.AstNode;
import ast.exo9.exo9b.AstVisitorDefault;
import ast.exo9.exo9b.ExpAff;
import ast.exo9.exo9b.ExpEntier;
import ast.exo9.exo9b.ExpFmax;
import ast.exo9.exo9b.ExpFmin;
import ast.exo9.exo9b.ExpFor;
import ast.exo9.exo9b.ExpOpBin;
import ast.exo9.exo9b.ExpVar;
import ast.exo9.exo9b.ExpWhile;
import compil.parser;

/**
 * Visiteur de l'AST calculette.
 */
public class Evaluation extends AstVisitorDefault {
    /**
     * Valeur de retour des visit() !
     */
    static Integer retour;

    /**
     * Constructeur.
     */
    public Evaluation(AstNode n) {
        n.accept(this);
        System.out.println("> Visitor Evaluation = " + retour);
    }

    /* visites : */
    @Override
    public void visit(ExpAff n) {
        n.e.accept(this);
        parser.symTab.put(n.v.name, retour);
    }

    @Override
    public void visit(ExpFor n) {
        n.n.accept(this);
        int max = retour;
        for (int i = 1; i <= max; i++) {
            parser.symTab.put(n.v.name, i);
            n.e.accept(this);
        }
        n.v.accept(this);
    }

    @Override
    public void visit(ExpEntier n) {
        retour = n.value;
    }

    @Override
    public void visit(ExpFmax n) {
        Integer max = Integer.MIN_VALUE;
        for (AstNode f : n.args) {
            f.accept(this);
            if (retour > max)
                max = retour;
        }
        retour = max;
    }

    @Override
    public void visit(ExpFmin n) {
        n.e1.accept(this);
        Integer r1 = retour;
        n.e2.accept(this);
        Integer r2 = retour;
        if (r2 > r1)
            retour = r1;
        else
            retour = r2;
    }

    @Override
    public void visit(ExpOpBin n) {
        n.e1.accept(this);
        Integer r1 = retour;
        n.e2.accept(this);
        Integer r2 = retour;
        switch (n.op) {
        case '+':
            retour = r1 + r2;
            return;
        case '-':
            retour = r1 - r2;
            return;
        case '*':
            retour = r1 * r2;
            return;
        case '/':
            retour = r1 / r2;
            return;
        case '%':
            retour = r1 % r2;
            return;
        }
    }

    @Override
    public void visit(ExpVar n) {
        retour = parser.symTabGet(n.name);
    }

    @Override
    public void visit(ExpWhile n) {
        Integer res = -1;
        n.e1.accept(this);
        boolean cont = (retour != 0);
        while (cont) {
            n.e2.accept(this);
            res = retour;
            n.e1.accept(this);
            cont = (retour != 0);
        }
        retour = res;
    }
}

Et la spécification CUP avec le test de Gratos et Evaluation :

Attention aux potentiels « ... » dans le code inséré !

package compil;
import ast.exo9.*;
import ast.exo9.exo9b.*;
import ast.exo9.exo9c.*;
init with {: System.out.println("Calculatrice avec Visiteur"); prompt(); :}

parser code {:
  static void prompt() { System.out.print("> "); }
// Table de symboles (static et classe parser pour visibilité)
public static java.util.Map<String, Integer> symTab = new java.util.HashMap<>() ;
// Gestion des variables non initialisées
public static Integer symTabGet(String v) {
  Integer val = symTab.get(v);
  if (val!=null) return val ;
  System.out.println("Warning : " + v + " non initialisé");
  symTab.put(v,0);  // initialisation implicite 
  return 0;
}
:}

terminal NL, LPAR, RPAR, COMMA, FMIN, FMAX;
terminal PLUS, MOINS, MULT, DIV, MOD;
terminal AFFECT, CLEAR;
terminal Integer ENTIER;
terminal String VAR;
terminal WHILE, FOR;

nonterminal lignes, ligne, inst;
nonterminal Exp expr;
nonterminal AstList<Exp> args;

precedence left PLUS,MOINS;
precedence left MULT,DIV,MOD;

lignes ::= /* vide */   {: :}
       |   lignes ligne {: prompt(); :}  NL
;
ligne  ::= expr:e        {:
   // on laisse ici les 2 modes d'evaluations pour comparer mais cela
   // casse la semantique de la calculette sur les variables  puisque
   // chaque expression est evaluée 2 fois! pb i.e. "i=i+1"
                  new Gratos(e);
                  new Evaluation(e);
                  System.out.println("AST Eval=" + e.eval());
                  System.out.println(e.toPrint());
                         :}
       |   inst         {: :}
       |   error        {: /* msg ? */ :}
;
inst   ::= CLEAR        {: symTab.clear(); :}
       |   CLEAR VAR:v  {: symTab.remove(v); :}
       |   /* vide */   {: :}
;
expr   ::= ENTIER:e              {: RESULT = new ExpEntier(e); :}
       |   LPAR  expr:e RPAR     {: RESULT = e; :}
       |   expr:e1 PLUS expr:e2  {: RESULT = new ExpOpBin(e1, '+',  e2); :}
       |   expr:e1 MOINS expr:e2 {: RESULT = new ExpOpBin(e1, '-',  e2); :}
       |   expr:e1 MULT expr:e2  {: RESULT = new ExpOpBin(e1, '*',  e2); :}
       |   expr:e1 DIV expr:e2   {: RESULT = new ExpOpBin(e1, '/',  e2); :}
       |   expr:e1 MOD expr:e2   {: RESULT = new ExpOpBin(e1, '%',  e2); :}
       |   FMIN LPAR expr:e1 COMMA expr:e2 RPAR
                                 {: RESULT = new ExpFmin(e1, e2); :} 
       |   FMAX LPAR args:l RPAR {: RESULT = new ExpFmax(l); :} 
       |   VAR:v AFFECT expr:e   {: RESULT = new ExpAff(new ExpVar(v), e); :}
       |   VAR:v                 {: RESULT = new ExpVar(v); :}
       |   WHILE expr:e1 expr:e2 {: RESULT = new ExpWhile(e1, e2); :}
       |   FOR VAR:v ENTIER:n expr:e
                                 {: RESULT = new ExpFor(new ExpVar(v), new ExpEntier(n), e); :}
;
args   ::= expr:e                {: RESULT = new AstList<Exp>(); RESULT.add(e); :}
       |   args:e1 COMMA expr:e2 {: RESULT = e1; RESULT.add(e2); :}
;

Bootstrap et Brainfuck (hors présentiel, long, optionnel)

Paradoxe du Bootstrap, Comparaison Compilation/Interprétation.

TP optionnel en hors présentiel : Brainfuck

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