Projet de compilation (Étape 2)

Samuel Tardieu

SE202 - Année scolaire 2016/2017

Deuxième étape

Avant de commencer

Avant de commencer à travailler, il vous faut intégrer le code venant de l'équipe pédagogique. Depuis votre dépôt :

% git pull template step2

À ce stade, votre dépôt a été enrichi de l'étape step2 du dépôt de référence. Vérifiez que les tests de base fonctionnent toujours :

% workon se202
(se202)% python -m unittest

La première commande fait appel à votre environnement de développement virtuel tiger, si ce n'était pas déjà fait. La seconde cherche tous les tests unitaires du dépôt et les exécute.

Travail à faire

Vous allez ajouter, avant la séance prochaine, les notions de

dans un nouveau visiteur Binder dont la partie commune vous est fournie dans semantics/binder.py. Toute erreur dans ce visiteur devra lever une exception de type BindException.

Vous rajouterez ensuite dans la grammaire :

Évaluation de l'arbre

Contrairement à l'étape précédente, il ne sera pas demandé d'enrichir le visiteur qui évalue l'arbre. En effet, le but n'est pas de faire un interpréteur Tiger mais un compilateur, donc nous ne ferons pas d'interprétation complète.

Variables et fonctions

Les variables et fonctions sont déclarées dans le corps d'un bloc let, avec les mots clés var et function, comme indiqué dans les transparents de cours.

Exemple :

let
  var a: int := 3
  var b := a + 1
  function add(x: int, y: int): int = x + y
in
  add(a + b, 3)
end

Les types sont facultatifs sauf pour la déclaration des paramètres d'une fonction.

Notes

Détection de listes (1 ou plus)

Comment faire dans la grammaire pour détecter des listes de 1 ou plusieurs déclarations (supposons que la règle pour une déclaration s'appelle decl et recouvre les déclarations de variable et de fonction) ?

def p_decls(p):
    '''decls : decl
             | decls decl'''
    p[0] = [p[1]] if len(p) == 2 else p[1] + [p[2]]

En testant la taille de la liste p, on peut distinguer si on est dans la première alternative de la règle (déclaration simple, len(p) == 2, et donc on construit une liste ne contenant que cette déclaration) ou dans la seconde (on construit une liste avec la liste correspondant à decls à laquelle on ajoute la nouvelle déclaration).

Détection de listes (0 ou plus)

Dans le cas des listes acceptant un nombre quelconque de termes (0 ou plus) séparés par un symbole (par exemple une virgule), la règle est un peu plus complexe car il ne faut pas se retrouver avec le séparateur seul. Par exemple, pour les arguments lors de l'appel d'une fonction :

def p_args(p):
    '''args :
              | argssome'''
    p[0] = p[1] if len(p) == 2 else []


def p_argssome(p):
    '''argssome : expression
                  | argssome COMMA expression'''
    p[0] = [p[1]] if len(p) == 2 else p[1] + [p[3]]

Profondeur et échappement

En Tiger, il est possible d'accéder depuis une fonction à une variable définie en dehors de cette fonction :

let
  var a := 3
  function f() =
    let
      function g() = a // a défini en dehors de g et f
    in
      g()
    end
in
  f()
end

Déclaration et visibilité

La visibilité des nouveaux identifiants diffère selon qu'il s'agit d'une variable ou d'une fonction :

let var a := 10 in
  let var a := a + 1 in  // Référence au a précédent
    a * 2                // Vaut 22
  end
end

Profondeur et échappement

Lorsqu'elle s'exécute sur le microprocesseur, une fonction a en général accès à :

Dans l'exemple précédent, g devra pour accéder à a déréférencer deux fois son static link: une fois pour accéder au contexte de f (qui englobe g) puis une seconde fois pour accéder au contexte contenant a.

Profondeur et échappement

Pour faciliter la génération de code et calculer ces déréférencements, on procèdera lors de l'analyse sémantique à différentes opérations :

Profondeur et échappement

Lors de la génération de code, le compilateur pourra librement choisir de stocker une variable en mémoire ou dans un registre (pour un accès plus rapide). Cependant, si la variable doit être accédée à travers le static link, elle doit nécessairement se trouver en mémoire, les registres étant utilisés par la fonction courante.

Pour cela, chaque déclaration possède un attribut escapes qui sera positionné à True lors du parcours de l'arbre si la variable est accédée depuis une profondeur supérieure à celle de sa déclaration. Dans ce cas, on demandera au générateur de code (plus tard dans le projet) de toujours placer la variable en mémoire plutôt que dans un registre.

Scopes

Le visiteur qui parcourt l'arbre pour effectuer l'analyse sémantique maintient à jour une liste courante de scopes, des dictionnaires qui contiennent le nom des variables définies et pointent vers leur définition.

Le fichier semantics/binder.py contient des méthodes permettant de commencer un nouveau scope, d'ajouter un nom dans le scope courant et de faire une recherche. De plus, ces fonctions se chargent de positionner les attributs depth et escapes des déclarations et des identifiants.

Appels de fonction

L'analyseur sémantique devra également vérifier, pour chaque appel de fonction (nœuds FunCall), que :

Tests

Le visiteur d'affichage parser.dumper.Dumper s'est doté d'un nouveau paramètre dans son constructeur : un champ semantics (par défaut à False) qui, s'il est mis à True, doit afficher des informations complémentaires (uniquement pour les déclarations de variables et l'utilisation de ces variables, pas pour les déclarations ni les appels de fonction) :

Tests

Par exemple, le code

let var a := 3
    function f() = let function g() = a in g() end
in f() end

s'affichera comme

let var a/*e*/ := 3
    function f() = let function g() = a/*2*/ in g() end
in f() end

Tests

Autre exemple :

let var a := 3
    var b := 4
    function f(c: int) = a + c
in f(b) end

donnera :

let var a/*e*/ := 3
    var b := 4
    function f(c: int) = a/*1*/ + c
in f(b) end

car b n'est pas utilisé à une profondeur de déclaration de fonction supérieure à sa déclaration.

Commentaires

On modifiera le parseur Tiger pour ignorer les commentaires :

Commentaires : implémentation

Pour implémenter les commentaires imbriqués, on pourra utiliser les états (states) de Ply dans le lexer :

Du coup, si on a par exemple trois niveaux imbriqués de commentaire, trois états ccomment seront placés sur la pile des états et devront être enlevés avant de revenir à l'analyse classique.

Moins unaire

On ajoutera au parseur Tiger la gestion de l'opérateur - unaire :

La documentation de Ply indique comment lui affecter une priorité différente de celle du - binaire (chercher UMINUS).

 % ./tiger.py -d -e -E "-17+1"
 ((0 - 17) + 1)
Evaluating: -16