Dans l’article précédent, nous avons créé un arbre syntaxique. Nous allons maintenant analyser ce langage pour vérifier que notre programme est cohérent. Nous allons vérifier si les variables sont accessibles, si les types son correctement utilisés etc. Un langage peut être syntaxiquement correcte mais ne peux pas être exécuté car sa sémantique n’est pas correcte.

Exemple :

var i = x;

Dans ce code nous utilisons une variable « x » qui n’a jamais été définie avant.

Closure

L’un des premiers principes est la portée des variables. Le principe de closure est de définir le scope d’une variable. Par exemple, dans le cadre d’un langage tel que le C# nous pouvons écrire des lambda, et les lambda utilisent des variables de la méthode parente. Même après l’exécution de la méthode, les variables son toujours disponibles. C’est cette portée qui demande à être définie.

Pour simplifier mes variables son scopées sur la méthode courante et pas la méthode enfant. Ainsi le code suivant émet une erreur :

var x = 0;
var m = fun() -> x;

D’un point de vue du compilateur « x » n’est pas défini dans le scope de la sous méthode.

Par contre, dans mon langage j’ai souhaité gérer la redéfinition d’une variable. À tout moment je peux recréer une variable avec un autre type et dans la suite du programme on utilisera cette variable.

Exemple :

var i = 1;
var i = true;

Pour cela je recrée un scope pour la suite du programme. Ce que je veux c’est avoir un équivalent à :

var i = 1;
var i1 = true;

Je parcours mon arbre syntaxique et je le réécris en enlevant cette ambiguïté. Cela va me permettre de faire des checks de syntaxe plus intelligents dans la suite du langage.

L’analyse du typage

