Compilation : partie 4

À présenter lors de la séance du 10 janvier 2003

Introduction

Le but de cette partie est d'ajouter la phase d'analyse sémantique au compilateur misc. Cette analyse sémantique effectue deux tâches : l'analyse des noms et l'analyse des types. Au même titre que l'analyse lexicale se basait sur la grammaire lexicale et l'analyse syntaxique sur la grammaire syntaxique, l'analyse sémantique se base sur la grammaire attribuée de misc, qui a été vue au cours.

L'analyse des noms consiste à associer à chaque identificateur du programme sa définition, et donc à vérifier que les identificateurs utilisés dans le programme sont effectivement définis.

L'analyse des types consiste à vérifier que les types des différentes parties du programme sont corrects.

Une fois l'analyse sémantique effectuée avec succès, la production de code pourra enfin commencer, car le programme sera garanti correct par rapport aux règles statiques du langage.

Analyse des noms

L'analyse des noms associe à chaque identificateur du programme sa définition. Pour ce faire, elle stocke directement dans l'arbre, dans chaque nœud contenant un identificateur, un symbole qui contient les informations relatives à l'identificateur. Cela signifie qu'il vous faudra ajouter un champ de type Symbol à ces classes de nœud.

Chaque symbole contient les informations suivantes :

Les différentes sortes de symboles sont définies dans la classe Kinds. Dans le cas de misc, il n'y en a que deux, chaque symbole représente soit une fonction (déclarée par un def), soit une variable (déclarée par un var).

L'analyse des noms vérifie également que les identificateurs utilisés sont préalablement définis, et qu'un même identificateur n'est pas défini plus d'une fois dans une portée. En misc, les portées suivantes existent :

Cela signifie, par exemple, qu'il est légal d'avoir un argument d'une fonction de même nom que la fonction elle-même.

Le langage misc dispose de 4 fonctions d'entrée-sortie prédéfinies, qui doivent faire partie de la portée principale du programme. Ces fonctions ont le profil suivant :

  1. Unit printInt(Int)
  2. Unit printChar(Int)
  3. Int readInt()
  4. Int readChar()
Pour cette partie, ces fonctions seront traitées exactement comme des fonctions normales, si on excepte bien entendu le fait qu'elles sont automatiquement définies. Ce n'est qu'au moment de la production de code qu'elles devront être traitées différemment.

Analyse des types

L'analyse des types calcule le type des différentes parties du programme et vérifie qu'ils sont corrects.

Les types existant en misc sont :

Ces types sont liés entre eux par une relation de sous-typage. Pour mémoire, un type B est un sous-type d'un autre type A si des valeurs de type B peuvent être utilisées partout où des valeurs de type A sont attendues. En misc, la relation de sous-typage est très simple : bottom est un sous-type de tous les autres types; le type List[B] est un sous-type de List[A] si et seulement si B est un sous-type de A; finalement, la relation de sous-typage est réflexive, c'est-à-dire que tout type est sous-type de lui-même. (En passant, on notera que cette relation est également transitive, et anti-symétrique et forme donc un ordre partiel). On écrit t1 <: t2 si t1 est un sous-type de t2.

Grâce à la relation de sous-typage, on définit le maximum de deux types t1 et t2, noté max(t1, t2), de la manière suivante :
t2 si t1 <: t2
max(t1, t2) = t1 si t2 <: t1
indéfini sinon

Le type bottom est utile pour donner un type à la liste vide, notée [] en misc. En effet, la liste vide peut être une liste de n'importe quoi, le type de ses éléments n'étant pas connu, et son type doit donc refléter cette propriété. En lui attribuant le type list[bottom], étant donné la relation de sous-typage décrite plus haut, on obtient le résultat désiré. Vous pouvez, pour vous en convaincre, vérifier que le type de la liste vide est un sous-type de list[list[int]] (par exemple), selon la relation de sous-typage énoncée plus haut.

Nœuds sans type

Certains nœuds ne possèdent pas de type, comme par exemple ceux correspondant aux définitions de fonction ou aux instructions while. A ces nœuds, il faut attribuer le pseudo-type NONE (défini dans la classe Type) qui représente l'absence de type.

Erreurs

Lors des phases précédentes, vous étiez autorisé à vous arrêter après la première erreur. Ceci n'est pas le cas pour cette phase; cette fois-ci, toutes les erreurs doivent être signalées.

Il peut arriver qu'à cause d'une erreur, il soit impossible de calculer le type d'un nœud. Dans ce cas, vous pouvez lui attribuer le type BAD définit dans la classe Type.

Fichiers

 Pour cette partie, nous vous fournissons les fichiers suivants :

Projet en Scala

Ajout de symboles aux arbres

Pour ajouter des symboles aux arbres, une solution simple consiste à simplement ajouter un champ sym aux nœuds qui en ont besoin. Par exemple, on pourrait réécrire la classe Ident comme suit : 

case class Ident(name: String) extends Tree with {
  var sym: Symbol = null;
}

L'ennui avec cette solution est qu'il n'est pas facile d'accéder au champ sym. Par exemple dans le code suivant : 

def foo(tree: Tree): Unit = {
  tree match {
    case Ident(name) => {
      tree.sym = identSym;
    }
  }
}
l'accès à sym n'est pas légal, car tree est de type Tree et sym n'est déclaré que dans la sous-classe Ident.

