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

Question

我有一个迷你 AST 结构，其中每个节点可能有一个左 child 和一个右 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 一起工作。我可以在分支节点本身中潜在地嵌入条件，这意味着在分支节点上进行预序遍历，但感觉不舒服，因为没有其他类型的节点在评估自身时涉及潜在的子树遍历。

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

Answer 1

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

• if-block(左:条件，右:if-body)
• if-body(左:任意，右:任意)

如果父条件为真，则使用 if-body 的左 child ，否则使用右 child 。