语言分析的二叉树实现-作为节点的子节点：不起作用

Question

我一直在尝试用 C++ 实现 AST 来存储从 ML 语言派生的数据，这是我的 AST 设法记录的指令：

var foo = 8;

词法分析器隔离了标记，解析器推断它是一个变量声明，所以它隔离了整个：

foo = 8

由此可以轻松构建临时 AST：

    =  
  /   \
foo    8

但是我还是处理不了子节点：

foo = 2 + 4

或

foo : integer = 2 + 4

那么谁应该给这个：

         =      
       /   \    
      /     \   
     :       +  
    / \     / \ 
   /   \   2   4
 foo integer

这是我的实现尝试：

*.hpp

enum NodeTypes { /* ... */ };

struct Node {
    token_t NodeValue;
    NodeTypes NodeType;
    Node *LeftChild = NULL;
    Node *RightChild = NULL;
    Node(token_t value, NodeTypes type);
    void InsertLeft(token_t NodeValue, NodeTypes NodeType = NOTHING);
    void InsertRight(token_t NodeValue, NodeTypes NodeType = NOTHING);
    void BrowseUp();
};

*.cpp

Node(token_t value, NodeTypes type) {
    NodeValue = value;
    NodeType = type;
}
void InsertLeft(token_t value, NodeTypes type) {
    if (LeftChild == NULL)
        LeftChild = new Node(value, type);
    else {
        Node NewNode = Node(value, type);
        NewNode.LeftChild = LeftChild;
        LeftChild = &NewNode;
    }
}
void InsertRight(token_t value, NodeTypes type) {
    if (RightChild == NULL)
        RightChild = new Node(value, type);
    else {
        Node NewNode = Node(value, type);
        NewNode.RightChild = RightChild;
        RightChild = &NewNode;
    }
}
void BrowseUp() {
    std::cout << NodeValue.value << " ";
    if (LeftChild) LeftChild->BrowseUp();
    if (RightChild) RightChild->BrowseUp();
}

使用它：

Node main = Node(NodePosition, NodeType);
SetMainAst(main, expr);
main.BrowseUp();

SetMainAst:

void SetMainAst(Node &node, Expr expr, NodeTypes type = NodeTypes::NOTHING) {
    std::array<Expr, 3> exp = CutExpr(expr, GetNodePosition(expr));
    Expr left = exp[0], right = exp[2];
    token_t value = exp[1][0];

    if (type == NOTHING) node.NodeValue = value;

    if (!ContainNodes(left)) node.InsertLeft(left[0]);
    else SetMainAst(node, left, DetermineFirstNode(expr));
    if (!ContainNodes(right)) node.InsertRight(right[0]);
    else SetMainAst(node, right, DetermineFirstNode(expr));
}

CutExpr() 允许在 3:

中剪切表达式

左值；
节点；
右值。

我用 this 帮助自己（它在 python 中，但我用 C++ 转录了它）。

使用单个节点表达式，它会产生奇迹。但是，当有多个节点时，它不再起作用：BrowseUp() 在显示主节点（即本例中的等号）后停止程序。

我真的不明白，但我很好地遵循了教程并且认为我在 C++ 中转录得很好......也许这是一个 pointer/reference 问题？

如果你能帮我解决这个问题（已经困扰我3天了），我将不胜感激。

Answer 1

这个

    Node NewNode = Node(value, type);
    NewNode.LeftChild = LeftChild;
    LeftChild = &NewNode;

是错误的，因为您正在存储指向即将被销毁的对象的指针（当您退出 if ... else 语句时）。

你可能想要这样的东西

    Node* NewNode = new Node(value, type);
    NewNode->LeftChild = LeftChild;
    LeftChild = NewNode;

您正在从具有垃圾回收功能的 Python 转录到没有垃圾回收功能的 C++。所以你必须自己添加内存管理。

语言分析的二叉树实现-作为节点的子节点：不起作用

Binary tree implementation for language analyse - child as node: does not work

c++

tree

parsing

abstract-syntax-tree