CODEWITHSUNDEEP
c++parsingrecursionnodesabstract-syntax-tree
SolaGratia
SolaGratia

Reputation: 309

Parsing nodes and their own (indefinite amount of nested) child nodes in an AST

I'm writing a basic lexer for my language and I want to traverse a tree of Node objects in an AST object. Each Node object in the AST has a member Children of type vector<Node>. This is to allow for nodes to have child nodes (for example, an expression node coul store two nodes operand_a, and operand_b).

The problem is, I don't know how to make a for loop iterate through an AST of Nodes, whose child nodes can have an indefinite number of their own child nodes and so on.

Here is the header for my AST/Node classes.

enum NodeType {
    ... 
TOKEN_SIGN_PLUS,
TOKEN_SIGN_MINUS,
    ...
};

class Node;
struct AST
{
    vector<Node> Nodes;
    void addNode(Node node);
    void deleteNode(size_t nodeID);
    //void deleteNodeRange(size_t from, size_t to);
    void popEndNode();
    size_t NodeCount() { return Nodes.size(); }
    AST() {}
    ~AST() {}
};

struct Node  
{
    friend AST;
    AST* ParentAST;
    NodeType NodeType;
    size_t NodeID();
    string Data;
    vector<Node> Children;
    size_t ChildCount() { return Children.size(); }
    Node() {}
    ~Node() {}
  private:
    size_t _nodeID;
};

So my question is, how can I iterate through every single child node and its children, on a per parent basis so I could, say, print something like this:

NODE: "EXPR"
            NODE: "INT_LITERAL"
            NODE: "OP_PLUS"
            NODE: "INT_LITERAL"

OR, more to the point (multiple nested children):

NODE: "DECL_AND_INIT_VARIABLE"
                              NODE: "KEYWORD_INT"
                              NODE: "IDENTIFIER"
                              NODE: "OP_EQ"
                              NODE: "EXPR"
                                          NODE: "INT_LITERAL"
                                          NODE: "OP_PLUS"
                                          NODE: "INT_LITERAL"

Upvotes: 0

Views: 351

Answers (1)

Matt Jordan
Matt Jordan

Reputation: 2181

This is a quick/crude example, but probably something vaguely like this:

struct AST
{
   ...
   void print() const;
};
...
struct Node
{
   ...
   void print(int indent) const;
};

void AST::print() const
{
    for(const auto& node:Nodes)
        node.print(0);
}

void Node::print(int indent) const
{
    auto thisindent = strlen("NODE: ") + Data.length();
    cout << string(indent + thisindent, ' ');
    cout << "NODE: " << Data << endl;
    if(Children.size() > 0)
        for(const auto& child:Children)
            child.print(indent + thisindent);
}

Upvotes: 1

Related Questions