多态抽象语法树（递归下降解析器）：不可能？

Question

我已经开始用 C++ 编写多态递归下降解析器。但是我运行是个问题。类是这样设置的：

class Node {
public:
    std::vector<Node*> children;
};

class NodeBinary : public Node {
public:
    Node* left;
    Node* right;
};

class NodeUnary : public Node {
public:
    Node* operand;
};

class NodeVar : public Node {
public:
    std::string string;
    NodeVar(std::string str) : string(str) {};
};

class NodeNumber : public Node {
public:
    signed long number;
    NodeNumber(signed long n) : number(n) {};
};

// etc.

然后类喜欢 NodeDeclaration、NodeCall、NodeNot、NodeAssignment、NodePlus、NodeMinus、NodeIf 等将从 Node 或不那么通用的东西继承，例如 NodeBinary 或 NodeUnary.

但是，其中一些采用更具体的操作数。 NodeAssignment 总是需要一个 var 和一个 number/expression。所以我必须将 Node* left 覆盖为 NodeVar* left 和 NodeExpr* right。问题来自 NodePlus 之类的东西。左边可以是 NodeVar 或 NodeExpr！而根节点也有类似的问题：在顶层解析将子节点添加到根时，如何判断子节点是NodeExpr、NodePlus、NodeIf 等等...?

我可以让所有节点都有一个枚举 "type" 说明它是什么类型，但是拥有一个漂亮的多态继承树有什么意义呢？

这个问题一般是怎么解决的？？

Answer 1

如果您对 AST 节点使用 class 继承，则需要创建适当的继承层次结构，就像任何面向对象的设计一样。

因此，例如，NodeAssignment（大概是 NodeStatement 的特化）需要包含一个 NodeLValue（其中 NodeVariable 是一个特化）和一个 NodeValue。与往常一样，LValues（即您可以分配给的东西）是 Values 的子集，因此 NodeLValue 将是 NodeValue 的特化。等等。您的二进制运算符节点将包含 left 和 right 成员，它们都是 NodeValue 基础对象（我希望 NodeValue 是纯虚拟的，具有大量特定的专业。)

如果你坚持使用递归下降解析器，每个解析函数都需要return一个合适的子class of Node，这样解析左边的函数赋值的一侧在逻辑上会 return 一个 NodeLValue*，准备插入到 NodeAssignment 构造函数中。（坦率地说，我会在所有这些 class 名称中放弃 Node 一词。将它们全部放入命名空间 node:: 并节省您自己的输入时间。）

多态抽象语法树（递归下降解析器）：不可能？

Polymorphic Abstract Syntax Tree (recursive descent parser): impossible?

c++

parsing

polymorphism

abstract-syntax-tree

recursive-descent