玩具编译器符号 Table

Question

我正在创建一个编译器（用于 Cool 语言）作为个人项目，但我在设计符号时遇到了问题 table。对于上下文，我使用类的层次结构作为我的 AST。这是 AST 的一小段：

class NodeAST {
public:
  virtual void accept(Visitor&) = 0;  
};

class ProgramAST : public NodeAST {
private:
  const std::vector<ClassPtr> vClasses;

public:
  ProgramAST(std::vector<ClassPtr> vClasses);

  auto class_cbegin() const { 
    return std::cbegin(vClasses); 
  }
  auto class_cend() const { 
    return std::cend(vClasses); 
  }

  virtual void accept(Visitor& v) override;
};

class ClassAST : public NodeAST {
private:
  const std::string name;
  const std::vector<FeaturePtr> vFeatures; 

public:
  ClassAST(std::string name, std::vector<FeaturePtr> vFeatures);

  auto getName() const { 
    return name; 
  }

  auto feature_cbegin() const { 
    return std::cbegin(vFeatures);
  }
  auto feature_cend() const { 
    return std::cend(vFeatures); 
  }

  virtual void accept(Visitor& v) override;
};

目前，我的符号 table 的核心是一个定义如下的地图：

std::unordered_map<std::string, NodeAST*> table

它将声明的名称映射到它在 AST 中的相应节点。这样，例如，我可以使用我在 AST 节点中设置的类型来填充松散标识符的类型。

然而，问题是当我查询节点的符号 table 时，我得到一个 NodeAST*。因此，我必须将它向下转换为 ClassAST*、MethodAST* 或 VarDecAST* 等才能实际使用它。

如何设计我的符号 table 以避免向下转换的需要？

Answer 1

我不知道您正在实现的编程语言，但我认为您不太可能完全避免动态转换。例如，在 f(1) 中，如果您的语言有 lambda，f 可以是函数或变量。您需要通过在符号 table.

中查找来找出答案

如果可以绝对排除这种可能性，理论上可以为每种类型创建单独的符号 table。但请记住，如果您需要检测名称冲突，这显然会使查找名称冲突变得更加困难，并且可能意味着您的编程语言以后更难扩展。我不推荐这个解决方案。

就我个人而言，我只会将 to_class()、to_var()、is_class()、is_var() 等方法添加到您的 NodeAST class，这样动态转换就被封装起来，而不是散布在整个代码库中。您还可以为您的符号 table 创建一个 class，这样您就可以使用 get_class()、get_var() 等访问元素

如果您担心 C++ 中 RTTI 的运行时成本，您可以查看其他编译器正在使用的解决方案。对于 LLVM，在此处进行了描述：http://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html

Answer 2

我过去曾非常成功地使用访问者模式来访问具有公共基础的指针容器。在一个实现中，我体验到比 dynamic_cast<> 实现提速约 40%，这在我编写的数据库抽象层中很重要。

此处的一个答案中有更多解释....Right design pattern to deal with polymorphic collections of objects

Visitor Pattern 上的 Wikipedia 页面还提供了一个很好的简短 C++ 示例，说明了 Dispatcher class 访问的一组基指针。

您在问题中显示了 "visitable" class 的源代码。我们需要查看您的 "visitor" 的实现，以了解您为什么需要 dynamic_cast<>。应该没有必要。应通过函数参数重载选择要使用的正确 visit() 函数。

干杯

玩具编译器符号 Table

Toy Compiler Symbol Table

c++

compiler-construction