TD 3 - Interprète mini-Python

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

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-python.tar.gz. Une fois cette archive décompressée avec tar zxvf mini-python.tar.gz, vous obtenez un répertoire mini-python/ contenant les fichiers suivants :

ast.mli	la syntaxe abstraite de mini-Python (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-python et s'applique à un fichier mini-Python portant le suffixe .py, ainsi :

  ./mini-python fichier.py

Un fichier mini-Python a la structure suivante :

# zéro, une ou plusieurs définitions de fonctions au début du fichier
def fibaux(a, b, k):
    if k == 0:
        return a
    else:
        return fibaux(b, a+b, k-1)

def fib(n):
    return fibaux(0, 1, n)

# une ou plusieurs instructions à la fin du fichier
print "quelques valeurs de la suite de Fibonacci :"
for n in [0, 1, 11, 42]:
    print fib(n)

Plus généralement, un fichier mini-Python est composé d'une liste optionnelle de déclarations de fonctions, suivie d'une liste d'instructions. Les instructions sont : l'affectation, la conditionnelle, la boucle (for), l'affichage d'une expression avec print, le renvoie d'une valeur avec return ou l'évaluation d'une expression. Les expressions entières sont : une constante (booléen, entier ou chaîne de caractères), l'accès à une variable, la construction d'une liste (avec la notation [e1, e2, ..., en), l'accès à un élément de liste (avec la notation e[i]), l'appel d'une fonction, ou une des opérations +, -, * et /, =, <>, <, <=, >, >=, and, or et not.

On considère également deux fonctions primitives: range(n) construit la liste [0, 1, 2, ..., n-1] et len(l) renvoie la longueur de la liste l.

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 ctx de la fonction expr.) Tester sur le programme suivant :

print 1 + 2*3
print (3*3 + 4*4) / 5
print 10-3-4

dont le résultat doit être

7
5
3

Les opérations division et modulo doivent signaler une erreur en cas de division par zéro. On utilisera pour cela la fonction error fournie dans le fichier interp.ml.

Pour tester facilement, on peut éditer le fichier test.py et lancer la commande make. Celle-ci compile l'interprète mini-python et le lance sur le fichier test.py.

Question 2. Expressions booléens et conditionnelles

Compléter les fonctions is_true et is_false, qui déterminent respectivement si une valeur est vraie ou fausse. En Python, la valeur None, le booléen False, l'entier 0, la chaîne vide "" et la liste vide [] sont considérées comme fausses et les autres valeurs comme vraies.

Compléter ensuite la fonction expr pour interpréter les constantes booléennes, les opérations de comparaison et les opérations and, or et not. En Python, la comparaison est structurelle ; on pourra utiliser directement la comparaison structurelle d'OCaml, c'est-à-dire utiliser des opérations comme < sur des valeurs de type value. Compléter enfin la fonction stmt pour interpréter la conditionnelle (construction Sif).

Tester sur le programme suivant :

print not True and 1/0==0
print 1<2
if False or True:
    print "ok"
else:
    print "oups"

dont le résultat doit être

False
True
ok

Question 3. Variables

Pour gérer les variables (du programme principal mais aussi les variables locales et paramètres) on va utiliser un environnement, à savoir une table de hachage passée aux fonctions expr et stmt sous la forme d'un argument ctx. Cette table associe à chaque variable sa valeur. Cette table d'association est réalisée avec le module Hashtbl d'OCaml et a donc le type:

  (string, value) Hashtbl.t

Compléter la fonction expr pour que l'on puisse accéder aux variables. C'est le cas de filtrage Eleft (Lident id). Tenter d'accéder à une variable qui ne se trouve pas encore dans la table doit provoquer une erreur. De même, compléter la fonction stmt pour que l'on puisse affecter une variable. C'est le cas de filtrage Sassign (Lident id, e1). Cette fois, la variable peut ou non se trouver dans la table. Dans le second cas, sa valeur est modifiée.

Enfin, compléter la fonction expr pour que l'on puisse concaténer deux chaînes de caractères avec l'opération +.

Tester sur le programme suivant :

x = 41
x = x+1
print x
b = True and False
print b
s = "hello" + " world!"
print s

dont le résultat doit être

42
False
hello world!

Question 4. Fonctions

On va ajouter maintenant le traitement des fonctions. Ces dernières sont stockées dans la table globale ainsi déclarée :

let functions = (Hashtbl.create 17 : (string, ident list * stmt) Hashtbl.t)

À chaque nom de fonction est associée une paire constituée de la liste des paramètres de la fonction et de l'instruction qui constitue le corps de la fonction. Compléter la fonction file pour qu'elle remplisse cette table avec les fonctions contenues dans la liste fl.

Compléter ensuite les fonctions expr et stmt pour interpréter un appel de fonction. Pour un appel de la forme f(e1,...,en), à une fonction f de la forme def f(x1,...,xn): body il faut construire un nouvel environnement qui associe à chaque argument formel xi la valeur de ei. On peut alors interpréter l'instruction body (le corps de la fonction) dans ce nouvel environnement. L'instruction return sera interprétée en utilisant l'exception OCaml Return (déjà définie).

Tester sur le programme suivant :

def fact(n):
    if n <= 1: return 1
    return n * fact(n-1)

print fact(10)

dont le résultat doit être

Question 5. Listes

Ajouter enfin le support des listes. Pour cela, compléter la fonction expr pour que l'on puisse concaténer deux listes avec l'opération +, pour interpréter l'appel aux primitives len (longueur d'une liste) et range (liste [0, 1, 2, ..., n-1]), et enfin pour interpréter les constructions [e1, e2, ..., en] et e1[e2]. (On pourra trouver utile d'introduire une nouvelle fonction OCaml pour évaluer une expression de type left_value.)

Compléter ensuite la fonction stmt pour interpréter l'affectation d'un élément de liste (cas de filtrage Sassign (Lnth (lv, e1), e2)).

Enfin, compléter la fonction stmt pour interpréter la construction for. La construction Sfor(x,e,s) affecte la variable x successivement aux différents éléments de la liste e et exécute à chaque fois l'instruction s. L'expression e doit être évaluée une seule fois.

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

Question 5. D'autres tests

Des tests positifs et négatifs sont fournis. Pour lancer votre interprète sur ces tests, faire make tests.

solution

retour à la page du cours