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

  1. É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é:
    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.

  2. 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:
  3. É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.
  4. É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.

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

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