c++ - 语言分析的二叉树实现-子节点为 : does not work

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();

设置主助手:

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++ 中转录得很好......也许这是一个指针/引用问题？

如果你能帮我解决这个问题(已经困扰我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++。因此你必须自己添加内存管理。