Un interpréteur Pseudo-Pascal

La solution complète est ici.

Contexte informatique des TP

Ce TP reprend la présentation des TP inaugurée la semaine dernière. L'exercice consiste à écrire le fichier manquant d'un programme complet.

Ici, le programme complet est un interpréteur pseudo-pascal qui prend un fichier source en argument. Vous n'avez à écrire ni analyseur syntaxique ni analyseur lexical, ni glue code qui met tout ça ensemble. C'est déjà fait et present dans une archive tar.

Ici l'archive s'appele zyvai.tar, c'est donc un interpréteur où il ne manque que l'interprète...Il faut d'abord récupérer l'archive, puis la défaire : 
# tar xf zyvai.tar
Cette opération crée un sous-répertoire zyvai qui contient tout ce qui est nécessaire pour le TP, en particulier un Makefile et un .depend. 
# cd zyvai
# make zyvai
ocamlc  -c misc.mli
ocamlc  -c misc.ml
ocamlc  -c location.mli
ocamlc  -c location.ml
ocamlc  -c pp.mli
ocamlc  -c print.ml
ocamlc  -c lexer.mli
ocamlc  -c lexer.ml
ocamlc  -c ll.mli
ocamlc  -c ll.ml
ocamlc  -c interpret.mli
make: *** No rule to make target `interpret.ml', needed by `interpret.cmo'.  Stop.
Et ça rate parce qu'il manque justement le fichier interpret.ml. Mais un fichier squelette.ml est fourni. Ce fichier est in interpréteur extrêmement incomplet qui ne sait qu'interpréter l'instruction writeln.
open Pp

exception PasEncore

type valeur = Vint of int

type erreur = Type of type_expr

exception Error of erreur

(* Évaluation des expressions, type Pp.expression -> valeur *)
let rec expr e = raise PasEncore

(* Évaluation des expressions de type entier, type Pp.expression -> int *)
and expr_int e = match expr e with
| Vint i -> i
| _ -> raise (Error (Type Integer))

let instr = function
| Writeln_int e ->
   let i = expr_int e in
   print_int i ;
   print_newline ()
| _ -> raise PasEncore

let instrs is = List.iter instr is

let eval {global_vars = globs ; definitions = defs ; main = is} =
  instrs is
(Noter que le type Pp.program est un type enregistrement.)

Il faut le récupérer, puis le renommer : 
# mv squelette.ml zyvai/interpret.ml

Ce qu'il faut faire

L'implémentation interpret.ml doit être conforme à l'interface interpret.mli. C'est à dire qu'elle exporte une fonction eval qui prend un programme (type Pp.program) et renvoie ``()'' :
val eval : Pp.program -> unit

Pour écrire interpret.ml, on s'appuiera sur la syntaxe abstraite (déjà présente dans pp.mli) et la description sémantique informelle données dans le poly. La démarche suivante est suggérée.
  1. Commencer par définir un type des valeurs (booléens, entiers, tableaux). Définir également le type des erreurs (qui l'on complètera au fur et à mesure).

  2. Définir l'évaluation des expressions arithmétiques sans variables, à partir du type des expressions de pp.mli.

    On peut ensuite essayer l'interprète minimal en lui donnant un programme minimal, a.p par exemple : 
    program
begin
   writeln(1+2+3+4)
end.
    On essaiera : 
    # ./zyvai a.p
10
    Voir la solution, si besoin


  3. Définir la structure des environnements, compte tenu du langage traité, il faudra concevoir un environnement en trois parties : definitions de fonctions et procédures, variables globales, et variables locales --- un enregistrement s'impose. Chacune des parties peut être mise en oeuvre à l'aide de listes (cf. le module List). Concevoir également les fonctions de base qui travaillent sur ces environnements, (chercher une variable par exemple). Il faut aussi se souvenir que l'on peut affecter les variables en Pseudo-Pascal.

  4. Étendre la fonction eval minimale pour tenir compte des variables globales, modifier l'évaluateur des expressions entières pour traiter le cas des variables, ainsi que l'évaluateur des instructions pout tenir compte de l'affectation de variable et de la séquence. Tester à l'aide d'un exemple simple, par exemple b.p. On obtiendra encore : 
    program
var x,s : integer ;
begin
   x := 0 ; s:= 0 ;
   x := x+1 ; s := s+x ;
   x := x+1 ; s := s+x ;
   x := x+1 ; s := s+x ;
   x := x+1 ; s := s+x ;
   writeln(s)
end.


    # ./zyvai b.p
10
    Voir la solution, si besoin


  5. Attaquez vous ensuite aux appels de fonction et de procédure, c'est à dire principalement traiter la gestion de la partie locale de l'environnement. Compléter enfin l'interprète en traitant toutes les constructions et notamment les tableaux. Vous pouvez à tout moment lancer une procédure de test complète, par ``make oki''. L'interprète est alors lancé sur une série de programmes (fact.p, ...) en prenant une série d'entrées (fact.in, ...) et sa sortie est confrontée à une sortie de référence (fact.ref, ...). L'ensemble des fichiers utiles aux tests se trouve dans le sous-répertoire test.

  6. Terminer par les aspects esthétiques : beau code, belle gestion des erreurs. La gestion des erreurs, fera la part des erreurs dans le programme interprété et des eventuels bugs de l'interpréteur (par exemple, en cas d'erreur d'indice dans un tableau, mieux vaut un message un peu explicatif qu'un accès illégal en Caml).
Voir la solution complète
Ce document a été traduit de LATEX par HEVEA.