CODEWITHSUNDEEP
c++abstract-syntax-tree
swang
swang

Reputation: 5249

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

I have a mini AST structure in which each node may have a left and a right child, for example:

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

It works great for the operations I need so far, but when it comes to a branch statement, I don't know how to implement it with this binary tree structure. According to wiki, a branch statement will have 3 leaves:

enter image description here

I can get away with it for now because most of my if statement has no else, so the condition will be the left child, and if-body will be the right child. But it's not going to work with a else-body. I can potentially embed condition in the branch node itself, which means do a pre-order traversal on branch node, but it feels uncomfortable because no other type of nodes involve potential subtree traversal when evaluating itself.

Maybe the AST should not be a binary tree, rather each node can have any number of children, but that will(I think) make the implementation a bit awkward. Any suggestions please?

Upvotes: 6

Views: 13502

Answers (2)

leemes
leemes

Reputation: 45675

You could define an abstract AST node which doesn't hold any children. Then for each number of child nodes ("arity"), define a different subclass:

  • a unary AST node for things like return or for unary operators such as negation
  • a binary AST node for binary operations
  • a ternary AST node for if-then-else constructs as well as for the ternary operator ?!
  • maybe a dynamic n-ary AST node for the set of cases in a switch-case construct, if you want to support them. Your statement-sequence perfectly fits into this node type, too. If you don't implement this node type, you could put statement sequences in a binary tree structure, but that sounds like a dirty hack.
  • maybe a four-ary (is this the name?) AST node for for loops. They have an initial, a conditional and an incremental statement plus a body.

Note that implementing everything with dynamically sized children lists is a bad idea in my opinion, since it doesn't make sense to have a node of type operator = with only one child, as an example.

Then, inherit the concrete node types from the node class corresponding to the 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 {
    ...
};

and so on

Upvotes: 6

sithereal
sithereal

Reputation: 1686

By the nature, ASTs should be implemented in multi-child trees to support if-condition-then expressions. But a workaround could be having 2 types for IF;

  • if-block(left:condition, right:if-body)
  • if-body(left:any, right: any)

left child of the if-body is used if condition of the parent is true, right child is used otherwise.

Upvotes: 7

Related Questions