如何使用C++在抽象语法树中实现if-else分支

Question

我有一个迷你AST结构,其中每个节点可能有一个左和右子,例如:

class AstNode;
typedef std::shared_ptr<AstNode> AstNodePtr;

class AstNode
{
public:
    AstNode()
        : m_children(2)
    {
    }

    virtual ~AstNode()
    {
    }

    virtual void accept(AstNodeVisitor& visitor) = 0;

    void addLeft(const AstNodePtr& child);
    void addRight(const AstNodePtr& child);
    const AstNodePtr left() const;
    const AstNodePtr right() const;

private:
    std::vector<AstNodePtr> m_children;
};

它对我到目前为止所需的操作非常有用,但是当涉及到一个分支语句时,我不知道如何使用这个二叉树结构来实现它.根据维基,分支声明将有3个叶子:

我现在可以侥幸逃脱,因为我的大部分if语句都没有,所以条件将是左子,if-body将是正确的孩子.但它不适用于其他身体.我可以在分支节点本身中嵌入条件,这意味着在分支节点上进行预先遍历遍历,但是感觉不舒服,因为在评估自身时没有其他类型的节点涉及潜在的子树遍历.

也许AST不应该是二叉树,而是每个节点都可以有任意数量的子节点,但这(我认为)会使实现有点尴尬.有什么建议吗？

Answer 1

从本质上讲，AST应该在多子树中实现，以支持if-condition-then表达式。但是一种解决方法是为IF提供2种类型；

• if-block（left：condition，right：if-body）
• if-body（左：任意，右：任意）

如果父项的条件为true，则使用if-body的左子项，否则使用右子项。

Answer 2

您可以定义一个不包含任何子节点的抽象AST节点.然后,对于每个子节点数("arity"),定义一个不同的子类:

• 一个单一的 AST节点,return用于诸如否定之类的一元运算符
• 用于二进制运算的二进制 AST节点
• 构造以及三元运算符的三元 AST节点if-then-else?!
• 如果你想支持它们,那么对于构造中的一组案例,可能是一个动态的n-ary AST节点switch-case.您也statement-sequence非常适合此节点类型.如果不实现此节点类型,则可以将语句序列放在二叉树结构中,但这听起来像是一个脏的黑客.
• 也许是一个四元(这是名字？)AST节点的for循环.他们有一个初始,一个条件和一个增量声明加上一个正文.

请注意,在我看来,使用动态大小的子列表实现所有内容是一个坏主意,因为operator =例如,只有一个子节点的类型节点没有意义.

然后,从与arity对应的节点类继承具体的节点类型.

class ASTNode {
public:
    virtual ASTNode() {}
    virtual void accept(AstNodeVisitor& visitor) = 0;
};

// ----

class ASTNodeUnary : public ASTNode {
protected:
    AstNodePtr c1;
};

class ASTNodeBinary : public ASTNode {
protected:
    AstNodePtr c1, c2;
};

class ASTNodeTernary : public ASTNode {
protected:
    AstNodePtr c1, c2, c3;
};

class ASTNodeDynamic : public ASTNode {
protected:
    std::vector<AstNodePtr> children;
};

// ----

class ASTNodeBranch : public ASTNodeTernary {
    ...
};

等等