L'objectif de ce TP est d'étendre le langage A6000 avec des tableaux alloués dans la mémoire dynamique (c'est-à-dire le tas). On manipulera les tableaux avec trois opérations de base :

Un tableau contenant des éléments de type ty a un type noté []ty (mais on ne s'occupera pas encore à cette séance de la vérification des types).

Voici un exemple de programme complet : 

    main(integer x) (
      var []integer tab;
      var integer i;
      tab := [x+1]integer;
      tab[0] := 1;
      tab[1] := 1;
      i := 2;
      while (i <= x) (
        tab[i] := tab[i-1] + tab[i-2];
        i := i + 1;
      )
      print(tab[x]);
    )

1. Description

1.1. Extension du langage source

1.1.1. Lexique

Le langage contient les nouveaux symboles terminaux [ et ].

1.1.2. Grammaire

La grammaire des emplacements ([location]) est étendue d'une nouvelle production pour l'accès à une case d'un tableau 

      [location] ← ...
                 |  [expr] [ [expr] ]
et la grammaire des expressions est étendue d'une nouvelle production pour la création d'un nouveau tableau 
      [expression] ← ...
                   |  [ [expr] ] [type]
La grammaire des types est étendue d'une nouvelle production pour les types des tableaux 
      [type] ← ...
             |  [ ] [type]

1.1.3. Sémantique

Un tableau est constitué de cellules indicées à partir de 0 et contenant chacune une valeur.

Une expression [ e ]t produit un tableau non initialisé de valeurs de type t, dont la taille est donnée par l'expression e. Le résultat de cette expression est le tableau lui-même.

Une expression e₁[e₂] renvoie la valeur contenue dans la case d'indice donné par l'expression e₂ du tableau donné par l'expression e₁.

Une instruction e₁[e₂] := e₃ stocke la valeur de l'expression e₃ dans la case d'indice donné par e₂ du tableau donné par e₁.

1.1.4. Sémantique : précision supplémentaire

Le test d'égalité t == u entre deux tableaux ne s'intéresse pas au contenu des tableaux, mais à leur identité. Ainsi, après une initialisation comme 

  var integer[] t;
  t := [1]integer;
  t[0] := 3;

  var integer[] u;
  tu := [1]integer;
  tu[0] := 3;
le résultat de la comparaison t == u doit être false, car les deux tableaux comparés sont des tableaux distincts, et donc des valeurs différentes.

Remarques :

1.2. Extension du compilateur

1.2.1. Syntaxes abstraites

Dans la syntaxe abstraite source SourceAst, on introduit deux nouveaux constructeurs :

Dans la syntaxe abstraite IrAst, on a un nouveau type access = value * value, et trois nouveaux constructeurs :

1.2.2. Représentation

Une donnée est soit une valeur (entière ou booléenne) comme précédemment, soit un pointeur vers une adresse du tas. Pour l'instant, rien dans la représentation des données ne distingue un cas de l'autre, excepté la convention que 0 ne peut pas être un pointeur valide. Comme précédemment, une donnée est donc représentée par un mot de 4 octets.

Le tas contient des blocs. Un bloc est composé d'un en-tête et d'un ou plusieurs champs.

  1. L'en-tête, de taille 4 octets, contient un entier indiquant le nombre de champs constituant le bloc.
  2. Les champs, chacun de taille 4 octets, sont en nombre égal au nombre donné par l'en-tête, et contiennent chacun une donnée. 
    |-----------|
    |           |    <- adresse + 4 + 4*n, début du bloc suivant 
  --|-----------|--
    | Champ n-1 |
    |-----------|
    |           |
    |    ...    |    <- données arbitraires
    |           |
    |-----------|
    |  Champ 0  |    <- adresse + 4, premier champ
    |-----------|
    |  En-tête  |    <- adresse du bloc, contient le nombre n de champs
  --|-----------|--

La valeur d'un tableau est l'adresse du premier mot de sa représentation en mémoire. La valeur d'un tableau est donc représentée en mémoire par un simple mot, comme toutes les autres données.

1.2.3. Gestion du tas

Dans la version de base, chaque bloc alloué dans le tas est placé immédiatement après le précédent, sans s'occuper de récupérer l'espace alloué à des tableaux qui ne sont plus utiles.

À chaque création d'un nouveau tableau, on fait un appel système sbrk selon la convention suivante :

Après cette séquence le registre $v0 contient l'adresse de début du bloc qui a été alloué.

2. Travail attendu

Vous devez étendre l'ensemble du compilateur pour intégrer ces nouveaux aspects :

3. Extensions

3.1. Vérification des bornes des tableaux

Modifier le code généré lors des accès aux tableaux (en lecture comme en écriture) afin d'interrompre le programme lorsque l'accès se fait en dehors des bornes.

3.2. Sucre syntaxique : boucles inconditionnelles

On veut permettre dans la syntaxe concrète du langage l'écriture de boucles inconditionnelles : 

  for i = 1 to 5 (
    print(i * i);
  )
Remarque : Remarquez qu'une telle boucle peut être simulée par une boucle conditionnelle (boucle while) en ajoutant quelques instructions pour la bonne gestion du compteur de boucle i. Il n'est donc pas nécessaire d'inclure de nouvelle construction dans la syntaxe abstraite, tout peut se faire par une règle supplémentaire lors de l'analyse syntaxique.

3.3. Tableaux initialisés

Il est agréable de pouvoir représenter directement dans le langage source un tableau contenant des valeurs données, par exemple avec une syntaxe de la forme 

{ 1; 8; 7; 1 }

Étendre le compilateur pour ajouter cette possibilité. Notez que seules les parties placées avant la représentation intermédiaire IrAst ont besoin d'être étendues.

3.4. Gestion du tas

Ajouter un système manuel ou automatique de gestion du tas.

Remarquez qu'il n'est pas nécessaire d'écrire à la main l'intégralité du gestionnaire en assembleur Mips. Vous pouvez à la place écrire un système de gestion de mémoire en A6000 et récupérer le code assembleur produit par votre propre compilateur.
Voir pour cela le TP bonus.

3.5. Égalité structurelle

L'égalité structurelle ne s'intéresse pas à l'identité d'un objet complexe comme un tableau, mais à son contenu. On propose ici une première approche pour implémenter un opérateur d'égalité structurelle. Une approche alternative sera proposée dans le TP 8.

3.5.1. Égalité structurelle restreinte

Ajouter au compilateur un opérateur =t tel que t =t u renvoie true si t et u sont deux tableaux de même taille dont les éléments sont égaux deux à deux (vis-à-vis de l'égalité classique ==), et false si les deux tableaux ont des tailles différentes ou que des éléments de même indice diffèrent.

Le code généré pourra échouer si l'un des opérandes n'est pas un tableau.

3.5.2. Égalité structurelle générale

Ajouter au compilateur un opérateur = d'égalité structurelle, tel que a = b renvoie true si et seulement si a et b représentent la même valeur logique (nécessite l'extension Distinction valeurs/pointeurs).

Autrement dit, si a et b sont des valeurs immédiates (entières ou booléennes), = est équivalent à ==, tandis que si a et b sont des tableaux, = renvoie true si et seulement si les tableaux ont la même taille, et pour tout i valide, a[i] = b[i]. Cet opérateur doit renvoyer false si les deux opérandes sont de genres ou de tailles incompatibles.

3.6. Distinction valeurs/pointeurs

Il est parfois utile de conserver quelques informations sur la nature des données présentes en mémoire, en particulier ici pour l'égalité structurelle et pour la gestion automatique de la mémoire.

Modifier la représentation des données pour permettre de distinguer les valeurs immédiates des pointeurs vers le tas. Il y a au moins deux techniques possibles :