在符号表中记录所有权

Question

我正在实现dragon book中所述的符号表：

class SymbolTable {
    std::unordered_map<std::string, Record> table;
    SymbolTable* parent;

public:
    SymbolTable(SymbolTable* p) : parent{p} {}

    const Record* lookUp(const std::string& name) const {
        for (auto* scope = this; scope != nullptr; scope = scope->parent) {
            auto iter = scope->table.find(name);
            if (iter != cend(scope->table))
                return &iter->second;
        }
        return nullptr;
    }

    bool insert(const std::string& name, const Record& record) { 
        return names.insert({name, record}).second; 
    }
};

但是，我不确定如何存储记录数据。谁应该拥有类型信息？ Record是否应包含指向AST中已存储类型的非所有指针？

[此外，我想保留我的符号表以备以后的编译器通过。 Cooper & Torczon简要提到直接在AST节点中插入指向相应SymbolTable的指针。这是常用方法吗？

Answer 1

对记录中名称的查找通常不遵循自下而上的方法，该方法是使用从范围到范围的父指针实现的。 （实际上，简单的数据结构也可能不完全适用于范围；一旦引入词法闭包，您的范围关系就变得更加复杂。）

尽管有一些语言会从结构到包含结构的成员进行隐式查找，但它们很少见，经验表明，这种形式的名称查找很容易出现困难，尽管有时看起来很方便。

最常见的模式是结构类型包含一个成员列表，每个成员都有自己的类型。该成员列表实际上是一个符号表，因为要解析类似r.a.b.c的成员引用，您需要在a的成员中搜索r，然后在b'中搜索r.a”。的成员，等等。这表明结构类型包含成员的符号表（取决于设计，它可能是或可能不是指针。通常不共享结构的成员列表，但是在OO子类/超类关系的情况下，成员查找可能会更复杂。）

我想我想在这里说明的是符号表的结构在很大程度上取决于语言的性质。符号表的核心是一个符号列表，该列表以某种方式进行组织，从而可以高效地按名称查找符号。符号表将每个符号与某个符号数据对象相关联，该符号数据对象可能随符号表类型的不同而有所不同（例如，使用C ++泛型），或者在所有符号表中可能是一致的。通常，符号表与简单的哈希表（或关联容器）有所不同，因为符号还具有某种线性排序，用于在编译时生成线性表示。精确的细节会有所不同，但是能够以一致，定义明确的顺序遍历符号通常是一个重要功能。

根据关注点分离的一般原则，如上所述的符号表也不应试图成为符号表的容器。符号表可以回答有关其包含的名称的问题。最好使用一个不同的对象来搜索多个符号表（范围搜索或其他操作），该对象知道如何处理某些符号表中的名称查找失败，但无需了解单个名称查找的技术细节。

您是否可以保留对符号表的持久指针或引用完全取决于您的低级设计。如果那是您的愿望，那么轻松实现。我认为这很普遍，但是我不能代表那里各种各样的语言实现。

符号表并不总是以简单的方式相互关联，而可以很容易地将其表示为所有权。在这方面，它们类似于在编译器中浮动的其他内部对象。一旦开始实现公共子表达式优化，AST节点可能突然变成图形中的共享节点，而不是树节点。 （这只是一个例子。）据我所知，大多数复杂的编译器最终都会为内部对象实现某种垃圾收集，除非当然要用具有通用垃圾收集的语言编写编译器。