c++ - 使用二元和一元节点的解析器工作？

问题描述

我现在这个标题有点奇怪，但我希望你能明白我在问什么。几个月前，我在 python 中从事解释器程序的工作，这非常棒，但现在我想在 C++ 中实现相同的功能，但这样做给我带来了很大的问题，因为 C++ 是类型严格的。

让我们从我在 python 程序中所做的开始。首先，我创建了一个 Lexer，它将所有内容分成标记（键值对），我编写了一个 Parser，它将算术语法转换为操作节点，如 BinaryOpNode、UnaryOpNode 和 NumberNode。ex- (-2+7)^3 将被转换为 AST 作为二进制节点，左节点作为另一个二进制节点，运算符为 POW(power)，右节点为 3 的数字节点。该节点的左节点是二进制节点其左节点是一元节点（MINUS 和数字节点 2），运算符为 PLUS，右节点为数字节点 7。

我通过识别表达式、术语和因素来做到这一点。我用 C++ 编写了一个 Lexer，但在 Parser 中有问题。请帮助我在 C++ 中做同样的事情。

到目前为止我做了什么？

我尝试了一些奇怪但有点工作的东西。我创建了一个 BinaryOpNode 类，其中有两个 void* 成员用于右节点和左节点，一个 Enum 成员用于 Rt 和 Lt 节点之间的操作。现在两个节点的另外两个布尔成员将有助于现在什么类型的 void* Lt 和 Rt 是？它们是 UnaryOpNode 还是 BinaryOpNode（默认）。这将帮助我将节点类型转换为相应的类型。

但是我对我的结果不满意，因为它们看起来不太优化，而且我无法以这种方式跟踪 NumberNode。

请帮我。提前致谢

标签： c++c++11c++14c++17

您正在寻找的是多态性。也就是说，程序员编写的代码，并根据它所操作的事物的类型做不同的事情。

C++ 支持一系列令人眼花缭乱的多态性方法。

最受支持的类型是基于继承的虚拟多态性。在此，您创建一个基类：

struct INode {
  virtual ~INode() {}
};

并向其中添加通用操作，使这些通用操作成为纯虚拟的：

struct INode {
  virtual ~INode() {}
  virtual std::vector<INode*> GetChildren() const = 0;
};

这要求您使用指针而不是对象实例。

在这个系统中，如果你知道一个对象的类型，你就可以使用dynamic_cast<RealType*>(iNodePointer)一个指针来获取该对象作为那个类型的实例。nullptr如果类型不匹配，则返回。这使您可以访问不在基接口中的下降类型中的方法。

第二种多态性是std::variant基于的。这是解析器通常拥有的一组封闭类型。

using AnyNode = std::variant<Node::BinaryOp, Node::UnaryOp, Node::Number>;

在这里，您使用std::visit具体类型而不是来操作dynamic_cast，并且您的解析树是基于值的而不是基于指针的。

当您希望节点内部有一个向量时，会有些痛苦AnyNode。

第三种方式是std::function类型擦除样式。在这里，您编写自己的多态系统，该系统接受任意类型的对象并将它们的操作包装在值语义包装器中。

第四个选项是 CRTP 静态多态性。这不适合构建动态解析树，但它可以用来帮助实现上述一些内容。

第五个选项是面向方面的std::function操作包。

第六个选项是手动函数表调整，基本上是手动重新实现 C++ vtable 解决方案，就像你在 C 中一样，但在 C++ 中。这可以让您拥有与其他 OO 语言类似的功能。

第七个选项是编写一个信号槽系统并向您的对象发送消息。

几乎可以肯定还有更多。

最简单的解决方案可能是首先了解 C++ 中的继承和虚函数（上面的第一个选项）。我个人可能会std::variant在这一点上编写一个解析树，但如果你此时可能不知道足够的 C++ 来实际做到这一点。

c++ - 使用二元和一元节点的解析器工作？

问题描述

解决方案

推荐阅读