Maîtrise 2003--2004 Projet de compilation
Évaluateur d'expressions arithmétiques
TP individuel, à finir à la maison et à rendre |
par email au chargé de TP à J+3 au matin |
Personnalisation d'emacs avec le mode tuareg d'ocaml.
Pour mieux profiter de l'environnement de développement
emacs/ocaml, éditer le fichier ~/.emacs
afin d'y insérer le contenu du fichier
~conchon/compil/init-tuareg.el (avec ctrl-x
i). Cette modification du fichier de configuration d'emacs permettra
dès le prochain lancement de l'éditeur de charger automatiquement
le mode tuareg d'ocaml chaque fois que vous
éditerez un fichier .ml (un résumé des raccourcis
clavier de ce mode se trouve dans le guide de survie).
Le top-level d'ocaml.
Pour ce premier TP -- et uniquement pour celui-là -- vous
gn'utiliserez que le top-level d'ocaml pour évaluer vos
programmes (pas de compilation avec ocamlc). Ce top-level
sera lancé automatiquement dans emacs dès la première
évaluation d'une phrase ou d'un tampon ocaml (resp. avec les touches
ctlr-x ctrl-e et ctrl-c ctrl-b).
Évaluateur d'expressions arithmétiques
Le but du TP est de réaliser un évaluateur d'expressions
arithmétiques. La définition de type suivante en ocaml permet de
décrire la syntaxe abstraite de ces expressions:
type expr = Cst of int
| Sum of expr * expr
| Diff of expr * expr
| Prod of expr * expr
| Quot of expr * expr
Exercice 1
Écrivez une fonction eval_expr
de type expr -> int
qui calcule la valeur
entière d'une expression.
corrige
Exercice 2
On étend maintenant nos expressions arithmétiques avec des
variables locales pour stocker les résultats de calculs
intermédiaires. Le type expr est étendu avec deux nouveaux
constructeurs:
type expr = ...
| Var of string
| Letin of string * expr * expr
Modifiez votre fonction eval_expr en une fonction prenant
comme argument supplémentaire un environnement env qui
lie les noms des variables locales à leurs valeurs entières. On
utilisera un environnement env de type (string *
int) list et la fonction List.assoc : 'a -> ('a * 'b) list
-> 'b pour rechercher la valeur liée à une variable locale.
corrige
Parsing.
Afin de vous aider à tester les différentes fonctions que vous
aurez à développer dans ce TP (comme vous avez pu vous en
apercevoir dans l'exercice précédent, il est très pénible de
construire directement des valeurs de type expr), vous
pouvez récupérer des parsers d'expressions arithmétiques
en tapant la commande:
cp ~conchon/compil/tp1/parser*.ml .
Les deux fichiers parser_expr.ml et
parser_instr.ml que vous allez récupérer contiennent
respectivement les fonctions read_expr: string -> expr et
read_instr: string -> instr permettant de transformer une
chaîne de caractères de type string en une valeur de
type expr ou instr (ce dernier type sera utilisé
à partir de l'exercice 4). Pour utiliser ces fonctions dans le
top-level d'ocaml, vous devez tout d'abord charger en mémoire le
préprocesseur camlp4 à l'aide de la directive
#load ``camlp4o.cma'' puis charger le programme
parser_expr.ml (resp. parser_instr.ml) avec la
directive #use ``parser_expr.ml'' (resp. #use
``parser_instr.ml'').
Les chaînes de caractères reconnues par la fonction
read_expr seront par exemple de la forme ``10*let
x=(3+4) in x/2'' ou simplement "45+3*8". Celles de la
fonction read_instr seront celles reconnues par la fonction
read_expr auxquelles s'ajouteront les chaînes de la
forme "set x=3+(let y=z*4 in y/2)".
Exercice 3
Dans l'exercice précédent, la fonction eval_expr se
termine en renvoyant l'exception Not_found, sans plus de
précision, quand l'expression évaluée utilise une variable qui
n'existe pas (ou qui n'est pas dans la portée de sa déclaration).
Afin d'être plus précis sur l'origine de l'erreur, on définit
une nouvelle exception VarUndef:
exception VarUndef of string;;
Adapter votre fonction eval_expr pour lever cette exception
lorsqu'une variable est mal utilisée et indiquer ainsi le nom de la
variable posant problème.
corrige
Exercice 4
On ajoute maintenant la possibilité d'utiliser des variables
globales dans nos expressions. Le type instr suivant
décrit les instructions pour affecter une valeur à une variable
globale et afficher la valeur d'une expression:
type instr = Set of string * expr
| Print of expr
Écrire une fonction eval_instr : instr -> unit qui prend
en entrée une instruction et calcule sa valeur en lisant et
écrivant si nécessaire dans un environnement liant les noms des
variables globales à leurs valeurs entières. On utilisera un
environnement genv de type (string * int) list ref
(c'est à dire une référence sur une liste de paires
string * int).
corrige
Exercice 5
Dans l'exercice précédent nous vous avons utilisé un
environnement de variables globales de type (string * int)
list ref. Cependant, quand le nombre de variables est important,
l'opération de recherche dans une liste est trop coûteuse et on
préfère alors utiliser des structures de données comme les
tables de hachage où l'opération de recherche est plus efficace.
L'objectif de cet exercice est de remplacer l'environnement global
genv de l'exercice précédent par une table de
hachage.
Rappel. L'idée de base d'une table de hachage est la
suivante: pour chaque enregistrement à ajouter/rechercher dans la
table, on calcule une clé entière, entre 0 et M-1 (où M
est la longueur de la table de hachage), et on utilise M listes
pour stocker les enregistrements de même clé.
-
Écrire une fonction hash : string -> int qui calcule
la clé entière d'une chaîne de caractère. Une fonction
possible est celle qui étant donné une chaîne
s=a0a1... an retourne la clé:
où code(ak) est le code ASCII du caractère ak (ce
code est donné en ocaml par la fonction Char.code).
On pourra prendre par exemple M=17 comme longueur de la table de hachage.
Une autre possibilité est d'utiliser la fonction
Hashtbl.hash de type 'a -> int qui associe un entier positif
à des valeurs de types quelconques.
- On définit le type des tables de hachage de la façon
suivante:
type t = (string * int) list array;;
Écrire une fonction nouveau : int -> t pour créer une
nouvelle table de hachage dont la taille est donnée en argument
à la fonction. Les fonctions de manipulation de tableaux dont
vous aurez besoin pour cette question (et les suivantes) sont:
Array.make : int -> 'a -> 'a
array. L'expression Array.make n x retourne un
tableau de longueur n dont tous les éléments sont
initialisés avec la valeur x.
- Array.length : 'a array -> int. L'expression
Array.length t retourne la longueur du tableau t.
- L'expression t.(i) permet d'accéder au
i élément du tableau t.
- L'expression t.(i) <- x affecte la valeur
x au i élément du
tableau t.
- Écrire une fonction ajoute : t -> string * int -> unit
pour ajouter une nouvelle entrée (formée d'une chaîne de
caractères et d'un entier) dans une table de hachage.
- Écrire une fonction trouve : t -> string -> int pour
chercher la valeur associée à une chaîne de caractères
donnée dans une table de hachage.
À l'aide de ces fonctions, modifier la fonction eval de
l'exercice précédent pour un environnement global genv
implanté à l'aide d'une table de hachage.
corrige
Exercice 6
Le but de cet exercice est de rendre plus modulaire le code de votre
évaluateur d'expressions arithmétiques en découpant les
parties de votre programme à l'aide des modules et des
foncteurs d'ocaml.
-
La signature suivante définit l'interface d'un module
implantant un environnement de variables globales pour des
expressions arithmétiques entières.
module type GlobalEnv =
sig
type t
val nouveau : int -> t
val ajoute : t -> string * int -> unit
val trouve : t -> string -> int
end
En réutilisant les fonctions que vous avez écrites dans les
exercices 3 et 4, écrivez deux implantations
AssocEnv et HashEnv pour cette interface.
AssocEnv utilisera simplement une liste comme
implantation du type t et HashEnv une table
de hachage.
- Afin de rendre le code de votre évaluateur indépendant du
choix d'implantation de l'environnement global, écrivez un
foncteur Eval (Genv : GlobalEnv) paramétré par un
module dont l'interface est GlobalEnv et générez deux
évaluateurs utilisant respectivement un environnement global
implanté avec une table de hachage et avec une liste de
paires de type string * int.
corrige
This document was translated from LATEX by
HEVEA.