Question sur l'arbre syntaxique abstrait

Question

Je travaille actuellement sur un compilateur en C et je suis un peu perdu dans la partie où nous construisons la structure de données pour l'AST, en particulier pour la partie où nous construisons la structure pour les ID, qui s'appelle "Symbol Table Entry" (entrée dans la table des symboles).

Je vois des structures sur le réseau 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 */
}; 

Cela ressemble à une liste chaînée puisqu'elle contient un pointeur sur l'entrée précédente (*prev), mais quelle est la logique derrière cela ?

Answer 1

La réponse à votre question concrète est la suivante : le lien prev signifie que, lorsque votre code dispose d'un pointeur sur l'un de ces nœuds, il peut suivre le lien jusqu'au maillon précédent de la chaîne. L'une des raisons pour lesquelles une table de symboles puede Une liste de ce type permet de gérer les champs d'application imbriqués :

{
int x;
  {
   int x;
  }
}

Cependant, il existe de très nombreuses autres raisons pour lesquelles les nœuds de symboles peuvent être disposés dans une liste. Toute raison pour laquelle le compilateur doit visiter tous les nœuds est une raison.

Answer 2

Vous voyez ici les restes d'une habitude pernicieuse prise par les programmeurs C il y a longtemps : on suppose que les symboles se trouveront sur certaines listes et, au lieu d'allouer les structures de listes séparément, les pointeurs de listes sont inclus dans la structure des symboles. Cette astuce permet d'économiser une allocation par élément de liste, mais elle a un coût : l'ensemble des listes sur lesquelles un symbole peut figurer est fixe, et cette structure est source de confusion pour les programmeurs. Si l'application concerne les compilateurs, il y a non raison d'utiliser encore cette astuce. Il est beaucoup plus clair d'avoir une structure de liste séparée qui est définie comme suit :

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

Vous pouvez en avoir autant que vous le souhaitez, et personne ne s'en apercevra. Et les indications internes que vous trouvez déroutantes disparaissent.

Vous demandez

Quelle est la logique de cette démarche ?

Une partie de la réponse est 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 en question. Mon hypothèse la plus plausible est que le compilateur prev va être utilisée pour mettre en œuvre des scopes imbriqués (l'entrée { ... } en C), mais c'est une supposition basée sur les compilateurs que j'ai vus ou sur lesquels j'ai travaillé. La logique est peut-être que lorsqu'une accolade fermante est rencontrée, le compilateur peut suivre ce lien jusqu'à ce qu'il atteigne une accolade fermante. ste dans une portée englobante. Les personnes ayant un peu plus d'expérience que l'auteur du compilateur que vous étudiez placent généralement cette logique dans une "abstraction de table de symboles" qui comprend des fonctions telles que enterscope() et exitscope() et les détails de ces opérations seront cachés de la représentation interne des entrées individuelles de la table des symboles.

Answer 3

Ma première idée pour l'utilisation d'une liste chaînée à sens inverse serait pour les langages qui permettent de remplacer les noms de variables, comme par exemple :

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 voulez accéder à la variable ayant la portée la plus interne (la dernière définie). Cette variable peut être trouvée en parcourant la liste à rebours (en supposant que vous construisiez la liste en avançant, bien sûr).

Ensuite, lorsqu'un champ d'application disparaît, il suffit d'ajuster le pointeur de tête pour supprimer les dernières variables ajoutées.

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