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

Question

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 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 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: 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 branc…

Accepted Answer

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.

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

Solution

Problem