c++ - 在符号表中记录所有权

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 这样的成员引用，您需要在 r 中搜索 a code> 的成员，然后是 r.a 的成员中的 b，依此类推。这表明结构类型包含成员的符号表(可能是指针，也可能不是指针，具体取决于您的设计。通常，结构的成员列表不共享，但在 OO 子类/父类(super class)关系的情况下，成员查找可能会更复杂。)

我想我在这里想表达的观点是符号表的结构在很大程度上取决于语言的性质。符号表的核心是包含一个符号列表，该列表的组织方式使得通过符号名称查找符号更加高效。符号表将每个符号与某个符号数据对象相关联，这些符号数据对象可能因符号表类型而异(例如使用 C++ 泛型)，也可能在所有符号表中保持一致。通常，符号表与简单的哈希表(或关联容器)不同，因为符号还具有某种线性排序，用于在编译时生成线性表示。精确的细节可能会有所不同，但能够以一致的、定义明确的顺序迭代符号通常是一个重要的功能。

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

是否可以保留对符号表的持久指针或引用完全取决于您的底层设计。如果这是您的愿望，那么很容易实现。我认为这很常见，但我不能谈论那里的各种语言实现。

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