question arbre de syntaxe abstraite

Question

Je travaille actuellement sur un compilateur en C et je suis abit perdu à la partie où l'on construit la structure de données pour AST, en particulier pour la partie où nous construisons stucture pour les ID, il est appelé « Table des symboles d'entrée »

Je vois des structures plus net telles que:

struct ste {
  struct id   *name;  /* pointer into hash table for assoc. id */
  struct decl *decl;  /* pointer into symbol table for its decl */
  struct ste  *prev;  /* pointer to previous entry in symbol table */
}; 

Il ressemble à une liste chaînée comme il contient un pointeur à l'entrée précédente (* prev) mais quelle est la logique derrière tout cela?

Answer 1

La réponse à votre question concrète est la suivante: le lien prev signifie que, lorsque votre code a un pointeur vers un de ces nœuds, il peut suivre le lien vers le lien précédent dans la chaîne. L'une des raisons d'une table de symbole peut ont une telle liste est de traiter la portée imbriquée:

{
int x;
  {
   int x;
  }
}

Cependant, il y a beaucoup, beaucoup d'autres raisons pour lesquelles les nœuds symboles pourraient vouloir être disposés dans une liste. Toute raison pour laquelle le compilateur a besoin de visiter tous les nœuds est une raison.

Answer 2

Vous voyez les restes d'une habitude pernicieuse de programmeurs C il y a longtemps: on suppose que les symboles seront sur certaines listes, et au lieu d'allouer des structures de liste séparément, les pointeurs de la liste sont inclus dans le cadre de la structure de symbole. Cette astuce permet d'économiser une allocation par élément de la liste, mais à un coût: l'ensemble des listes qu'un symbole peut être sur est fixe, et cette structure embrouille les programmeurs. Si l'application est compilateurs, il est pas raison d'utiliser cette astuce plus. Il est beaucoup plus clair d'avoir une structure de liste séparée qui est défini comme ceci:

struct ste_list {
    struct ste *symbol_table_entry;
    struct str_list *next;
};

Vous pouvez avoir autant d'entre eux que vous le souhaitez, et personne est le plus sage. Et les pointeurs internes que vous trouvez confus disparaissent.

Vous demandez

  

Quelle est la logique derrière tout cela?

Une partie de la réponse est tout simplement qu'il est utile d'avoir des symboles sur une liste distinguée. Je ne peux pas répondre définitivement à la question sans en savoir plus sur le compilateur particulier. Ma meilleure estimation est que l'entrée de prev va être utilisé pour mettre en œuvre les portées imbriquées (les supports de { ... } en C), mais qui est une estimation basée sur les compilateurs que j'ai vu ou travaillé. Alors peut-être la logique est que lorsqu'une accolade fermante est rencontré, le compilateur peut suivre ce lien jusqu'à ce qu'il arrive à un ste dans une portée englobante. Les gens avec un peu plus d'expérience que l'auteur du compilateur que vous étudiez sera généralement mis cette logique dans une « abstraction table des symboles » qui comprendra des fonctions comme enterscope() et exitscope(), et les détails de ces opérations seront cachées à l'interne représentation des entrées individuelles tables de symboles.

Answer 3

Ma première pensée pour l'utilisation d'un sens inverse liste chaînée serait pour les langues qui prennent en charge la surcharge des noms variables, tels que:

int main (void) {
    int x = 1;
    int y = 1;
    if (x == 1) {
        int y = 2;
        printf ("y = %d\n", y);
    }
    return 0;
}

Dans ce cas, vous souhaitez accéder à la variable avec la portée la plus interne (le dernier celui défini). Cela peut être trouvé en marchant en arrière dans la liste (en supposant que vous construisez la liste en l'avenir bien sûr).

Alors, quand un champ disparaît, vous pouvez également régler simplement le pointeur « tête » pour éliminer les variables les plus récemment ajoutées.

Bien sûr, vous pouvez obtenir le même effet en insérant avant la tête en cours plutôt que d'ajouter à la fin de la liste (qui ressemble à conceptuellement ce qui est fait, juste avec le pointeur appelé prev au lieu de next).