Projet du cours de construction de compilateurs: Typer

Description de l'étape

Vous devez implanter un vérificateur de types conforme aux règle de la spécification de Vier.

Vous devez 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 devez implanter 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.
Chaque noeud de l'AST contenant un nom doit être doté d'un symbole valide (nécessaire pour l'étape suivante).

A propos des symboles

Si jusqu'à présent vous avez décris les noms comme de simples chaînes de caractères, 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.

Les symboles sont représentés par une classe case pour chaque cas.
Pour les types, vous pouvez soit réutiliser les types syntaxiques de l'AST, ou définir un autre type de types pour les types analysés (typiquement).
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.

Les portées sont des dictionnaires de noms ou de types (pour la portée des classes) vers des symboles. Vous pouvez utiliser la classe Map de la librairie, une fonction partielle etc. Définissez un alias de type pour les portée au lieu de parler de l'implantation concrète.

Symboles et AST

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. Pour ce faire, il existe différentes solutions, je décris ici celle utilisée dans l'implantation de référence (qui utilise l'héritage multiple de Scala).

Vous définissez un trait représentant les noeud de l'AST dotés d'un symbole:
```
trait Symbolic[S >: scala.Null <: Symbol] extends Tree { symbolic =>
  private var symCache: S = null
  def setSym(sym: S): symbolic.type = {
    symCache = sym
    symbolic
  }
  def sym = if (symCache != null) symCache else throw new Error
}
```
La déclaration du type est un peu complexe, mais en gros S est un paramètre de type du trait qui définit quel type de symbole (de classe, de champ, etc) le noeux de l'AST attend.
Les classes case de l'AST qui définissent un symbole sont ensuite modifées pour étendre Symbolic:
```
case class Ident(name: String) extends Expr with Symbolic[ParamSymbol]
```
Dans votre analyseur, il suffit d'appeler la méthode setSym sur tous les noeuds symboliques de l'AST dès que le symbole correspondant est prêt.

Un canevas pour les classes de symboles et le type des portées est à votre disposition.

Analyseur de types

Le document Vier: syntaxe abstraite et règles de typage (2 p.p., 4 p.p.) contient un tas d'information utile sur l'implantation de l'analseur.

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

class Analyser {
  def validProgram(program: Program) : Unit
}

validProgram: Un méthode qui analyse l'AST program par rapport au jugement “validité d’un programme” de la spécification. 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 au moins pour chaque jugement de typage (héritage, membres, expressions, etc.).

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 expressions simples par exemple) 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 Vier est à votre disposition.

Autres classes de support

AnalyserTest.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