===== V. Gestion de la table des symboles =====

==== Introduction ====

La table des symboles mémorise les informations relatives aux identificateurs d'un programme :
  * le nom
  * le type (simple, structuré, étiquette, fonction, tableau, paramètre formel d'une fonction)
  * le nombre de dimensions, les bornes inférieurs et supérieurs (pour chaque dimension) pour un tableau
  * le nombre d'arguments pour une fonction
  * le mode d'adressage pour un paramètre formel (valeur ou adresse)
  * l'emplacement mémoire (utilisé pour la génération de code)

Remplissage de la table des symboles--ou la collecte des informations--s'effectue dans les phases d'analyse et ces information sont utilisées dans toute les phases de compilation.  Donc, l'accès aux informations doit être le plus efficace (rapide) possible.

L'objectif de ce chapitre es d'organiser la table des symboles de façon à accéder rapidement aux informations.

Certaines notions présentes dans les langages de programmation doivent être prises en compte.  La structuration d'un programme en blocs, par exemple, où chaque bloc est une unité de programme pouvant contenir des déclarations de variables.  Ceci entraine la nécessité de gérer la portée (visibilité) des variables; c'est à dire, de connaître l'ensemble des blocs où la variable est définie (et peut être utilisée).

  begin
    var b
    begin
      var a,b
      ...
    end
    ...
  end

==== Table des Symboles Locaux ====

Une table des symboles locaux mémorise les informations relatives aux identificateurs associés à un certain bloc.  Les opérations à réaliser sur une table locale sont :
  * création
  * destruction
  * insertion d'un identificateur
  * recherche d'un identificateur
  * accès à un champ de l'enregistrement associé à un identificateur

^ Représentations Possibles ^ Forces/faiblesses ^
| tableau unidimensionnel | recherche lente |
| arbre binaire équilibré | accès nécessite des indirections |
| table de hashage (un tableau de pointeurs sur une liste d'enregistrements indexé par les valeurs d'une fonction de hashage) | recherche rapide et accès efficace |

==== Table de Symboles Globaux ====

Dans le cas de langages permettant une imbrication de blocs, il faut gérer le masquage (ou redéfinition locale) de variables. Exemple :

  programme e
    var a,b,c integer
    procedure f
      var a,b,c integer
      b=a+c
    procedure g
      var a, b integer
      procedure h
        var c,d integer
      procedure i
        var b,d integer
    procedure j
      var b,d integer

FIXME Rajouter dessin de l'arborescence des table par bloc de procédure. 

Conclusion : utiliser une pile de tables locales. Une implantation efficace consiste en
  * une pile pour les identificateurs.
  * une pile pour les blocs
  * une table de hashage pour accéder rapidement aux informations dans la pile d'identificateurs

FIXME Autre dessin à rajouter

Le chainage dans la table de hashage se fait en tête : lorsqu'on tente d'accéder à un identificateur défii dans plusieurs blocs imbriqués, on accède directement à l'identificateur don la déclaration est la plus récente (chaque identificateur pointe aussi sur un prédécesseur du même nom s'il en existe un...facilite la mise à jour de la table de hashage lorsqu'un bloc est dépilé).

=== Implantation des Enregistrements ===

Implantation des enregistrements associés aux identificateurs

== Mémorisation du Nom ==

  * __identificateur de longueur limitée__ : le nom peut être directement mémorisé dans un champ de l'enregistrement
  * __identificateur de longueur illimitée__ : on se ert d'une table pour stocker les caractères des noms. La table va contenir la concatenation de tous les noms d'identificateurs. L'enregistrement va contenir un pointeur sur le premier caractère et la longueur (nombre de caractères).

== Informations Relatives à 1 Tableau ==

On peut avoir:
  * nombre de dimensions limité ou non
  * borne inférieur fix ou non (C ou Fortran).

Dans le cas le plus complexe, l'enregistrement doit contenir un pointeur sur une structure spécifique :

| nombre de dimensions | borne inf. 1 | borne sup. 1| borne inf. 2 | ... |

----
[[compil_7| <= Génération de code intermédiaire]] [[compil_9| optimisation du code =>]]