Master M1 2005--2006 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.
Pour mieux profiter de l'environnement de développement
emacs/ocaml, éditer le fichier ~/.emacs
afin d'y insérer le contenu du fichier
/homes/filliatr/TER-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
n'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
Écrire 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
Modifier votre fonction eval_expr pour qu'elle prenne
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
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 respectivement affecter une valeur à
une variable globale, annuler la dernière affectation (si elle
existe) d'une variable globale et afficher la valeur d'une
expression:
type instr = Set of string * expr
| Unset of string
| 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 (eval_instr (Unset "x")
n'aura aucun effet si la variable globale "x" n'apparait
pas dans l'environnement). 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). On
utilisera la fonction List.remove_assoc : 'a -> ('a * 'b)
list -> ('a * 'b) list pour supprimer la dernière valeur liée à
une variable globale.
corrige
Parsing.
Afin de vous aider à tester vos fonctions eval_expr et
eval_instr, vous pouvez récupérer le module Parsers
en tapant la commande Unix:
cp /homes/filliatr/TER-COMPIL/tp1/parsers.cm* .
Ce module contient la définition des types expr et
instr ainsi que les fonctions read_expr: string ->
expr et read_instr: string -> instr qui permettent
respectivement de transformer une chaîne de caractères de type
string en une valeur de type expr ou instr.
Pour utiliser ces fonctions dans le top-level d'Ocaml, vous devez
simplement charger en mémoire le module à l'aide des directives
suivantes:
# #load "parsers.cmo";;
# open Parsers;;
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 reconnues par
la fonction read_instr seront de la forme set
x=3+(let y=z*4 in y/2) ou unset x ou encore print
x+9.
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 devient important, les
opérations de recherche/suppression sur une liste sont trop
coûteuses et on préfère alors utiliser des structures de données
comme les tables de hachage où ces opérations sont plus efficaces.
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/supprimer
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 à l'élément
i du tableau t.
- L'expression t.(i) <- x affecte la valeur x
à l'élément i 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 (trouve tbl s lève
Not_found si s n'est liée à aucune valeur
dans tbl).
- Écrire une fonction supprime : t -> string -> unit
afin que supprime tbl s supprime la dernière valeur
associée à s dans tbl et restaure la valeur
précédente si elle existe (cette fonction n'a aucun effet si
s n'est liée à aucune valeur dans tbl).
À l'aide de ces fonctions, modifier la fonction eval de
l'exercice précédent pour qu'elle fonctionne avec 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
val supprime : t -> string -> unit
end
En réutilisant les fonctions que vous avez écrites dans les
exercices 3 et 4, écrire 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, écrire un foncteur
Eval (Genv : GlobalEnv) paramétré par un module dont
l'interface est GlobalEnv et générer 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.