4

我目前正在研究 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) 的指针，但这背后的逻辑是什么？

4

3 回答 3

8

您的具体问题的答案是：prev 链接意味着，当您的代码有一个指向这些节点之一的指针时，它可以跟随链接到链中的前一个链接。符号表可能有这样一个列表的一个原因是为了处理嵌套范围：

{
int x;
  {
   int x;
  }
}

但是，符号节点可能希望排列在列表中的原因还有很多。编译器需要访问所有节点的任何原因都是一个原因。

于 2009-12-26T00:54:36.917 回答
2

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

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

你可以拥有任意数量的这些，没有人比你更聪明。你会感到困惑的内部指针消失了。

你问

这背后的逻辑是什么？

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

于 2009-12-26T02:54:30.017 回答
1

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

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

在这种情况下，您希望访问具有最内部范围（定义的最后一个范围）的变量。这可以通过在列表中向后走来找到（当然假设您正在通过前进来构建列表）。

然后，当范围消失时，您也可以只调整“头”指针以删除最近添加的变量。

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

于 2009-12-26T00:58:25.953 回答