CSC 3101 – Algorithmique et langage de programmation

Portail informatique

CI6 : Un petit interpreteur

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 :

Node / \ / \ Add Scalar

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 :
(+ (+ 1 2) (+ 3 4)) 10

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