抽象语法树问题

Question

我目前在C下做一个编译器，我对构造AST数据结构的部分有点迷惑，特别是构造ID结构的部分，它被称为“符号表条目”。

我在网络上看到了这样的结构：

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 */
}; 

它看起来像一个链表，因为它持有指向前一个条目(*prev)的指针，但这背后的逻辑是什么？

Answer 1

具体问题的答案是: prev链接意味着，当您的代码具有指向其中一个节点的指针时，它可以沿着链接指向链中的前一个链接。符号表可能有这样一个列表的一个原因是为了处理嵌套作用域：

{
int x;
  {
   int x;
  }
}

但是，为什么symbols节点可能需要排列在列表中，还有很多其他原因。编译器需要访问所有节点的任何原因都是原因。

Answer 2

您看到的是很久以前C程序员遗留下来的一个有害习惯:假设符号将出现在某些列表中，而不是单独分配列表结构，而是将列表指针作为符号结构的一部分包括在内。这种技巧为每个列表元素节省了一次分配，但代价是:符号可以位于的列表集合是固定的，这种结构会让程序员感到困惑。如果应用程序是编译器，那么就没有理由再使用这个技巧了。有一个单独的列表结构要清晰得多，它的定义如下：

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

你可以想要多少就有多少，没有人比你更聪明。你觉得令人困惑的内部指针也就消失了。

你会问

这背后的逻辑是什么？

答案的一部分很简单，将符号放在可分辨列表中是很有用的。如果不了解更多关于特定编译器的信息，我就无法明确地回答这个问题。我最好的猜测是prev条目将用于实现嵌套作用域(C中的{ ... }括号)，但这是基于我见过或使用过的编译器的猜测。因此，可能的逻辑是，当遇到右大括号时，编译器可能会跟随该链接，直到它到达封闭作用域中的ste。比您正在研究的编译器的作者更有经验的人通常会将此逻辑放在“符号表抽象”中，其中将包括enterscope()和exitscope()等函数，并且这些操作的细节将对单个符号表条目的内部表示隐藏起来。

Answer 3

我使用反向链表的第一个想法是使用那些支持覆盖变量名的语言，例如：

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

在这种情况下，您希望访问具有最内层作用域的变量(定义的最后一个)。这可以通过向后遍历列表来找到(当然，假设您是通过向前走来构建列表的)。

然后，当一个作用域消失时，你也可以调整“head”指针来删除最近添加的变量。

当然，您可以通过在当前头部之前插入而不是添加到列表的末尾来达到相同的效果(从概念上看，这看起来就像正在做的事情，只是使用名为prev而不是next的指针)。