Une étape importante dans un compilateur est de vérifier le typage. Un langage de programmation peut avoir deux typages différents :

  • Typage fort : Le langage ne permet pas d’utiliser une variable entière pour stocker un booléen, un float, ou autre type. (C# par exemple)
  • Typage faible : Le langage permet de réutiliser une variable pour stocker différent type de valeur (Javascript par exemple)

Certains langages permettent un typage faible grâce à un mot clé. Exemple C# utilise le mot clé dynamic. Ainsi la variable définie par dynamic devient une variable avec un typage faible.

Qui veut dire typage fort, veut dire que le compilateur va vérifier les types. Il va donc vérifier que l’on ne met pas un entier dans une variable qui contient un booléen.

C’est-à-dire que nous allons vérifier si les types utilisés à chaque opération son compatibles entre eux. Exemple :

var i = 0;
var b = i + true;

Il est sémantiquement impossible dans ce langage d’additionner un entier avec un booléen. Certains langages ne poseraient pas de problème car ils considèrent un booléen comme un entier. C’est à vous de définir la sémantique que vous souhaitez mettre derrière le langage.

L’autre chose c’est le mot clé « var ». J’ai fait le choix dans ce langage de ne pas spécifier le type. Mais je suis quand même en typage fort. Ainsi, comme en F#, mon compilateur doit déduire le type par rapport à l’utilisation que l’on en fait. C’est ce que l’on appelle de l’inférence de type. Le principe est de déduire le type de l’utilisation. Nous allons parcourir notre arbre syntaxique pour en déduire le type des différents éléments.

Pour faire de l’inférence de type nous allons créer un nouvel arbre syntaxique. Cet arbre syntaxique va lui être identique au précédent mais avec un typage. Nous allons commencer par créer tous les types possibles :

typeTypeName=
|Typeofstring*(string*TypeName)list
|TypeInterfaceofstring*(string*TypeName)list
|TypeInt
|TypeFloat
|TypeBool
|TypeVoid
|TypeString
|TypeGenericofstring
|TypeFuncofTypeNameList*TypeName

Nous avons défini que nos éléments pouvaient être de type :

  • Objet avec des propriétés
  • Interface avec des propriétés
  • Entier
  • Float
  • Booléen
  • Void : pour les méthodes qui ne renvoient pas de valeur.
  • String : pour les chaines de textes.
  • Générique : Un type qui nous permet dans certain cas de dire que nous ne connaissons pas le type d’une variable. Mais ce type sera déduit plus tard. Il prend un nom unique au moment de sa création pour pouvoir l’identifier.
  • Fonction : pour le typage des méthodes.

Puis nous allons reprendre notre premier arbre en ajoutant des informations de typage. Ces informations de type seront importantes pour la génération de code IL plus tard.

Exemple pour la création de variables

Notre type Create(“maVariable“, _) va se transformer en :

|TypedCreateofTypeName*string*TypedExpression

Nous retrouvons le nom de notre variable, l’expression associée à la création, et un objet qui indique de quel type est la variable.

Pour cela nous parcourons notre arbre syntaxique avec le pattern matching de F# :

|Create(name,e)->
let(typeAccu,typeExpression,exp)=(checkTypeExpressionetypeAccu)
lettypeAccu=(name,typeExpression)::typeAccu
in(typeAccu,TypedCreate(typeExpression,name,exp))

Première ligne, nous allons évaluer notre arbre d’expression pour connaitre son type. Ainsi checkTypeExpression va nous renvoyer trois choses :

  • typeAccu : Un tableau contenant une liste de variables avec leurs types associés.
  • typeExpression : Le type déduit de l’évaluation de notre sous arbre d’expression.
  • exp : Le nouvel arbre d’expression typé.

Sur la deuxième ligne je rajoute dans ma liste de variables la nouvelle variable que je suis en train de créer. Ce qui me permet d’agrandir ma liste de mapping entre mes variables et leurs types.

Sur la troisième ligne je renvoie ma liste de variables et mon nouveau « TypedCreate ». Nous avons maintenant un nœud « TypedCreate » qui contient le type de notre sous arbre « exp ».

Autre exemple l’addition

Notre type Add(ex1, ex2) va se transformer en :

|TypedAddofTypeName*TypedExpression*TypedExpression

Nous retrouvons nos deux arbres d’expressions, et un autre objet qui détermine que c’est une addition d’un certain type.

De la même manière que pour le « Create », nous allons évaluer par pattern matching notre arbre et lorsque nous tombons sur un Add :

|Add(ex1,ex2)->
let(typeAccu,type1,ex1)=(checkTypeExpressionex1typeAccu)
let(typeAccu,type2,ex2)=(checkTypeExpressionex2typeAccu)
incompareTypetypeAccutype1ex1type2ex2

Première ligne, nous évaluons le premier sous arbre qui va nous renvoyer un type et le sous arbre de manière typé.

La deuxième ligne fait la même chose avec le deuxième sous arbre.

Puis nous allons comparer les types des deux sous arbres. Si les deux types sont identiques alors cela veut dire que le typage est cohérent. Dans ce cas-là, nous allons renvoyer notre nœud « TypedAdd ». Par contre si les deux types sont différents alors nous générons une erreur car le typage est incorrect.

Dans la liste des types, nous avons introduit la notion de type générique. Ce type permet de définir une variable sans connaitre son type au début. Cela nous permet de déduire le type des paramètres des méthodes. Exemple :

var f = fun(x) -> x + 1;

De son utilisation nous pouvons déduire que f est de type « TypeFun([TypeInt], TypeInt) » Mais au moment où nous parcourons l’addition de « x + 1 » le type de x sera « TypeGeneric » car nous ne connaissons pas le type. C’est pour cela que nous allons ajouter dans « typeAccu » la variable x avec un nouveau type générique.

Puis quand nous allons comparer les deux types, nous allons remplacer le type générique de la variable par le vrai type. Dans la méthode compare nous avons le code :

letcompareTypetypeAccutype1t1type2t2=
match(type1,type2)with
|(TypeGeneric(tg1),TypeGeneric(tg2))->
(replaceTypetypeAccutg2(TypeGeneric(tg1)),TypeGeneric(tg1),TypedAdd(TypeGeneric(tg1),t1,t2))
|(TypeGeneric(tg1),type2)->
(replaceTypetypeAccutg1type2,type2,TypedAdd(type2,t1,t2))
|(type1,TypeGeneric(tg2))->
(replaceTypetypeAccutg2type1,type1,TypedAdd(type1,t1,t2))
|(type1,type2)->
iftype1=type2then
(typeAccu,type1,TypedAdd(type1,t1,t2))
else
raise(TypeError("Expressionattheleftis"+(typeToStringtype1)+"andtherightis"+(typeToStringtype2)))

Il y a quatre cas :

  • Les types des deux sous arbres son génériques. Dans ce cas-là nous remplaçons le type générique 2 des variables par le type générique 1
  • Le type 1 est générique et pas l’autre. Dans ce cas-là nous remplaçons le type générique 1 des variables par le type 2.
  • Le type 2 est générique et pas l’autre. Dans ce cas-là nous remplaçons le type générique 1 des variables par le type 2.
  • Les deux types ne sont pas génériques. Nous vérifions qu’ils sont identiques. Si ils sont différents on renvoie une erreur.

Le principe de cela est de faire des remplacements de nos types génériques par les types déduits pendant l’évaluation de notre addition. Nous savons que si d’un côté nous avons un type générique et de l’autre un type, nous pouvons remplacer le type générique par l’autre type.

Optimisation d’arbre

Notre arbre syntaxique a été analysé et il est correct. Nous avons maintenant un typage de nos variables. Nous pouvons à ce moment évaluer notre arbre pour exécuter le programme. Si nous continuons à faire notre compilateur nous pouvons ajouter une phase d’optimisation de notre arbre syntaxique. Tous les compilateurs modernes sont capables de faire ce genre d’optimisation.

Dans mon compilateur, je n’ai pas encore implémenté d’optimisation mais voici quelques idées d’optimisation simples.

Le remplacement des variables

Une variable constante qui est lue qu’une seule fois peut être remplacée par sa valeur directement.

Exemple :

var i = 1;
var x = i + 2;

Nous pouvons remplacer ce code par un code similaire à :

var x = 1 + 2;

Évaluation

L’idée est d’évaluer un maximum notre code pour éviter qu’il soit fait à l’exécution. Ainsi, notre code n’évaluera pas l’addition à l’exécution.

Si on reprend le code :

var x = 1 + 2;

Alors il sera remplacé par :

var x = 3;

Suppression des variables

Les variables qui ne sont jamais lues, ne sont pas utiles dans l’exécution. Il n’est pas intéressant de stocker la valeur d’un calcul si celui-ci n’est pas utilisé.  Il faut éviter d’allouer de la mémoire pour rien et de faire des opérations d’affectations. Si je reprend le code :

var x= 3;

Nous pouvons supprimer la variable, et dans le même cas supprimer la constante 3. Attention, s’il s’agit d’une constante, il faudra supprimer non seulement l’affectation, mais aussi l’exécution de l’arbre d’expression.

Pour terminer

Pour terminer, il reste a regarder comment générer, à partir de notre arbre, du code MSIL pour qu’il soit exécutable.