P3 — Interpréteur Python
L'objectif dans ce projet est de faire un interpréteur (pour un sous-ensemble de) Python. Pour ce projet on vous fournit une trame de code avec un parseur et un lexer mais ceux-ci ne sont pas complets, il ne gère qu'un petit ensemble du langage, vous aurez donc à modifier tous les fichiers sauf eval.ml (qui appelle lexer, parser et runtime) et ptipython.ml (qui parse la ligne de commande).
Voici les objectifs à compléter dans l'ordre.
Partie 0 - explication des parser et lexer (écouter le cours)
Partie 1 - expressions entières et print
Dans cette première partie, vous n'avez que le fichier runtime.ml à éditer
et vous ne devez supporter que les expressions entières (pas les
variables, pas les listes, pas les chaînes de caractères, pas les
comparaisons boolénnes, etc.), le seul appel de fonction à gérer est
celui de print donc Ecall("print",[e]) avec e une expression entière. Pour cela, il est fortement conseillé d'introduire une fonction eval_expr qui prend une expression et renvoie l'entier correspondant à l'expression évaluée. Notez que print est une fonction "particulière" dont le code n'est pas en python mais c'est à vous d'ecrire le code OCaml correspondant.Partie 2 - Expressions listes, chaînes, booléens
Dans cette seconde partie, vous n'avez toujours que le fichier runtime.ml à éditer
et vous ne devez supporter que toutes les expressions entières (mais pas les
variables). Le seul appel de fonction à gérer est toujours
celui de print donc Ecall("print",[e]) avec e une expression quelconque. Pour cela, il est fortement conseillé d'introduire un type values pour représenter les divers types de pythons. Attentions la sémantique des opérateurs (comme +) dépend du type. Pour toutes les opérations qui reçoivent des types incompatibles (comme + sur int et str ou comparaison entre deux types différents) on renverra une erreur. Pour les comparaisons sur les chaînes et les listes, on utilisera l'ordre lexicographique.
Partie 3 - Variables et boucle for
Dans cette troisième partie, vous n'avez toujours que le fichier runtime.ml à éditer. On veut maintenant rajouter des variables et les boucle for, on supposera qu'il n'existe pas de variables globales mais toutes les fonctions ont des variables locales. Si une variable est lue avant d'être écrite, on considèra qu'elle n'est pas définie et on lèvera une exception RuntimeError. Attention les variables sont locales à toute une fonction ! On n'essaiera ici pas de gérer les Sassign dans des tableaux mais seulement de gérer les affectations de variables.
Partie 4 - Fonctions
Dans cette quatrième partie, vous n'avez toujours que le fichier runtime.ml à éditer. On
veut maintenant supporter les définitions et appels de fonctions arbitraires. Une fois que cela est fait rajouter du code pour gérer les fonction type (qui renvoie une chaîne de caractères correspondant à un type) et len.
Partie 5 - If-then, if-then-else et while
Dans cette cinquième partie, vous avez (enfin !) à éditer d'autres fichiers que runtime.ml. On veut maintenant supporter les constructions if-then, if-then-else et while. Vous devrez donc modifier parser.mly pour ajouter des tokens correspondants aux mots clefs à introduire, puis lexer.mll pour qu'il reconnaisse ces tokens puis ast.ml et parser.mly pour ajouter des élèments à l'ast et les règles de grammaire produisant ces éléments et enfin il faudra modifier runtine.ml pour supporter ces constructions à l'exécution. Il est conseillé de travailler méthodiquement en ajoutant ces constructions l'une après l'autre.
Partie 5bis - Left values améliorée
On veut maintenant gérer des accès plus général aux listes et autoriser des expressions comme [0,1][0] etc. Pour cela on va changer ast.ml pour que le type left_value soit
and left_value =
| Tab of expr*expr
| Var of string
Modifier le parser et votre runtime pour gérer ce cas. Que renvoie le code suivant :
def f(x):
print(x)
f(0)[f(1)][f(2)] ?
Partie 6 - Variables globales
[Ce passage a été édité car il contenait une erreur] En Python, toutes les variables qui sont syntaxiquement modifées (s'il y a un x=... quelque part dans le corps de la fonction) sont considérées locales sauf si on introduit explicitement une variable comme globale avec le mot-clef global.
def f(): a=x+1 return a def h(): x=x+1 return x def g(): x=1 return x
x=42
print(f())print(x) print(g())print(x) print(h()) print(x)
Et voilà la sortie correspondante : 43 42 1 42 Traceback (most recent call last): File "/tmp/b.py", line 20, inprint(h()) File "/tmp/b.py", line 8, in h x=x+1 UnboundLocalError: local variable 'x' referenced before assignment
En effet les 4 premières lignes sont claires étant donnée la sémantique donnée, la 4 ème est plus subtile, Python voit une affectation sur x en déduit qu'elle est locale puis ensuite calcule sa valeur, ce qui échoue puisque x est local et n'a pas de valeur. Il ne vous est pas demandé de supporter ce cas étrange.
Partie 7 - Modification des tableaux
Dans cette partie, l'objectif c'est de gérer les modifications de tableaux et donc t[i] = j ou t[i][j] = k, etc.
Python, la portée des variables est dynamique. Si, dans une fonction, une variable x est lue avant d'être modifiée alors x est considérée comme une variable
Partie 8 - Extensions possibles
Voici une liste (non ordonnée) d'extensions que vous pouvez essayer de supporter :
- les compréhensions de liste comme [f(e) for e in ... ]
- les tuples
- le type range avec sa construction range() (qui ne servira qu'à itérer des boucles for)
- les itérateurs avec la syntaxe yield. Attention la sémantique des yield en python est un peu particulière (une fonction qui a syntaxiquement un yield est une fonction génératrice qui ne sera exécutée qui renvoie un objet de type
- gérer les fonctions comme des objets de premier ordre, c'est à dire que l'on peut stocker les fonctions dans des variables, les passer en arguments de fonctions, etc. Que se passe-t-il sur [print,len,print][0]([print,len,print][1]) ?
- trouver une manière acceptable pour que print fonctionne sur les listes infinies ; on pourra tronquer la sortie de print même quand la liste n'est pas infinie.
- 10 octobre 2023, 15:57