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

Question

我有一个迷你 AST 结构，其中每个节点可能有一个左节点和一个右节点 child，例如：

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;
};

到目前为止，它非常适合我需要的操作，但是当涉及到分支语句时，我不知道如何用这种二叉树结构来实现它。根据 wiki，分支语句将有 3 个叶子：

我现在可以不用管它了，因为我的大部分 if 语句都没有 else，所以条件将是左边的 child，而 if-body 将是右边的 child ].但它不适用于 else-body。我可以潜在地将条件嵌入分支节点本身，这意味着在分支节点上进行 pre-order 遍历，但感觉不舒服，因为没有其他类型的节点在评估自身时涉及潜在的子树遍历。

也许 AST 不应该是二叉树，而是每个节点可以有任意数量的 children，但是（我认为）这会使实现有点尴尬。有什么建议吗？

Answer 1

本质上，AST 应该在 multi-child 树中实现以支持 if-condition-then 表达式。但是解决方法可能是有 2 种类型的 IF；

if-block(left:condition, right:if-body)
if-body（左：任意，右：任意）

如果 parent 的条件为真，则使用 if-body 的

left child，否则使用 right child。

Answer 2

您可以定义一个不包含任何子节点的抽象 AST 节点。然后对于每一个子节点数（"arity"），定义不同的subclass:

a unary AST 节点，用于 return 或一元运算符，如否定
a binary 二元运算的 AST 节点
a 三元 if-then-else 构造以及三元运算符 ?!
如果您想支持 switch-case 结构中的案例集，n-ary AST 节点可能是动态的。您的 statement-sequence 也非常适合这种节点类型。如果您不实现此节点类型，则可以将语句序列放入二叉树结构中，但这听起来像是一个肮脏的 hack。
可能是四元（这是名字吗？）for 循环的 AST 节点。它们有一个初始语句、一个条件语句和一个增量语句以及一个正文。

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

然后，从class节点对应的节点继承具体的节点类型。

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 {
    ...
};

等等

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

How to implement if-else branch in a abstract syntax tree using C++

c++

abstract-syntax-tree