Un interprète Pseudo-Pascal

Voici le cours correspondant. La solution se trouve dans le fichier interpretPP.ml.

Présentation

Ce TD se présente comme le précédent: l’exercice consiste à écrire un morceau manquant pour un programme par ailleurs déjà complet. Cette fois, le programme en question est le petit compilateur de Pseudo-Pascal vers l’assembleur MIPS, et le morceau manquant est l’interprète de Pseudo-Pascal.

On souligne bien le fait qu’un compilateur ne contient habituellement pas d’interprète du langage source, car cela n’est pas utile. Le petit compilateur est un peu particulier: il contient un interprète pour chacun des langages intermédiaires qu’il utilise. Cela permet d’interpréter le programme obtenu à n’importe quel point de la chaîne de compilation, et de vérifier qu’il se comporte de façon identique au programme source. C’est donc un outil de debugging relativement utile.

Il faut télécharger puis dépaqueter l’archive td2.tar.gz: 

# tar xvfz td2.tar.gz
# cd td2
# make
...
ocamlopt.opt -o compilo ...

Cependant, l’interprète ainsi produit ne fonctionne pas : 

# ./compilo -ipp test/a.p
Fatal error: exception Failure("UNIMPLEMENTED")

Vous noterez l’utilisation de l’option -ipp pour appeler l’interprète du langage Pseudo-Pascal.

Le fichier interpretPP.ml contient un interprète extrêmement incomplet qui ne traite que très peu de formes d’expressions et d’instructions.

Vous pouvez vérifier qu’il fonctionne pour le programme ultra minimal trivial.p:

program begin writeln(10) end.

On obtient: 

# ./compilo -ipp test/trivial.p
10

Ce qu’il faut faire

L’implémentation interpretPP.ml doit être conforme à l’interface interpretPP.mli.

Elle doit donc fournir une fonction interpret qui, étant donnée une valeur de type PP.program, c’est-à-dire un arbre de syntaxe abstraite représentant un programme, l’exécute. Cette fonction ne renverra aucun résultat, mais son exécution pourra avoir des effets de bord: par exemple, elle pourra afficher une chaîne de caractères sur la sortie standard si le programme Pseudo-Pascal fourni contient une instruction writeln. C’était le cas de trivial.p ci-dessus.

On tiendra compte du fait que le programme Pseudo-Pascal fourni est supposé bien typé. Certaines erreurs seront donc impossibles: par exemple, l’opération d’addition sera toujours appliquée à deux arguments entiers. Cependant, toutes les erreurs ne sont pas éliminées par le typage: par exemple, déréférencer un pointeur nul, ou bien accéder à un tableau en dehors de ses bornes, reste possible. On veillera à distinguer les erreurs qui ne doivent pas se produire (que l’on signalera par assert false) de celles qui peuvent se produire (que l’on signalera en levant l’exception RuntimeError).

Pour compléter le fichier interpretPP.ml, on s’appuiera sur la syntaxe abstraite du langage Pseudo-Pascal, définie formellement dans PP.mli, et sur la description de la sémantique formelle donnée dans le cours.

On suggère la démarche suivante:

  1. Augmenter la définition du type des valeurs (value), qui au départ ne contient que les valeurs entières, pour y ajouter les valeurs booléennes. On traitera les valeurs de type tableau plus tard.
  2. Définir l’évaluation des expressions arithmétiques, sans traiter pour le moment les cas EGetVar, EFunCall, EArrayGet, EArrayAlloc. Pour cela, on étend la fonction interpret_expression pour prendre en compte les cas EUnOp, EBinOp et EConst. On prendra garde à écrire ce code de façon aussi compacte et élégante que possible.

    On peut alors essayer cet interprète minimal en lui proposant un programme très simple, par exemple trivial2.p :

    program begin writeln(1+2+3+4) end.

    On obtient: 

    # ./compilo -ipp test/trivial2.p
10
  3. En vue de traiter correctement les références aux variables, globales et locales, il faut comprendre la notion d’environnement. Étudiez la définition du type environment, et notez que l’on utilise deux environnements, genv et env, pour les variables globales et locales, respectivement.

    Définir une fonction lookup qui recherche une variable (désignée par son nom) successivement dans ces deux environnements, et qui renvoie non pas le contenu de la variable mais son adresse.

  4. Ajouter le cas EGetVar à interpret_expression et le cas ISetVar à interpret_instruction. On utilisera bien sûr la fonction lookup.
  5. Modifier la fonction principale, interpret, pour passer une valeur appropriée de genv à la fonction interpret_instruction.

    À présent, on peut tester un exemple simple qui n’utilise que des variables globales, par exemple trivial3.p :

    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.

    On obtient encore: 

    # ./compilo -ipp test/trivial3.p
10
  6. S’attaquer ensuite aux appels de fonctions et de procédures, en complétant la fonction interpret_call. Cela nécessite principalement de gérer l’environnement env. On pensera à allouer les variables locales de la procédure ou fonction, ses paramètres, ainsi la variable spéciale qui stocke le résultat des fonctions.
  7. Implémenter interpret_condition. Traiter la conditionnelle et la boucle.
  8. Augmenter la définition du type value avec les valeurs de type tableau (cela mérite quelque réflexion) et compléter l’interprète en traitant toutes les constructions liées aux tableaux.

Vous pouvez à tout moment lancer une procédure de test complète à l’aide de la commande make test. L’interprète est alors lancé sur une série de programmes (fact.p, …) pour une série d’entrées fixées (fact.in, …). Le résultat obtenu sur la sortie standard est stocké dans un fichier (fact.ipp, …) qui est confronté au résultat attendu (fact.ispim, …). L’ensemble des fichiers utiles aux tests se trouve dans le sous-répertoire test.

Ce document a été traduit de LATEX par HEVEA