Implémentation d'une table de symboles avec une table de hachage et une pile
-
05-11-2019 - |
Question
J'étais en classe aujourd'hui, dans un cours de traduction en langue, en pensant à la meilleure façon d'écrire une table de symboles pour un compilateur. Mon professeur nous a montré une table de hash avec des listes liées reliant différents niveaux de "blocs", qui sont généralement des supports bouclés {} dans des langues telles que C.
Ma pensée était, qu'est-ce qui ne va pas avec l'utilisation de piles à la place?
Par exemple, voici quelques code:
int x = 5;
float y = 3;
{
// stuff
int x = 100;
}
Ne serais-je pas en mesure de commencer, hachant x, le poussant sur une structure de pile comme
struct symbol_def{
char * type;
val_type value;
}
Je ne sais pas comment faire un type dynamique pour la valeur (si la valeur est même nécessaire là-dedans).
Quand le deuxième x arrive:
int x = 100;
Ensuite, nous hachons à nouveau x, poussant sur la pile.
À tout moment, le haut des piles est la visibilité de la portée actuelle.
Le problème pourrait cependant s'accompagner. Comment pouvons-nous sortir des bonnes choses? Celui que je ne suis pas entièrement sûr, et pourrait être un défaut fatal de cette conception.
En théorie, ce serait beaucoup d'emplois O (1) (recherche de table de hachage, poussée, éclater, faire un coup d'œil).
Dites moi ce que vous en pensez. Peut-être que je manque quelque chose ici, ou peut-être que c'est comment c'est déjà vraiment fait.
Pas de solution correcte