Pour remédier à ce problème, on peut déclarer un champ abstrait sym dans la classe de base Tree : 

abstract class Tree with {
  abstract var sym: Symbol;
  // ...
}

Grâce à cette déclaration, l'accès à sym décrit ci-dessus devient légal. Mais, cette définition de Tree implique que chaque sous-classe de Tree doit implémenter un champ sym. Pour pouvoir faire cela, il faut d'abord comprendre comment Scala gère les champs d'une classe.

En Scala, lorsque l'on déclare un champ x on définit en réalité deux méthodes d'accès nommées x et x_= et une valeur nommée x$. La déclaration suivante 

class Foo {
  var bar: Int = 32;
}
est donc équivalente à celle-ci 
class Foo {
  private var x$: Int = 32;
  def bar: Int = x$;
  def bar_=(value: Int): Unit = x$ = value;
}
et la déclaration suivante 
class Foo {
  abstract var bar: Int = 32;
}
est équivalente à celle-ci 
class Foo {
  abstract def bar: Int;
  abstract def bar_=(value: Int): Unit;
}
De plus chaque assignation à un champ est transformée en un appel à la méthode d'écriture x_=. Le code suivant 
(new Foo).x = 42;
est donc transformé en 
(new Foo).x_=(42);

Pour implémenter le champ sym dans une sous-classe de Tree qui en possède effectivement un, on fait comme avant en déclarant simplement un champ concret. Par exemple, pour Ident on fait comme suit : 

case class Ident(name: String) extends Tree with {
  var sym: Symbol = null;
}

Pour les sous-classes de Tree qui ne possèdent pas de champ sym, il faut implémenter les deux méthodes sym et sym_= de façon à lever une exception. Voici un exemple : 

case class While(cond: Tree, body: Tree) extends Tree with {
  def sym: Symbol = Error("This tree node has no symbol: " + this).throw;
  def sym_=(s: Symbol): Unit = Error("This tree node has no symbol: " + this).throw;
}

L'ennui avec ça, c'est qu'il faut copier le code de ces deux méthodes dans toutes les sous-classes de Tree qui n'ont pas de champ sym. Pour éviter cela, on peut utiliser les mixins de Scala. Pour cela, on commence par déclarer les deux classes suivantes : 

class NoSymbol with {
  def sym: Symbol = Error("This tree node has no symbol: " + this).throw;
  def sym_=(s: Symbol): Unit = Error("This tree node has no symbol: " + this).throw;
}

class HasSymbol with {
  var sym: Symbol = null;
}

Ces deux classes contiennent les deux implémentations du champ abstrait sym dont nous avons besoin. Il ne reste plus qu'à les intégrer aux différentes sous-classes de Tree. Pour cela, on déclare simplement que les différentes sous-classes héritent à la fois de Tree et de l'une des deux classes ci-dessus. Par exemple, Ident et While sont déclarées comme suit : 

case class Ident(name: String) extends Tree with HasSymbol;
case class While(cond: Tree, body: Tree) extends Tree with NoSymbol;

Dans ces deux déclarations, les classes HasSymbol et NoSymbol sont des mixins, car elles sont utilisées comme des superclasses additionnelles ; leur code s'ajoute à celui fournit par la superclasse principale Tree. Lorsqu'une classe Scala est déclarée avec plusieurs superclasses, elle hérite de toutes les méthodes déclarées par toutes ces superclasses. Si une méthode est héritée de plusieurs superclasses, alors c'est l'implémentation fournie par la classe la plus à droite qui est retenue.

Représentation textuelle des types

Afin de pouvoir produire des message d'erreur à propos des erreurs de type, il faut pouvoir afficher un type sous forme textuelle. Dans la version Java, cela se fait simplement en redéfinissant la méthode toString de la classe Type. En Scala, on aimerait faire la même chose en redéfinissant la méthode toString de la classe Type définie dans le module Type. Malheureusement, cela n'est pas possible avec le compilateur Scala actuel. Le problème est que les sous-classes de la classe Type sont des classes cas et le compilateur Scala définit automatiquement une méthode toString pour chacune d'elle. Donc, si l'on appelle la méthode toString sur un type, c'est la méthode définie par le compilateur Scala qui sera appelée et non celle définie dans la classe de base Type. L'erreur du compilateur Scala est qu'il ajoute ces méthodes toString dans tous les cas, même si la classe de base en possède déjà une. Cela sera corrigé dans une future distribution.

Pour contourner le problème, deux solutions existent. La première est de définir une méthode toString dans chaque classe cas. Mais, c'est plutôt long et fastidieux et pas tellement dans l'esprit des classes cas. Une autre solution (celle que nous avons utilisée) consiste a utiliser un autre nom de méthode (nous avons choisi asString). Ainsi, on peut définir la méthode dans la classe de base en utilisant le filtrage de motifs. Le seul inconvénient de cette solution est qu'il faut se rappeler d'utiliser asString à la place de toString (si on se trompe, aucune erreur ne sera signalée, mais la représentation que l'on obtiendera ne sera pas la bonne).

Fichiers

Ci-dessous, les fichiers à utiliser pour le projet en Scala.

Cette partie est la dernière avant les vacances de Noël. Après la rentrée, nous traiterons la production de code à partir de l'arbre, ce qui nous occupera jusqu'à la fin du semestre.

Nous vous souhaitons à tous un joyeux Noël et une bonne année 2002.