Projet de compilation: typer

Description de l'étape

Vous devez écrire un vérificateur de types, conforme aux règles de validité du typage de Drei.

Vous devrez définir des structures de données pour les concepts utilisés dans la représentation formelle de ces règles (types, symboles, portées; vous avez déjà l'AST).
Vous implanterez la classe d'analyse de type elle-même. Celle-ci doit détecter toutes les erreurs de type présentes dans le programme, la détection de la première erreur n'est pas suffisante. Si une définition contient une erreur, vous considérerez cette définition comme inexistante pour la suite de l'analyse du programme. Si le programme est correct (bien typé), l'analyseur retourne sans erreur.
Vous vous assurerez également que chaque nom dans l'AST est doté d'un symbole valide (nécessaire pour l'étape suivante).

Structures de données

Les types et les symboles sont représentés par une classe case pour chaque cas. N'oubliez pas de définir tous les champs requis dans chaque cas.

Un canevas pour les classes de symboles est à votre disposition.
Les portées sont des dictionnaires de noms vers des symboles. Vous pouvez utiliser la classe Map de la librairie, une fonction partielle etc.
Si jusqu'à présent vous avez décris les noms comme de simples chaînes de caractères (instances de la classe Name), cette étape verra l'introduction du concept de symbole. Le symbole est une représentation plus précise (deux symboles différents peuvent avoir le même nom) et plus complète (les symboles sont annotés avec leurs types) de la même notion. Notez que deux noms qui représentent la même chose doivent référencer la même instance de symbole, une égalité structurelle n'est ici pas suffisante.

L'AST ne contient actuellement que des noms, les symboles n'existant que dans les portées qu'utilisera votre analyseur. Mais dans la phase suivante, les symboles devrons également êtres disponibles dans l'arbre. Etendez pour cela la classe Name afin qu'elle contienne également un symbole, que vous définirez pour chaque nom lors de l'analyse.
```
case class Name(name: String) {
  var sym: Symbol
}
```
sym

Après la phase d'analyse: l'instance symbole spécifique à la classe, au champ, à la méthode ou à la variable définie par le nom, avant toujours null.

Analyseur de types

L'analyseur de types va vérifier que toutes les prémisses des règles d'inférences sont correctes (dérivable en des axiomes) sur le programme analysé. A partir de la règle «Program», l'analyseur procédera à une descente récursive à travers l'AST, guidé par les règles de typage, jusqu'à atteindre des axiomes. Si l'une ou l'autre règle ne peut vérifier ses prémisses, une erreur sera générée (mais n'oubliez pas que l'analyse doit continuer quand même).

Attention toutefois.

L'analyse de la définition des membres requiert que toutes les classes aient étés analysées (un membre peut être du type d'une classe définie après celle qui le contient).
L'analyse du corps des méthodes requiert que toutes les définition des membres de toutes les classes aient étés analysées (le corps d'une méthode peut contenir une référence à un membre défini plus tard).

Cela n'est pas un problème dans la définition formelle du système de type: la notion d'ordre d'exécution n'y est pas définie. Vous devrez donc contourner ce problème en cachant le fait que votre analyseur s'exécute d'après un ordre bien défini.

La solution la plus simple est de diviser votre analyse en trois «tranches» distinctes.

L'introduction des symboles de classes dans la portée des classes, et la définition de la super-classe éventuelle (notez ici qu'une classe ne peut pas étendre une classe définie après elle).
L'introduction des symboles des membres dans la portées des membres de chaque classe.
La validation du corps des méthodes.

Vous constaterez que la séparation se fait au niveau des règles «Program», «Class1», «Class2» et «Method» chaque tranche vérifiant une partie des prémisses.

Les plus téméraires (et eux seuls) pourront essayer d'implanter l'algorithme avec des valeurs gelées (lazy) plutôt que des tranches.

Définissez l'analyseur comme une classe avec l'interface suivante.

class Analyzer {
  def analyzeProgram(tree: Program): Unit
}

analyzeProgram: Un méthode qui analyse l'AST tree. Cette méthode retourne toujours, mais génère en effet de bord une liste des erreurs de types détectées dans l'AST.

Vous aurez intérêt à définir d'autres méthodes analyze…(…), au moins pour chaque catégorie de règles de typage (programmes, membres, expressions, etc.). Inspirez-vous de la «forme» de ces catégories de règles pour définir les paramètres de ces méthodes.

Un canevas pour cette classe est à votre disposition.

Soyez attentif à la difficulté qu'il y a à implanter l'entier du système de type en une seule étape. Préférez une approche modulaire: implantez un sous-ensemble minimal des règles (permettant la définition des classes et champs, par exemple, similaire au contenu du cours «analyse de noms») et testez celles-ci. Ajoutez ensuite les règles les unes après les autres, en testant à chaque étape.

Notez bien que vos programmes devront dorénavant être correctement typés pour êtres acceptés par votre compilateur. En particulier, les chaînes de caractères ne pourront êtres acceptées que si des classes définissant les listes existent. Une implantation des listes en Drei est à votre disposition.

Autres classes de support

AnalyzerTest.scala

Cet objet permet de tester votre analyseur de types, à condition que l'interface de celui-ci corresponde. A l'exécution

son premier paramètre est le fichier source du programme à analyser,
son second paramètre, optionnel, est le fichier de destination pour l'impression du résultat.

Ecole polytechnique fédérale de Lausanne

Laboratoire des méthodes de programmation