Cet exercice a pour objectif de travailler sur l'héritage et les interfaces,
et de vous faire découvrir les principes permettant d'écrire un petit
interpréteur, c'est-à-dire un programme capable d'exécuter d'autres programmes.
Durée des exercices obligatoires : 2h en présentiel
- Exercice 1 : obligatoire (facile, ∼20mn)
- Exercice 2 : obligatoire (moyen, ∼30mn)
- Exercice 3 : obligatoire (difficile, ∼40mn)
- Exercice 4 : obligatoire (difficile, ∼30mn)
- Exercice 5 : entraînement (moyen, ∼1h)
Écrire un interpréteur complet capable de lire un autre programme source
et de l'interpréter étant un peu trop long à réaliser dans le cadre d'un TP, nous ne
nous préoccupons que de la partie interprétation à partir d'un arbre de
syntaxe abstrait.
Un arbre de syntaxe abstrait est une représentation sous forme d'arbre d'un
programme. Dans notre cas, un arbre est constitué
de nœuds qui peuvent correspondre
à des opérations (addition, soustraction etc.), des variables
ou des scalaires (des entiers).
Par exemple, l'arbre représenté ci-dessous correspond
à l'expression x = x + 42 en Java.
La racine de l'arbre est une opération d'affectation
qui affecte la partie droite de l'arbre (l'expression qui ajoute 42
à la variable x) à la partie gauche (la variable x).
[Set]
/ \
/ \
[Variable x] [Add]
/ \
/ \
[Variable x] [Scalaire 42]
Dans l'exercice, nous aurons besoin de représenter des arbres sous une forme textuelle.
Pour cela, nous affichons un arbre
sous une forme préfixée et parenthésée : chaque nœud de l'arbre
qui représente une opération est affiché sous la forme
(op e1 ... en), où op est l'opération et
e1 ... en les paramètres.
Typiquement, nous afficherons l'arbre ci-dessus sous la forme
(set! x (+ x 42)) : set! représente une opération d'affectation,
le premier x l'élément de gauche et (+ x 42) l'élément de droite
(puisque l'opération est une addition avec comme paramètres x et 42).
Les étudiants fins connaisseurs remarqueront que cette écriture est celle du langage
Scheme.
Un simple additionneur (∼20mn – facile – obligatoire)
Nous commençons par mettre en œuvre un simple additionneur, c'est-à-dire une classe
capable d'additionner deux scalaires.
Dans un projet nommé ast, créez une classe tsp.ast.Main
contenant une méthode main.
Écrivez une classe nommée
Scalar avec un unique champ (privé) de type
entier nommé
value.
Outre un constructeur permettant d'initialiser le champ
value,
ajoutez les méthodes d'instance suivantes à
Scalar :
-
public int get() : cette méthode renvoie la valeur du scalaire,
-
public String toString() : cette méthode retourne une chaîne
de caractères représentant la valeur du scalaire
en utilisant la méthode statique Integer.toString(int i).
Dans la méthode
main, créez le scalaire
1 et affichez-le
dans le terminal.
On souhaite maintenant créer un arbre capable d'additionner deux scalaires.
Écrivez une classe nommée
Add contenant deux champs de type
Scalar
nommés
left et
right.
Le constructeur de
Add doit prendre en argument les opérandes de gauche et de droite
et les affecter aux champs.
Ajoutez les méthodes suivantes à
Add :
-
public int execute() : renvoie le résultat de l'addition de l'opérande de gauche
avec l'opérande de droite.
-
public String toString() : renvoie la chaîne de caractères (+ e1 e2),
dans laquelle e1 est la représentation de left
sous la forme d'une chaîne de caractères et e2 celle de right.
Dans la méthode
main, utilisez
Add pour calculer et afficher le résultat
de l'addition de 1 et 2. Vous veillerez aussi à afficher l'expression et à vérifier que
l'affichage produit est bien
(+ 1 2).
Additions imbriquées (∼30mn – moyen – obligatoire)
Nous souhaitons maintenant rendre notre additionneur générique dans le sens où
les opérandes de gauche et de droite doivent pouvoir être des scalaires ou elles-mêmes des
opérations d'addition. De cette façon, nous pourrons évaluer une expression
comme (+ (+ 1 2) (+ 3 4)) qui devrait donner comme résultat
10.
Pour cela, nous créons une interface générique nommée Node représentant
un nœud quelconque de l'arbre, c'est-à-dire un scalaire ou un additionneur.
La figure ci-dessous présente l'arbre d'héritage/mise en œuvre que nous utilisons :
Techniquement, l'interface Node doit définir
une unique méthode nommée int execute() qui va permettre d'évaluer un nœud.
Si le nœud est un scalaire, le résultat de son évaluation est sa valeur.
Si le nœud est un additionneur, le résultat de son évaluation est la somme
du résultat de l'évaluation du membre de gauche avec celle du membre de droite.
Créez une interface nommée
Node définissant la méthode
int execute().
Comme
Add possède déjà une méthode
execute, vous pouvez
aussi directement déclarer que
Add met en œuvre
Node
sans autre modification.
Avec Eclipse, il suffit de cliquer sur New puis sur Interface
pour créer une interface.
Modifiez Scalar de façon à ce que Scalar mette en œuvre
Node. L'évaluation d'un scalaire doit simplement renvoyer sa valeur.
Dans Add, modifiez les types des membres de gauche et de droite de façon
à ce que ce qu'ils aient le type générique Node.
Modifiez le constructeur de façon à prendre en paramètre deux nœuds,
et modifiez la méthode execute de façon à ce qu'elle additionne
le résultat de execute() sur le membre de gauche avec le résultat
de execute() sur le membre de droite.
Vérifiez que vous arrivez toujours à calculer la somme de 1 et 2.
Construisez l'expression correspondant à
(+ (+ 1 2) (+ 3 4)) dans
la méthode
main.
Affichez cette expression sur le terminal
avant d'afficher le résultat de son évaluation.
Sur le terminal, vous devriez voir :
Calculette multi-opérations (∼40mn – difficile – obligatoire)
Nous souhaitons maintenant ajouter de nouvelles opérations comme la multiplication
de deux entiers ou l'inversion du signe d'un entier.
Une première approche simple permettant d'ajouter ces opérations serait
de créer des classes sur le modèle de Add
mettant en œuvre Node, et effectuant l'opération.
Toutefois, comme beaucoup de code serait alors redondant entre ces classes
et la classe Add,
nous préférons utiliser l'héritage pour factoriser un maximum le code.
Tout au long de cet exercice, l'affichage produit par votre programme
ne devrait pas varier par rapport à l'affichage que vous avez eu à la question précédente.
Nous modifions notre code étape par étape pour introduire une nouvelle classe
générique représentant n'importe quelle opération.
Dans un premier temps, nous insérons une classe abstraite nommée Operation
dans l'arbre d'héritage.
Cette classe représente une opération quelconque.
Pour le moment, cette classe est vide, le but de la question n'étant que de l'insérer
de façon à obtenir l'arbre d'héritage/mise en œuvre suivant :
Node
/ \
/ \
Operation Scalar
|
|
Add
Créez donc une classe abstraite nommée Operation et mettant en œuvre
Node.
Cette classe est abstraite car elle ne met pas elle-même en œuvre la méthode
execute qui est mise en œuvre dans les classes filles.
Modifiez ensuite la classe Add de façon à ce qu'elle ne mette plus
en œuvre Node, mais hérite
de Operation.
Avec Eclipse, il suffit de sélectionner abstract dans l'onglet qui vous permet
de créer une classe.
La classe
Operation représente n'importe quelle opération et le nombre
d'opérandes n'est donc pas fixe (l'inversion du signe a une unique opérande alors que l'addition en a deux).
Pour cette raison, ajoutez à la classe
Operation :
- un champ privé Node[] ops contenant l'ensemble des opérandes,
- une méthode publique Node op(int i) permettant d'accéder à la iième opérande,
- une méthode publique int nbOps() renvoyant le nombre d'opérandes,
- un constructeur publique Operation(Node... ops) permettant d'initialiser
le champ ops de Operation. On vous rappelle
que Node... ops permet de déclarer une méthode avec un nombre variable
d'arguments, et que les arguments sont rangés sous la forme d'un tableau dans ops.
Pour finir, dans le constructeur de
Add, utilisez
super
pour initialiser de façon adéquate le tableau d'opérandes de
Operation
via le constructeur de
Operation.
À cette étape, les opérandes sont donc représentées deux fois :
une fois dans
Operation sous la forme d'un tableau, et une fois
dans
Add sous la forme des champs
left et
right.
Pour le moment, conservez cette double représentation.
Modifiez les méthodes int execute() et String toString()
de Add de façon à utiliser la méthode Node op(int i)
pour accéder aux opérandes. Vous pouvez maintenant vous débarrasser des champs
left et right de Add de façon à ne conserver qu'une unique
représentation des opérandes dans la classe Operation.
Nous souhaitons maintenant rendre la méthode String toString()
générique en la déplaçant de Add vers Operation.
Dans Operation, on connaît les opérandes, mais
pas encore l'opération.
Pour cette raison, nous effectuons une étape intermédiaire avant de déplacer la
méthode String toString().
À cette étape on vous demande donc juste d'ajouter une méthode abstraite String opString()
à la classe Operation et de la mettre en œuvre dans Add.
Cette mise en œuvre doit renvoyer la chaîne de caractères "+".
Enfin, modifiez Add.toString() de façon à utiliser opString()
pour générer le '+'.
Déplacez maintenant String toString() de Add vers Operation.
Au lieu de considérer que votre opération a forcément deux opérandes, modifiez la méthode
toString() pour qu'elle concatène les nbOps() opérandes.
Écrivez une classe Neg héritant de Operation et permettant d'inverser le
signe de son opérande.
Modifiez la méthode main de façon à afficher et évaluer
l'arbre (+ (+ 1 2) (- (+ 3 4))) qui devrait donner comme résultat
-4.
À cette étape, l'arbre d'héritage que vous devriez avoir est le suivant :
Node
/ \
/ \
Operation Scalar
/ \
/ \
Neg Add
Les variables (∼30mn – difficile – obligatoire)
Nous souhaitons maintenant ajouter des variables à notre langage.
Vous remarquerez qu'une variable est simplement un scalaire possédant un nom.
Pour cette raison, nous réutilisons la classe Scalar pour mettre
en œuvre les variables.
Ajoutez une classe
Variable héritant de
Scalar et contenant :
- un champ String name indiquant le nom de la variable,
- un constructeur prenant en argument le nom de la variable et pré-initialisant la variable à 0 en utilisant
super.
L'arbre d'héritage que vous devriez avoir à cette étape est le suivant :
Node
/ \
/ \
Operation Scalar
/ \ |
/ \ |
Neg Add Variable
Évaluer une variable revient à renvoyer sa valeur.
La méthode int execute() mise en œuvre dans Scalar
effectue déjà ce travail et il n'est donc pas nécessaire de la redéfinir dans
Variable.
En revanche, lorsqu'on affiche une variable
avec String toString(), on veut afficher le nom de la variable et non sa valeur.
Redéfinissez donc la méthode String toString() dans Variable
de façon à afficher le nom de la variable.
Dans la méthode main, allouez une variable x, puis affichez
et évaluez l'arbre (+ x 20), qui devrait donc être évalué à 20 puisque x
est pré-initialisé à 0.
Ajoutez une classe
Set, héritant de
Operation, et permettant de modifier
une variable. Cette opération prend deux arguments : une variable et un nœud quelconque.
L'affichage d'une expression doit produire la chaîne de caractère
(set! var val)
où
var est la variable et
val un nœud quelconque.
Comme le champ value de Scalar est privé, vous ne pouvez pas y accéder
de la classe Set.
Pour cette raison, ajoutez une méthode publique void set(int value) à Scalar
permettant de modifier la valeur du scalaire.
Testez votre opération
Set en affichant et évaluant l'expression
(set! x 22) avant d'afficher et évaluer l'expression
(+ x 20). Ces affichages et évaluations devrait produire l'affichage suivant :
(set! x 22)
22
(+ x 20)
42
L'exécution d'une opération Set doit :
- évaluer le membre de droite de l'opération,
- affecter le résultat de cette évaluation à la variable (membre de gauche),
- renvoyer ce résultat.
La méthode op(0) renvoie la variable, mais cette dernière a le type Node,
ce qui fait que vous ne pouvez pas directement invoquer le set(int value) de
Variable pour modifier la valeur de la variable.
Pensez que vous pouvez transtyper explicitement un Node en Variable
puisque vous manipulez bien un objet de type Variable.
L'arbre d'héritage que vous devriez avoir à cette étape est le suivant :
Node
/ \
/ \
Operation Scalar
/ | \ |
/ | \ |
Neg Add Set Variable
Vers un interpréteur complet (∼1h – moyen – entraînement)
Vous pouvez maintenant compléter votre petit interpréteur d'arbre pour lui ajouter
quelques fioritures comme des structures de contrôle.
De façon à afficher des résultats intermédiaires, ajoutez une classe
Echo héritant de Opération.
Cette classe représente une opération
(echo expr),
qui affiche sur le terminal le résultat de l'évaluation de expr avant de renvoyer
ce résultat.
Vérifiez que (+ (echo (+ 1 2)) 7) affiche bien 3 pendant l'évaluation
et que l'évaluation de l'expression est bien égale à 10.
Pour gérer les conditions, nous avons besoin de booléens. Dans notre petit interpréteur,
un scalaire est directement considéré comme un booléen : si sa valeur est égale à 0, c'est que le scalaire
est un booléen faux, sinon, c'est que c'est un booléen vrai.
À partir de ce choix,
ajoutez une classe If permettant d'évaluer une condition.
L'arbre d'une condition est (if condition ifTrue ifFalse), où
condition, ifTrue et ifFalse sont des nœuds.
Vérifiez que (if 1 42 666) s'évalue bien en 42 et (if 0 42 666)
s'évalue bien en 666.
Pour écrire des programmes avancés, nous avons besoin de blocs.
Un bloc est simplement une opération dont le nombre d'opérandes est variable
et telle que son évaluation évalue chacune des opérandes avant de renvoyer le résultat de l'évaluation
de sa dernière opérande. Lorsque nous affichons l'arbre, nous représentons
l'expression correspondant à un bloc par (begin e1 ... en).
Ajoutez une classe Begin permettant d'évaluer un bloc.
Vérifiez que (if 1 (begin (echo 0) 42) 666) affiche bien 0 pendant l'évaluation
et que le résultat de cette évaluation est bien 42.
Ajoutez maintenant la classe Lt permettant d'évaluer un arbre (< e1 e2).
Cette évaluation doit renvoyer vrai (1) si e1 est plus petit que e2
et faux (0) sinon.
Finalement, ajoutez une classe
While permettant d'évaluer l'arbre
(while cond body).
L'évaluation doit commencer par évaluer
cond.
Si le résultat de cette évaluation est
vrai (un nombre différent de 0), l'évaluation doit continuer en évaluant
body
avant de recommencer l'évaluation de
cond.
Le résultat de l'évaluation doit être celui du dernier
body exécuté.
Si
body n'est jamais exécuté, le résultat de l'évaluation doit être le
nombre 0.
Construisez, affichez et interprétez l'arbre
(begin (set! x 0) (while (< x 10) (begin (echo x) (set! x (+ x 1))))).
Qu'affiche votre programme ?
Le programme affiche les entiers de 0 (inclus) à 10 (non inclus) dans la boucle,
puis affiche 10 puisque c'est le résultat de l'ensemble de l'expression.
Félicitations, vous savez maintenant écrire des interpréteurs ! Pour les étudiants qui veulent
approfondir le sujet, vous pouvez vous amuser à créer des fonctions.