在符号表中记录所有权

Question

我正在实现 table 中描述的符号 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 中的类型的非拥有指针？

此外，我想保留我的符号 table 以供以后的编译器通过。 Cooper & Torczon 简要提及直接在 AST 节点中插入指向适当 SymbolTable 的指针。这是常见的方法吗？

Answer 1

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

虽然有些语言会从结构到包含结构的成员进行隐式查找，但这种语言很少见，而且经验表明这种形式的名称查找很容易遇到困难，尽管它偶尔看起来很方便。

最常见的模式是结构类型包含一个成员列表，每个成员都有自己的类型。该成员列表实际上是一个符号 table，因为为了解析像 r.a.b.c 这样的成员引用，您需要在 r 的成员中搜索 a ，然后是 r.a 的成员中的 b，依此类推。这表明结构类型包含成员的符号 table（它可能是也可能不是指针，具体取决于您的设计。通常不共享结构的成员列表，但在 OO subclass/superclass 关系，成员查找可能会更复杂。）

我想我在这里想表达的意思是符号的结构 table 在很大程度上取决于语言的性质。在其核心，一个符号 table 包含一个符号列表，其组织方式使得通过名称查找符号变得高效。符号 table 将每个符号与某个符号数据对象相关联，这些数据对象可能因符号 table 类型和符号 table 类型而异（例如使用 C++ 泛型），或者可能在所有符号 table秒。通常，符号 tables 与简单散列 tables（或关联容器）的不同之处在于符号也具有某种线性排序，用于在编译时生成线性表示。精确的细节会有所不同，但能够以一致的、定义明确的顺序迭代符号通常是一个重要的特性。

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

是否可以保留对符号的持久指针或引用 table 完全取决于您的低级设计。如果那是你的愿望，那很容易实现。我认为这很常见，但我不能代表那里的语言实现种类繁多。

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

在符号表中记录所有权

Record ownership in symbol tables

c++

compiler-construction

symbol-table