Conception du compilateur - Table des symboles

La table de symboles est une structure de données importante créée et maintenue par des compilateurs afin de stocker des informations sur l'occurrence de diverses entités telles que des noms de variables, des noms de fonctions, des objets, des classes, des interfaces, etc. La table de symboles est utilisée à la fois par l'analyse et la synthèse parties d'un compilateur.

Une table de symboles peut servir les objectifs suivants en fonction de la langue utilisée:

Pour stocker les noms de toutes les entités sous une forme structurée à un seul endroit.
Pour vérifier si une variable a été déclarée.
Pour implémenter la vérification de type, en vérifiant que les affectations et les expressions dans le code source sont sémantiquement correctes.
Pour déterminer la portée d'un nom (résolution de la portée).

Une table de symboles est simplement une table qui peut être linéaire ou une table de hachage. Il gère une entrée pour chaque nom dans le format suivant:

<symbol name,  type,  attribute>

Par exemple, si une table de symboles doit stocker des informations sur la déclaration de variable suivante:

static int interest;

alors il devrait stocker l'entrée telle que:

<interest, int, static>

La clause d'attribut contient les entrées liées au nom.

la mise en oeuvre

Si un compilateur doit gérer une petite quantité de données, la table de symboles peut être implémentée sous forme de liste non ordonnée, ce qui est facile à coder, mais elle ne convient que pour les petites tables. Une table de symboles peut être implémentée de l'une des manières suivantes:

Liste linéaire (triée ou non triée)
Arbre de recherche binaire
Table de hachage

Parmi tous, les tables de symboles sont principalement implémentées sous forme de tables de hachage, où le symbole du code source lui-même est traité comme une clé pour la fonction de hachage et la valeur de retour est l'information sur le symbole.

Opérations

Une table de symboles, linéaire ou hachée, doit fournir les opérations suivantes.

insérer()

Cette opération est plus fréquemment utilisée par phase d'analyse, c'est-à-dire la première moitié du compilateur où les jetons sont identifiés et les noms sont stockés dans la table. Cette opération est utilisée pour ajouter des informations dans la table des symboles sur les noms uniques apparaissant dans le code source. Le format ou la structure dans lequel les noms sont stockés dépend du compilateur en main.

Un attribut d'un symbole dans le code source est l'information associée à ce symbole. Ces informations contiennent la valeur, l'état, la portée et le type du symbole. La fonction insert () prend le symbole et ses attributs comme arguments et stocke les informations dans la table des symboles.

Par exemple:

int a;

doit être traité par le compilateur comme:

insert(a, int);

Chercher()

L'opération lookup () est utilisée pour rechercher un nom dans la table des symboles afin de déterminer:

si le symbole existe dans le tableau.
s'il est déclaré avant d'être utilisé.
si le nom est utilisé dans la portée.
si le symbole est initialisé.
si le symbole a été déclaré plusieurs fois.

Le format de la fonction lookup () varie en fonction du langage de programmation. Le format de base doit correspondre à ce qui suit:

lookup(symbol)

Cette méthode renvoie 0 (zéro) si le symbole n'existe pas dans la table des symboles. Si le symbole existe dans la table des symboles, il renvoie ses attributs stockés dans la table.

Gestion de la portée

Un compilateur gère deux types de tables de symboles: a global symbol table accessible par toutes les procédures et scope symbol tables qui sont créés pour chaque étendue du programme.

Pour déterminer la portée d'un nom, les tables de symboles sont organisées selon une structure hiérarchique, comme illustré dans l'exemple ci-dessous:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

Le programme ci-dessus peut être représenté dans une structure hiérarchique de tables de symboles:

La table de symboles globale contient les noms d'une variable globale (valeur int) et de deux noms de procédure, qui doivent être disponibles pour tous les nœuds enfants indiqués ci-dessus. Les noms mentionnés dans la table des symboles pro_one (et toutes ses tables enfants) ne sont pas disponibles pour les symboles pro_two et ses tables enfants.

Cette hiérarchie de structure de données de table de symboles est stockée dans l'analyseur sémantique et chaque fois qu'un nom doit être recherché dans une table de symboles, il est recherché à l'aide de l'algorithme suivant:

d'abord, un symbole sera recherché dans la portée actuelle, c'est-à-dire dans la table des symboles actuelle.
si un nom est trouvé, la recherche est terminée, sinon elle sera recherchée dans la table des symboles parents jusqu'à ce que,
soit le nom est trouvé, soit la table de symboles globale a été recherchée pour le nom.