Lors de la dernière séance d'amphi, le langage CalculiX vous a été présenté, ainsi que sa sémantique, c'est-à-dire la manière dont un programme CalculiX doit être exécuté. Le but de ce TD est :

• d'implémenter une structure de données pour représenter les expressions sous forme d'arbres de syntaxe abstraite ;
• d'implémenter une méthode d'évaluation de ces expressions (un interprète) pour produire des valeurs.

Préparation

Pour commencer, créez un nouveau projet TD3, suivant la procédure habituelle.
Téléchargez l'archive td_12.zip qui contient un package CalculiX (dans le répertoire du même nom) et deux bibliothèques .jar (dans le répertoire lib).

Intégrez le package CalculiX à votre projet Eclipse de manière habituelle, puis importez-y les deux bibliothèques.
(Pour cela, accédez aux propriétés du projet puis sélectionnez la catégorie "Java Build Path", et enfin l'onglet "Libraries" ; l'ajout peut alors se faire à l'aide du bouton "Add JARs".)

L'exécution de la méthode main de la classe Main du package CalculiX doit afficher

All ok, testing from test0 to test-1

Organisation du TD

Le package CalculiX contient des classes décrites en cours :

• des classes énumérées Operator, Connective et Comparator, qui listent respectivement les opérations binaires sur les entiers, celles sur les opérations booléennes, et les comparaisons d'entiers ;
• une classe abstraite Expression, pour représenter les expressions sous forme d'arbres de syntaxe abstraite ;
• une classe abstraite Value, pour représenter les valeurs ;
• une classe EvalException, pour représenter une exception qui pourra être lancée lors de l'évaluation.

Pour autoriser l'évaluation d'une expression à renvoyer des valeurs de différentes natures, nous allons utiliser l'héritage comme dans le TD2 : l'évaluation d'une expression renverra un objet d'une classe abstraite Value (que nous vous avons fournie), et

Ainsi, l'expression (2*3)+4 va être un objet de la sous-classe d'Expression qui implémente les opérations sur les entiers, et cette classe aura un champ pour sa sous-expression gauche (ici 2*3) et un champ pour sa sous-expression droite (ici 4). Ces sous-expressions pouvant être de différentes formes (on le voit ici : multiplication d'une part, et constante entière d'autre part), on déclarera ces champs comme étant de type Expression.
Plutôt que d'être rassemblé en un seul endroit, le code de la fonction d'évaluation va être réparti entre les sous-classes d'Expression (par re-définition d'une fonction déclarée dans la classe abstraite Expression). Cette note vous en dira un peu plus sur ce paradigme de programmation.

Pour tester votre code, faciliter les dépôts et la correction de votre travail, vous devrez

• compléter les méthodes de la classe ExpressionFactory du package CalculiX
• placer toutes les classes que vous allez créer dans le même fichier ExpressionFactory.java, à la suite de la classe ExpressionFactory.

Nous allons maintenant procéder à l'implémentation du langage et de son interprète, construction par construction.

Implémenter une structure d'arbre simple

Considérons des expressions arithmétiques très simples faites d'entiers, de booléens, des opérations binaires sur les entiers et des opérations booléennes ou et et :

e ::=	i | b
	| e + e | e - e | e * e | e / e
	| e && e | e || e | e ^ e

où i représente un entier quelconque
et b représente un booléen quelconque.

Les valeurs renvoyées

Implémentez une sous-classe de Value pour représenter les constantes entières. On rappelle que cette classe doit être placée dans le fichier ExpressionFactory.java.
Assurez-vous que votre classe possède un constructeur et redéfinissez la méthode int asInteger (), qui convertit une valeur CalculiX entière en un entier nu.

Implémentez de même une sous-classe de Value pour représenter les constantes booléennes.
Assurez-vous qu'elle est munie d'un constructeur et d'une implémentation de la méthode boolean asBoolean (), qui convertit une valeur CalculiX booléenne en un booléen nu.

Complétez les méthodes Value buildValue (int i) et Value buildValue (boolean b) de la classe ExpressionFactory, qui construisent respectivement une valeur représentant l'entier i et une valeur représentant le booléen b.

Vous pouvez tester en utilisant le programme Test.java du package CalculiX et sa méthode test1().

Déposez le fichier ExpressionFactory.java qui contient donc la définition de trois classes.

Expressions constantes: Entiers et booléens

Implémentez une sous-classe d'Expression pour représenter les entiers, i.e. les expressions de la forme syntaxique i.
Dans cette classe, redéfinissez la méthode Value eval () définie dans la classe Expression, pour qu'elle évalue directement cette expression comme une valeur correspondant à l'entier associé à cette expression.
Pour l'instant, on ne s'intéresse pas à la méthode Value eval(Environment env).

Implémentez une sous-classe d'Expression pour représenter les booléens, i.e. les expressions de la forme syntaxique b.
Redéfinissez de manière appropriée la méthode Value eval ().

Complétez les méthodes Expression buildConstant (int i) et Expression buildConstant (boolean b) de la classe ExpressionFactory, qui construisent respectivement une expression représentant l'entier i et une expression représentant le booléen b.

