Interprète d'un mini-langage impératif

Introduction
Description
Documentation
Téléchargements

Introduction

Ce projet a pour but de définir un interprète d'un mini langage impératif. Ce langage est défini par un jeu d'instructions permettant la consultation et la mise à jour des variables de l'environnement. Les valeurs de ces variables sont décrites par des expressions arithmétiques ou booléennes. Cependant la représentation de ces valeurs, décrites par un domaine d'interprétation, n'est pas fixée et sera un paramètre de l'interprète. Suivant la représentation choisie, l'interprète calculera la valeur exacte des variables ou une valeur approchée indiquant simplement le type de la variable ou le signe de sa valeur. Il sera ainsi possible de vérifier les propriétés sur le programme (typage, terminaison, signe d'une variable, ...).

Top

Description

1) Le domaine d'interprétation
Le domaine d'interprétation se définit par une structure de données permettant de représenter de façon non nécessairement univoque les entiers et les booléens manipulés par le mini langage. Deux entiers différents peuvent donc avoir la même représentation. Par exemple, tous les entiers peuvent être représentés par la même constante INT. De même, un entier peut avoir plusieurs représentations. Par exemple, l'entier 1 peut être représenté par les constantes POSITIF et POSITIF_OU_NUL.
Cette structure de données fournit les opérations suivantes :
- représentation des booléens vrai et faux,
- représentation des entiers,
- comparaison de deux valeurs,
- somme et produit de deux valeurs,
- la valeur peut-elle représenter le booléen vrai ?, le booléen faux ?
- linéarisation (expression sous forme de chaîne de caractères) de deux valeurs.
A ces opérations, s'ajoute une opération de généralisation retournant une valeur « plus générale » que ses deux paramètres. Par exemple, la généralisation de POSITIF et de NUL pourra donner POSITIF_OU_NUL.
Les opérations appelées en dehors de leur domaine de définition lèveront une exception..

2) L'environnement
Un environnement est une structure de données générique associant à une variable (ici représentée par une chaîne de caractères) une valeur. Les opérations suivantes sont applicables sur l'environnement :
- création d'un environnement vide,
- ajout d'un couple (variable, valeur),
- modification d'une variable,
- suppression d'une variable,
- duplication de l'environnement,
- comparaison de deux environnements,
- invalidation de l'environnement. Un environnement invalide pourra être associé à une position inaccessible du programme (suite à une condition toujours fausse, une boucle infinie, …). La valeur des variables est alors non significative.
- test de validité de l'environnement,
- linéarisation (conversion en chaîne de caractères). Cette opération doit être définie sur les valeurs.
- combinaison de deux environnements. L'environnement résultant contient une généralisation des valeurs associées à une variable donnée par les deux environnements. La notion de généralisation doit être définie sur les valeurs. Si l'un des environnements est valide, l'autre environnement est retourné. Lorsque les deux environnements sont invalides, le résultat est invalide.
Les listes d'associations (style fonctionnel) ou les tables de hash (style impératif) pourront être utilisées pour représenter les environnements. Suivant le style choisi, les opérations précédentes pourront retourner un nouvel environnement ou modifier l'environnement considéré.

3) Les expressions
Une expression est évaluée dans un environnement. Le résultat de l'évaluation est une valeur du domaine d'interprétation. Une expression peut être (au moins) :
- un entier,
- un booléen,
- la somme de deux expressions,
- le produit de deux expressions,
- une variable,
- un test d'égalité de deux expressions.

4) Les instructions
Une instruction est exécutée dans un environnement et a pour effet de modifier l'environnement. Dans un style impératif, l'argument passé en argument est modifié. Dans un style fonctionnel, l'exécution retourne le nouvel environnement. Une instruction peut être (au moins) :
- une déclaration de variable dont la valeur initiale est donnée par une expression et la portée par une instruction. Lors de l'exécution, l'instruction définissant la portée de la variable est exécutée dans l'environnement courant augmenté d'une nouvelle entrée comportant la variable déclarée et sa valeur dans cet environnement.
- une affectation d'une expression à une variable. Lors de l'exécution, la liaison de la variable dans l'environnement courant est modifiée : la valeur de l'expression dans l'environnement courant lui est associée.
- un test (si cond alors inst1 sinon inst2). Lors de l'exécution, si la valeur de la condition peut être aussi bien vraie que fausse, les environnements résultant de l'exécution des deux instructions sont combinés. Si la valeur de la condition ne peut être que vraie, inst1 est exécutée ; sinon inst2 est exécutée.
- une séquence de deux instructions : la seconde instruction est exécutée dans l'environnement résultant de l'exécution de la première instruction.
- une boucle : si la valeur de la condition peut être aussi bien vraie que fausse, l'environnement courant est combiné avec l'environnement résultant de l'exécution du corps de la boucle puis de la boucle elle-même ; si la condition ne peut être que vraie, le corps puis la boucle elle-même sont exécutés ; si la condition ne peut être que fausse, l'environnement est inchangé. Pour éviter certains cas de bouclages infinis, si le corps de la boucle ne modifie pas l'environnement, la boucle n'est pas ré-executée et l'environnement est marqué invalide.
- une trace : le message passé en paramètre est affiché ainsi que le contenu de l'environnement. L'environnement est inchangé.

Top

Documentation

- En ligne. (html) [ 191 Ko]
- En ligne. (pdf) [ 463 Ko ]

Top

Téléchargements

- L' énoncé & la doc. (doc) [ 50 Ko ]
- L' énoncé & la doc. (pdf) [ 346 Ko ]
- Les sources.rar. [ 22 Ko ]
- Les sources.tar.gz. [ 26 Ko ]

Contenu de l'archive : (cliquable)
Partie Caml :
Makefile, cdom.h, cdom.c, domaine.mli, env.ml, langage.ml, main.ml, meval.ml, mexec.ml, mprint.ml, typedom.ml, valdom.ml
Partie Java :
Makefile, alloc.h, alloc.c, listgen.h, listgen.c, listNP.h, listNP.c, NPDom.h, NPDom.c,
Affect.java, Bool.java, Declare.java, Domaine.java, Egal.java, Entier.java, Environnement.java, Expression.java, Faux.java, If.java, Instruction.java, Int.java, Main.java, Menu.java, NPDom.java, Produit.java, Programme.java, Seq.java, Somme.java, Trace.java, TypeDom.java, ValDom.java, Variable.java, Vrai.java, While.java

Top