TD 3 - Interprète mini-Pascal

Le but de ce TD est de réaliser un interprète pour un fragment très simple de Pascal, appelé mini-Pascal ; il n'est pas nécessaire de connaître le langage Pascal.

Afin de vous aider à construire cet interprète, nous vous fournissons sa structure de base (sous la forme d'un ensemble de fichiers Caml et d'un Makefile) que vous pouvez récupérer ici : mini-pascal.tar.gz. Une fois cette archive décompressée avec tar zxvf mini-pascal.tar.gz, vous obtenez un répertoire mini-pascal/ contenant les fichiers suivants :

ast.mli la syntaxe abstraite de mini-Pascal (complet)
lexer.mll l'analyseur lexical (complet)
parser.mly l'analyseur syntaxique (complet)
interp.ml l'interprète, (à compléter)
main.ml le programme principal (complet)
Makefile pour automatiser la compilation (complet)

Comme pour le TD 2, le code fourni compile mais est incomplet. L'exécutable s'appelle mini-pascal et s'applique à un fichier mini-Pascal portant le suffixe .pas, ainsi : 

  ./mini-pascal fichier.pas
Un fichier mini-Pascal a la structure suivante : 
  program test;      (* nom du programme *)
  var x,y : integer; (* variables globales *)
      tmp : integer;
  procedure minmax();  (* ceci est une procédure sans argument *)
  begin
    if x > y then begin tmp := x; x := y; y := tmp end
  end;
  procedure fact(n : integer); (* ceci est une procédure avec un argument n *)
  var f : integer; (* variable locale à f *)
  begin
    f := 1;
    while n > 1 do begin f := n * f; n := n - 1 end;
    writeln(f)
  end;
  begin  (* ceci est le programme principal *)
    x := 10; y := 2; minmax(); writeln(x);
    fact(10)
  end.
Plus généralement, un fichier mini-Pascal est composé d'une déclaration optionnelle de variables globales, suivie d'une liste optionnelle de déclarations de procédures, suivie d'un programme principal. Il y a un seul type, integer. Les instructions sont : l'affectation (d'une variable globale, d'un paramètre ou d'une variable locale), la conditionnelle (if then ou if then else), la boucle (while do), le bloc begin end ou l'appel de procédure. Les expressions entières sont : une constante, l'accès à une variable, ou l'une des quatre opérations arithmétiques +, -, * et /. Dans la conditionnelle et la boucle, la condition booléenne est construite à partir de comparaisons d'expressions entières (=, <>, <, <=, >, >=) et des trois opérateurs logiques and, or et not.

Pour rendre les programmes plus intéressants, on considère deux procédures primitives : writeln(e), qui affiche l'entier e suivi d'un retour-chariot ; et drawline(x1,y1,x2,y2) qui ouvre une fenêtre graphique si besoin et trace une ligne du point (x1,y1) au point (x2,y2). Ces primitives sont déjà programmées dans le code fourni.

Question 1. Expressions arithmétiques

On ne considère pour l'instant que les expressions arithmétiques ne contenant pas de variable. Compléter la fonction expr pour interpréter ces expressions. (On ignorera pour l'instant le premier argument env de la fonction expr.) Tester sur le programme suivant : 
program test;
begin
   writeln(1+2*3);
   writeln((3*3 + 4*4)/5);
   writeln(10-3-4)
end.
dont le résultat doit être 
7
5
3

Question 2. Variables globales

On rajoute maintenant le traitement des variables globales. Pour cela, on a déclaré une table globals pour les variables globales : 
let (globals : (string, int) Hashtbl.t) = Hashtbl.create 17
Dans cette table, on peut ajouter la nouvelle liaison de la chaîne x à la valeur v avec Hashtbl.add globals x v et chercher la valeur liée à x avec Hashtbl.find globals x.
  1. Dans la fonction expr, ajouter le traitement d'une variable globale.
  2. Dans la fonction stmt interprétant les instructions, ajouter le traitement de l'affectation d'une variable globale. Note : la fonction stmt a le type env -> stmt -> env où le premier argument et le résultat seront exploités pour la gestion des variables locales (question 4) ; d'ici là, on se contentera de passer cette valeur aux fonctions expr, condition et stmt sans la modifier, et de la faire renvoyer par la fonction stmt.
Tester sur le programme suivant : 
program test;
var
   x,y : integer;
begin
   x := 3;
   writeln(2*(x+2));
   y := 4;
   writeln(x*x + y*y)
end.
dont le résultat doit être 
10
25
On n'oubliera pas de donner une valeur initiale à toute variable globale déclarée (par exemple 0). Pour cela, il faut compléter la fonction prog en remplissant la table globals avec toutes les variables globales déclarées. La liste de ces variables est dans p.globals ; on pourra la parcourir avec List.iter.

Question 3. Expressions booléennes, conditionnelle et boucle while

Compléter la fonction condition qui interprète une expression booléenne. Puis compléter la fonction stmt pour interpréter la conditionnelle (construction Sif) et la boucle while (construction Swhile).

Tester sur le programme suivant : 

program test;
var
   n,f : integer;
begin
   n := 10;
   f := 1;
   while n > 1 do begin f := n * f; n := n - 1 end;
   writeln(f)
end.
dont le résultat doit être 
3628800

Question 4. Procédures

Pour terminer, on va ajouter le traitement des procédures. Ces dernières sont stockées dans la table globale ainsi déclarée : 
let (procs : (string, procedure) Hashtbl.t) = Hashtbl.create 17
Compléter la fonction prog pour qu'elle remplisse cette table avec les procédures contenues dans la liste p.procs.

Pour gérer les variables locales (et paramètres) on va utiliser un environnement, à savoir une table d'association persistante, passée aux fonctions expr, condition et stmt sous la forme d'un argument env, et associant à chaque variable locale sa valeur (un entier). Cette table d'association est réalisée avec le module Map de Caml, ainsi : 

module Smap = Map.Make(String)
Compléter la fonction expr pour que l'on puisse accéder aux variables locales. De même, compléter la fonction stmt pour que l'on puisse affecter une variable locale. Attention : dans expr comme dans stmt, il faut considérer les variables locales avant les variables globales.

Enfin, compléter la fonction stmt pour interpréter un appel de procédure. Pour un appel de la forme p(e1,...,en), à une procédure p de la forme procedure p(x1,...,xn); var l1,...,lm; begin body end; il faut construire un nouvel environnement qui associe à chaque argument formel xi la valeur de ei et qui contienne les variables locales lj (initialisées à 0 par exemple). On peut alors interpréter l'instruction body (le corps de la procédure) dans ce nouvel environnement. Une fois que cela est fait, on jette l'environnement qui en résulte et on reprend l'environnement qui était celui juste avant l'appel de procédure.

Tester sur le programme donné au début du sujet, dont le résultat doit être : 

2
3628800

Question 5. Graphisme

solution
retour à la page du cours