Table des symboles - Symbol table

En informatique , une table de symboles est une structure de données utilisée par un traducteur de langage tel qu'un compilateur ou un interpréteur , où chaque identifiant (ou symbole) dans le code source d' un programme est associé à des informations relatives à sa déclaration ou à son apparition dans la source. En d'autres termes, les entrées d'une table de symboles stockent les informations relatives au symbole correspondant de l'entrée.

Fond

Une table de symboles peut n'exister qu'en mémoire pendant le processus de traduction, ou elle peut être intégrée dans la sortie de la traduction, comme dans un fichier objet ABI pour une utilisation ultérieure. Par exemple, il peut être utilisé lors d'une session de débogage interactive ou comme ressource pour formater un rapport de diagnostic pendant ou après l' exécution d'un programme.

La description

L'information minimale contenue dans une table de symboles utilisée par un traducteur comprend le nom du symbole et son emplacement ou son adresse. Pour un compilateur ciblant une plate-forme avec un concept de relocalisation, il contiendra également des attributs de relocalisation (absolus, relocalisables, etc.) et les informations de relocalisation nécessaires pour les symboles relocalisables. Les tables de symboles pour les langages de programmation de haut niveau peuvent stocker le type du symbole : chaîne, entier, virgule flottante, etc., sa taille, ses dimensions et ses limites. Toutes ces informations ne sont pas incluses dans le fichier de sortie, mais peuvent être fournies pour une utilisation dans le débogage . Dans de nombreux cas, les informations de référence croisée du symbole sont stockées avec ou liées à la table des symboles. La plupart des compilateurs impriment tout ou partie de ces informations dans la table des symboles et les listes de références croisées à la fin de la traduction.

Mise en œuvre

De nombreuses structures de données sont disponibles pour la mise en œuvre des tables. Les arbres, les listes linéaires et les listes auto-organisées peuvent tous être utilisés pour implémenter une table de symboles. La table des symboles est accessible par la plupart des phases d'un compilateur, en commençant par l'analyse lexicale et en continuant par l'optimisation.

Un compilateur peut utiliser une grande table de symboles pour tous les symboles ou utiliser des tables de symboles hiérarchiques séparées pour différentes portées . Par exemple, dans un langage étendu tel qu'Algol ou PL/I, un symbole "p" peut être déclaré séparément dans plusieurs procédures, peut-être avec des attributs différents. La portée de chaque déclaration est la section du programme dans laquelle les références à "p" résolvent cette déclaration. Chaque déclaration représente un identifiant unique "p". La table des symboles doit avoir un moyen de différencier les références aux différents "p".

Une structure de données courante utilisée pour implémenter les tables de symboles est la table de hachage . Le temps de recherche dans les tables de hachage est indépendant du nombre d'éléments stockés dans la table, il est donc efficace pour un grand nombre d'éléments. Il simplifie également la classification des littéraux sous forme de tableau en incluant la classification dans le calcul de la clé de hachage.

Comme l'analyseur lexical passe une grande partie de son temps à rechercher la table des symboles, cette activité a un effet crucial sur la vitesse globale du compilateur. Une table des mnémoniques doit être organisée de telle sorte que les entrées puissent être trouvées le plus rapidement possible. Les tables de hachage sont généralement utilisées pour organiser une table de symboles, où le mot-clé ou l'identifiant est « haché » pour produire un indice de tableau. Les collisions sont inévitables dans une table de hachage, et une façon courante de les gérer consiste à stocker le synonyme dans le prochain espace libre disponible dans la table.

Applications

Un fichier objet contiendra une table des symboles des identifiants qu'il contient et visibles de l'extérieur. Lors de la liaison de différents fichiers objets, un éditeur de liens identifiera et résoudra ces références de symboles. Habituellement, tous les symboles externes non définis seront recherchés dans une ou plusieurs bibliothèques d'objets . Si un module est trouvé qui définit ce symbole, il est lié avec le premier fichier objet, et tous les identifiants externes non définis sont ajoutés à la liste des identifiants à rechercher. Ce processus se poursuit jusqu'à ce que toutes les références externes aient été résolues. C'est une erreur si une ou plusieurs restent non résolues à la fin du processus.

Lors de la rétro-ingénierie d' un exécutable, de nombreux outils se réfèrent à la table des symboles pour vérifier quelles adresses ont été attribuées aux variables globales et aux fonctions connues. Si la table des symboles a été supprimée ou nettoyée avant d'être convertie en un exécutable, les outils auront plus de mal à déterminer les adresses ou à comprendre quoi que ce soit sur le programme.

Exemple

Considérons le programme suivant écrit en C :

// Declare an external function
extern double bar(double x);

// Define a public function
double foo(int count)
{
    double sum = 0.0;

    // Sum all the values bar(1) to bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

Le compilateur AC qui analyse ce code contiendra au moins les entrées de table de symboles suivantes :

De plus, la table des symboles contiendra également des entrées générées par le compilateur pour les valeurs d'expression intermédiaires (par exemple, l'expression qui iconvertit la variable de boucle en a doubleet la valeur de retour de l'appel à la fonction bar()), les étiquettes d'instruction, etc.

Exemple : SysV ABI

Un exemple de table de symboles peut être trouvé dans la spécification SysV Application Binary Interface (ABI), qui prescrit comment les symboles doivent être disposés dans un fichier binaire, afin que différents compilateurs, éditeurs de liens et chargeurs puissent tous trouver et travailler de manière cohérente avec le symboles dans un objet compilé.

L'ABI SysV est implémentée dans l' utilitaire nm de GNU binutils . Ce format utilise un champ d' adresse mémoire trié , un champ "type de symbole" et un identifiant de symbole (appelé "Nom").

Les types de symboles dans l'ABI SysV (et la sortie de nm) indiquent la nature de chaque entrée dans la table des symboles. Chaque type de symbole est représenté par un seul caractère. Par exemple, les entrées de table de symboles représentant des données initialisées sont désignées par le caractère "d" et les entrées de table de symboles pour les fonctions ont le type de symbole "t" (car le code exécutable est situé dans la section texte d'un fichier objet). De plus, la majuscule du type de symbole indique le type de lien : les lettres minuscules indiquent que le symbole est local et les majuscules indiquent un lien externe (global).

Exemple : la table des symboles Python

Le langage de programmation Python comprend une prise en charge étendue de la création et de la manipulation de tables de symboles. Les propriétés qui peuvent être interrogées incluent si un symbole donné est une variable libre ou une variable liée , s'il s'agit d'une portée de bloc ou d' une portée globale , s'il est importé et à quel espace de noms il appartient.

Exemple : tables de symboles dynamiques

Certains langages de programmation permettent de manipuler la table des symboles au moment de l'exécution, de sorte que des symboles peuvent être ajoutés à tout moment. Racket est un exemple d'un tel langage.

Les langages de programmation LISP et Scheme permettent tous deux d'associer des propriétés génériques arbitraires à chaque symbole.

Le langage de programmation Prolog est essentiellement un langage de manipulation de tables de symboles ; les symboles sont appelés atomes , et les relations entre les symboles peuvent être raisonnées. De même, OpenCog fournit une table de symboles dynamique, appelée espace atomique , qui est utilisée pour la représentation des connaissances .

Voir également

• Symbole de débogage

Les références