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

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

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

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

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 associés aux identificateurs

• 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).

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 :

<= Génération de code intermédiaire optimisation du code =>