Analyse sémantique : la table des symboles
Nous utiliserons principalement la table des symboles lors de l'analyse sémantique, mais nous la construirons pendant notre analyse syntaxique. Nous pouvons aussi profiter de la construction de la table des symboles poçur détecter des erreurs de syntaxe et décider d'interrompre le processus de compilation.
Dans ce document, nous allons nous poser les questions préliminaires nécessaires à la création d'une table des symboles pour le compilateur. Le document suivant reprend une implémentation possible en fonction des choix que nous prendrons suite à ces questions.
Problème de portée et de surcharge
Comme nous l'avons constaté lors de nos recherches d'une structure de données adéquoite pour notre table des symboles, nous retrouverons souvent un même identificateur pour des variables ou des méthodes1. Nous devrons donc trouver un moyen de gérer ces problèmes de portée et de surcharge.
Portée
Le problème de portée d'un symbole est comme un ensemble de poupées russes : une série de blocs qui peuvent contenir d'autres blocs. Si nous ne trouvons pas la déclaration de la variable dans le bloc dans lequel elle est utilisée, nous devons vérifier dans le bloc parent. C'est la règle de « l'englobant le plus proche », qui stipule que nous cherchons de bloc englobant en bloc englobant (ce qui correspond à une descente vers le fond de notre pile), et que la première déclaration trouvée est celle qui s'applique au bloc de départ de la recherche.
Si nous sommes au fond de la pile et si nous n'avons pas encore trouvé la déclaration du symbole, nous avons une erreur d'utilisation de variable non déclarée, ou une erreur d'utilisation de fonction non déclarée.
Nous pouvons considérer les différentes portées comme une pile. Selon le type d'implémentation choisi, nous pouvons avoir dans chaque élément de la pile une table des symboles, et dans ce cas nous ne pouvons plus avoir de collisions (car chaque table des symboles est limitée correspond à une portée particulière).
Nous ne retiendrons pas ce type d'implémentation car nous utiliserons le langage C et créer un tableau pour chaque portée coûte énormément en mémoire. De plus, peu de cellules par tableau seront réellement utilisées.
Utilisation d'une table principale
Si nous développons un compilateur qui sera exécuté sur des machines qui possèdent beaucoup de ressources mémoire, nous pouvons accélérer les lectures dans la table des symboles en créant une table qui contient les symboles dont la visibilité n'est pas masquée par des problèmes de portée. Nous devons alors maintenir une information supplémentaire dans cette table : la portée dans laquelle le symbole est déclaré. Ce gain de temps en lecture est balancé par une perte lors de l'insertion d'un symbole qui existe déjà : il faut alors non seulement copier le nouveau symbole dans la table qui correspond à sa portée, mais aussi marquer l'entrée dans la table principale afin que l'on sache qu'il est nécessaire de chercher dans la table correspondant à la bonne portée.Surcharge
Certains langages permettent d'utiliser un même nom pour différentes fonctions pour autant que leurs arguments diffèrent en nombre et/ou en types. Nous devons donc alors maintenir une collection comme valeur, car nous aurons des collisions au niveau des noms.
Signature de fonctions
Nous pouvons éviter ce genre de collision si nous utilisons un identifiant adapté à la « signature » de la méthode : par exemple une concaténation du nom de la fonction et des types de ses arguments dans l'ordre.Position des déclarations
Les règles relatives aux déclarations, imposées par le langage analysé, auront un impact sur la manière dont nous implémenterons notre table des symboles au sein du compilateur. En effet, certains langages permettent l'utilisation de variables non déclarées, d'autres requièrent une « déclaration anticipative » (en anglais, “backward declaration”), ou encore permettent une « déclaration a posteriori » (en anglais, “forward declaration”).
Nous pouvons travailler de la manière suivante pour détecter la position de la déclaration : déterminer dans quelle portée se trouvent la déclaration et l'utilisation du symbole, puis vérifier la position au sein du fichier source.
Quand créer la table des symboles ?
Nous pouvons créer la table des symboles au début de notre compilation. Nous créerons les blocs de portées par la suite.
Quand remplir la table des symboles ?
Nous pouvons attendre que l'AST [“Abstract Syntaxic Tree”4] soit entièrement constitué, et le parcourir ensuite pour constituer notre table des symboles, mais ce n'est pas la solution la plus rapide. Comme le langage que nous allons compiler (LSD010) ne permet pas de « déclaration a posteriori »3, c'est au moment de remplir l'AST lors de l'analyse syntaxique, à chaque fois que nous rencontrons une déclaration, que nous pouvons l'ajouter dans la table des symboles.
Rechercher une valeur
Comme un des buts de notre table des symboles est de nous aider à retrouver rapidement un symbole, nous devrons implémenter une fonction getDeclaration(Char * symbolId) qui nous retourne le nœud qui correspond à notre symbole dans l'arbre syntaxique.
Comme nous avons vu que l'identificateur peut comporter d'autres informations que le nom (comme par exemple dans le cas d'identificateur de fonction), nous pouvons passer par une fonction qui nous calcule l'identificateur avant de le passer en paramètre, ou simplement passer un pointeur vers un nœud de l'AST qui contient toutes les informations nécessaires.
Nous avons donc cette signature : getDeclaration(AstNode symbolNode)
Comme nous utilisons le langage C pour réaliser notre compilateur, que ce langage ne permet d'indexer les tableaux que par des valeurs de type numérique entier, et que nous avons seulement une chaîne de caractères à chercher dans notre table des symboles, nous devrons effectuer une conversion entre la chaîne de caractères et l'entier. Si nous désirons un algorithme de conversion assez rapide, nous risquons fortement d'avoir pour un certain nombre de chaînes de caractères différentes une valeur numérique entière identique. Nous avons là un nouveau type de collisions, et nous devons à nouveau stocker une liste chaînée en tant que valeur associée à notre clé numérique. Lorsque nous cherchons une déclaration de symbole, nous devons parcourir les éléments de la liste et comparer la chaîne de caractères avec celle que nous cherchons pour déterminer si nous sommes en présence du bon nœud.
Structure des données
Nous utiliserons le langage C pour réaliser notre compilateur7. La première idée est de générer un tableau dont la clé est le nom du symbole, et la valeur stockée est le nœud de l'AST, mais le langage C ne nous permet que des tableaux indexés par des clés de type int. En Java, par exemple, nous aurions pu utiliser une HashMap.
Hachage et identification des symboles
Notre algorithme de hachage nous assure que le résultat produits par deux appels sur des identifiants identiques produira toujours le même résultat, mais pas deux appels sur des identifiants différents produira deux résultats différents. Ce qui revient à dire que nous pouvons avoir une même valeur de retour pour deux identifiants de symboles différents, ce qui provoque des « collisions » au niveau des clés de notre tableau.
Nous pouvons résoudre ce problème de collisions dans la table des symboles en utilisant une liste chaînée de nœuds comme valeur correspondant à un nom de symbole. De cette manière, nous ne perdons pas d'information.
Alternatives pour les structures de données en C
Maintenant que nous avons soulevé certaines questions à propos de la gestion des symboles, nous pouvons penser à la structure de données de la table des symboles proprement dite. Nous avons un certain nombre d'alternatives qui s'offrent à nous, dont les deux décrites ci-dessous, qui diffèrent par l'importance que nous accordons aux identifiants des symboles ou à la portée courante.
Une seule table pour les symboles
Comme nous avons un algorithme de hachage à notre disposition pour les identifiants de symboles, nous pouvons utiliser un tableau unique dans lequel chaque cellule contient ce qui correspond à un identificateur de symbole. Nous utiliserons donc une structure particulière à stocker dans une cellule.
Comme nous avons vu que nous risquons d'avoir un même résultat pour le hashcode de plusieurs identificateurs différents, nous utiliserons comme structure à placer dans notre table des symboles une liste chaînée. Si le nom du premier élément de la liste ne correspond pas à notre symbole8, nous cherchons le nom de l'élément suivant. Normalement, si la taille du tableau est suffisante et l'algorithme de hachage assez dispersant, nous avons rarement besoin de chercher après un grand nombre d'éléments suivants.
Chaque élément de notre liste chaînée contiendra le nom du symbole et une pile qui correspond aux différentes portées de ce symbole9.
Nous retrouvons dans nos éléments de pile de portée l'identifiant de potrée, un pointeur vers le neœd qui contient la déclaration de notre symbole dans l'AST, et un pointeur vers la portée englobante.
Une seule pile de portées
Nous pouvons utiliser une pile de portées en tant que structure principale. Cette alternative nous évite de devoir calculer le hachage pour indexer notre tableau, et présente l'avantage d'être beaucoup plus économe en resources mémoire (Il n'est plus nécessaire de réserver l'espace mémoire pour le tableau). Cependant, elle est plus lente dans le cas des recherches, car nous devons à chaque fois parcourir la liste chaînée des déclarations pour la portée, et recommencer dans la portée englobante si nécessaire. Si la déclaration est dans le bas de la pile de portée, nous devons presque parcourir la totalité des déclarations.
Optimiser la recherche
Les deux alternatives permettent de dépiler les déclarations quand nous quittons une portée pour retourner dans la portée englobante, mais nous pouvons
optimiser la recherche de différentes manières :- Déplacer en tête de notre liste chaînée la dernière déclaration lue. Par exemple, si nous lisons une variable, il est fort probable que nous ayons besoin d'y accéder à nouveau dans un laps de temps assez court.
- Utiliser une pile externe d'une taille donnée, qui contient les pointeurs vers les dernières déclarations utilisées.
English translation
You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.
Thank you in advance.
Document created the 11/07/2010, last modified the 28/10/2018
Source of the printed document:https://www.gaudry.be/en/langages-table-des-symboles.html
The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.
- ↑ Variables et fonctions : Nous parlerons de symboles car cela s'applique aux variables utant qu'aux fonctions.
- ↑ déclaration anticipative : corresponds to “backward declaration” en anglais
- ↑a,b,c,d,e,f… 1 more links… Abstract Syntaxic Tree : corresponds to « arbre syntaxique abstrait » en français
- ↑ LSD010 : Langage Simple et Didactique Il existe une un certain nombre d'interprétations de l'acronyme LSD (Langage Symbolique Didactique, Langage Sans Difficulté, Langage Simple et Didactique). LSD010 est la version 2010 de la suite LSD80, LSD_02, LSD03, LSD04, LSD05, LSD06, LSD07, LSD08, et LSD09.
- ↑ Langage du compilateur : Nous aurions pu choisir un autre langage pour réaliser notre code interne au sein du compilateur, comme par exemple Java.
- ↑ Identificateur vs nom : Nous parlons de nom de symbole et pas d'identificateur, car l'identificateur peut comporter d'autres informations que le nom, comme par exemple dans le cas d'identificateur de fonction.
- ↑ Stockage du nom de symbole : En réalité, comme nous avons déjà toutes les informations nécessaires dans le nœud de notre AST, nous ne mémorisons pas le nom dans l'élément lui-même, mais nous le lisons dans le premier élément de la pile de portée, qui est un pointeur vers le nœud de la déclaration.
References
IHDCB332 - Théorie des langages : Syntaxe et sémantique : PY Schobbens, Syntaxe et sémantique
(January 2010)- Compilateurs : Dick Grune, Henry E. Bal, Ceriel J.H. Jacobs, Koen G. Langendoen,
Cours et exercices corrigés
- Compilateurs : A. Aho, M. Lam, R. Sethi, J. Ulman,
Principes; techniques et outils
These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.
