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

Question

我一直在尝试实现 AST C++来存储从 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 中剪切表达式：

• 左值 ;
• 节点;
• 右值。

我帮助自己解决了这个问题(它是用 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++。因此，您必须自己添加内存管理。