Vous pouvez tester en utilisant la méthode test2() du programme Test.java.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Opérations sur les entiers

On recommence maintenant ces étapes sur les autres constructions du langage, en commençant par les expressions de la forme e + e, e - e, e * e et e / e.

On pourra au choix, implémenter une sous-classe pour l'addition, une sous-classe pour la soustraction, etc., ou implémenter une seule sous-classe avec un champ de type Operator pour indiquer de quelle opération il s'agit.
Redéfinissez de manière appropriée la méthode héritée Value eval (), pour qu'elle évalue une telle expression comme une valeur.

Complétez la méthode Expression buildIntegerOperation (Expression left, Operator op, Expression right) de la classe ExpressionFactory.

Vous pouvez tester en utilisant la méthode test3() du programme Test.java.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Opérations sur les booléens

Implémentez la représentation des expressions de la forme e && e, e || e, et e ^ e.

Complétez la méthode Expression buildBooleanOperation (Expression left, Connective op, Expression right) de la classe ExpressionFactory.

L'opérateur booléen ^ représente xor et nous permettra d'autoriser dans la syntaxe concrète l'expression !e (la négation booléenne de e) : elle sera en effet représentée par le même arbre de syntaxe abstraite que e^true.

Implémentez donc également Expression buildBooleanNegation (Expression e) dans la classe ExpressionFactory.

Vous pouvez tester en utilisant la méthode test4() du programme Test.java.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Pour la suite, afin d'utiliser et de tester votre implémentation des expressions, un analyseur syntaxique (parser en anglais) va lire une expression sous forme textuelle et crée l'arbre de syntaxe abstraite qui la représente. Le package CalculiX contient donc aussi :

• une classe Main, pour tester l'implémentation de vos expressions et de leur évaluation ;
• d'autres classes et fichiers (que l'on n'a pas besoin d'ouvrir) qui réalisent l'analyse syntaxique.

Modifier la méthode main de la classe Main pour effectuer les 16 premiers tests, qui doivent passer correctement.

Implémenter une structure d'arbre avancée

e ::=	i | b
	| e + e | e - e | e * e | e / e
	| e && e | e || e | e ^ e
	| e==e | e<e | e<=e | if e then e else e

Nous allons voir :
- comment adapter notre implémentation des arbres pour cette syntaxe enrichie ;
- comment écrire notre fonction d'évaluation, sachant qu'elle devra parfois renvoyer un entier, parfois renvoyer un booléen.

If...then...else

Complétez la méthode Expression buildIf (Expression condition, Expression then_branch, Expression else_branch) de la classe ExpressionFactory.

Effectuez les tests de la classe Main. Les 18 premiers tests doivent passer.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Comparateurs

Complétez la méthode Expression buildIntegerComparison (Expression left, Comparator op, Expression right) de la classe ExpressionFactory.

Effectuez les tests de la classe Main. Les 20 premiers tests doivent passer.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Pour aller plus loin : Evaluation d'expressions avec variables

Variables et let...in

Redéfinissez maintenant, dans les sous-classes d'Expression, la méthode Value eval (Environment env), pour qu'elle évalue toutes les sortes d'expressions vues jusqu'à maintenant dans un environnement passé en paramètre. Celui-ci devra être passé aux appels récursifs. On veillera à réutiliser le code de Value eval() lorsque c'est possible.

Implémentez une sous-classe d'Expression pour représenter les variables (le nom x est une String) et une autre sous-classe pour les expressions de la forme let x = e in e.

Continuez votre implémentation de ExpressionFactory avec Expression buildVarRead (String x) et Expression buildLet (String x, Expression left, Expression right).

Redéfinissez de manière appropriée la méthode héritée Value eval(Environment env) (on ne redéfinira pas Value eval(), qu'on laissera générer une exception). L'argument Environment env est enfin utile :

• on peut retrouver la valeur associée à la variable x dans un certain environnement en utilisant sa méthode dynamique search(x) (qui lève une exception si x n'est pas trouvé dans l'environnement) ;
• un environnement peut être étendu avec une association de plus "x->v" par sa méthode dynamique Environment extend(x,v).

Effectuez les tests de la classe Main. Les 26 premiers tests doivent passer.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Sommes

Redéfinissez de manière appropriée la méthode héritée Value eval(Environment env).

Finissez votre implémentation de ExpressionFactory avec Expression buildSigma (String x, Expression lo, Expression hi, Expression body).

Effectuez les tests de la classe Main. Les 28 premiers tests doivent passer.

Déposez le fichier ExpressionFactory.java qui contient toutes les classes qui définissent votre structure de données.

Programmation en CalculiX

Dans un fichier texte ex2.txt, écrivez une expression qui calcule la somme des nombres premiers de 2 à 1000 (inclus).

Écrivez dans la classe Main deux méthodes java int ex1() et int ex2() qui font le même travail, et comparez les valeurs qu'elles renvoient avec l'évaluation de vos expressions, sous la forme de deux tests dans le Main.

Déposez ex1.txt.

Déposez ex2.txt.

Déposez Main.java.