|
|
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 :
- la position à laquelle le symbole est déclaré,
- le nom du symbole,
- la sorte du symbole,
- le type du symbole.
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 :
- la portée globale du programme,
- une portée pour chaque liste d'arguments d'une fonction,
- une portée pour chaque bloc.
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 :
Unit printInt(Int)Unit printChar(Int)Int readInt()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 :
- le type unit (
Unit),
- le type entier (
Int),
- les types liste (
List[type]),
- les types fonctionnels (
(type, ...)type),
- le type
bottom (pour lequel il n'existe pas de
syntaxe concrète).
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 :
Type.java contient la
définition de la classe Type et de ses
sous-classes, qui modélisent les types misc. Ces classes
définissent, entre autres, des méthodes permettant de comparer
et de calculer le maximum de deux types. Les sous-classes
FunType, modélisant les types fonctionnels, et
ListType, modélisant les types listes, sont à
compléter. Kinds.java contient la
classe Kinds, qui définit toutes les sortes de
symboles. Symbol.java contient la
classe Symbol, qui modélise les symboles. Scope.java contient la
classe Scope, qui modélise les portées. Analyzer.java contient
le visiteur d'analyse sémantique. Il s'agit du principal fichier
à compléter. AnalyzerTest.java
contient le programme de test.
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.
Type.scala contient la
définition de la classe Type et de ses
sous-classes, qui modélisent les types misc. Ces classes
définissent, entre autres, des méthodes permettant de comparer
et de calculer le maximum de deux types. Les sous-classes
FunType, modélisant les types fonctionnels, et
ListType, modélisant les types listes, sont à
compléter. Kinds.scala contient le
module Kinds, qui définit toutes les sortes de
symboles. Symbol.scala contient la
classe Symbol, qui modélise les symboles. Scope.scala contient la
classe Scope, qui modélise les portées. Analyzer.scala contient
le visiteur d'analyse sémantique. Il s'agit du principal fichier
à compléter. AnalyzerTest.scala
contient le programme de test.
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.
|
