1

我正在创建一个编译器，并开始创建我的解析树结构。

我有一个可以包含子节点或不包含子节点的“节点”。

typedef struct Node {
    int node_type;
    union {
        char* string;
        int number;
        struct Node* nodes;
    } node_data;
} Node;

这些功能组装/打印它

Node* MakeNodeFromString(char* mystring) {
    Node* mynode = (Node*) malloc(sizeof(Node));
    mynode->node_data.string = strdup(mystring);
    mynode->node_type = 0; // @TODO not 3
    return mynode;
}

Node* MakeTwoBranchNode(int nodetype, Node* a, Node* b) {
    Node* mynode = (Node*) malloc(sizeof(Node));
    mynode->node_type = 2; // @TODO not 3
    mynode->node_data.nodes = malloc(2 * sizeof(Node*));
    mynode->node_data.nodes[0] = *a; mynode->node_data.nodes[1] = *b;
    return mynode;
}

void printtree (Node *n, int level) {
    if (!n) return;

    printf ("start %d\n", n->node_type);
    switch (n->node_type) {
        case 2:
            printf ("%*c2\n", level, ' ');
            printtree (&n->node_data.nodes[0], level+1);
            printtree (&n->node_data.nodes[1], level+1);
            break;
        case 0:
            printf ("%*c%s\n", level, ' ', n->node_data.string);
            break;
    }
    printf ("end %d\n", n->node_type);
}

每当我组装一棵树时，我都会得到段错误，要么 printf'ing 要么 strlen'ing 我的字符串。我已经尝试过 strdup、strcpy 等。我很确定它不是 MakeTwoBranchNode 失败的，因为我可以创建大的数字树（不包括代码）。但我不确定。

这是一个代码示例，说明它在我的机器上会发生并且不会发生段错误

int main() {
    // Works
    printtree(
        MakeTwoBranchNode(3,
            MakeNodeFromString("first string"),
            MakeNodeFromString("second string")
        ),
        1
    );
    // Fails
    printtree(
        MakeTwoBranchNode(3,
            MakeTwoBranchNode(3,
                MakeNodeFromString("first string"),
                MakeNodeFromString("second string")
            ),
            MakeNodeFromString("third string")
        ),
        1
    );
}

如果您运行此示例（并且可以理解其神秘的输出），您将在 printf(n->node_data.string) 期间看到它的段错误。

4

2 回答 2

3

您在以下分配 sizeof-a-pointer，而不是 sizeof-a-node：

Node* MakeTwoBranchNode(int nodetype, Node* a, Node* b) {
    Node* mynode = malloc(sizeof(Node));
    mynode->node_type = 2; // @TODO not 3
    mynode->node_data.nodes = malloc(2 * sizeof(Node*)); // HERE
    mynode->node_data.nodes[0] = *a; mynode->node_data.nodes[1] = *b;
    return mynode;
}

您可以将上面的注释行更改为：

    mynode->node_data.nodes = malloc(2 * sizeof(Node));

但是，正如您编写的测试程序一样，存在内存泄漏。您为传递到的节点分配的内存会发生什么变化MakeTwoBranchNode()？这不是我认为你真正想要的。首先使用指针数组会更好。

typedef struct Node {
    int node_type;
    union {
        char* string;
        int number;
        struct Node *nodes[2];
    } node_data;
} Node;

然后保存传递给MakeTwoBranchNode. 在这样做时，您将这些节点的所有权传递给两个分支节点（因此您还应该确保在释放它时正确清理其子节点）：

Node* MakeTwoBranchNode(int nodetype, Node* a, Node* b) {
    Node* mynode = malloc(sizeof(Node));
    mynode->node_type = 2; // @TODO not 3
    mynode->node_data.nodes[0] = a; 
    mynode->node_data.nodes[1] = b;
    return mynode;
}

现在没有内存泄漏，除非你没有找到free()指针nodes[0]并且nodes[1]当你破坏两个分支节点时。

于 2013-09-07T17:41:40.977 回答
2 
typedef struct Node {
    int node_type;
    union {
        char *string;
        int number;
        struct Node **nodes; // <-- here
    } node_data;
} Node;


Node *MakeNodeFromString(char *mystring) {
    Node *mynode = malloc(sizeof *mynode);
    mynode->node_data.string = strdup(mystring);
    mynode->node_type = 0; // @TODO not 3
    return mynode;
}

Node *MakeTwoBranchNode(int nodetype, Node *a, Node *b) {
    Node *mynode = malloc(sizeof *mynode);
    mynode->node_type = 2; // @TODO not 3
    mynode->node_data.nodes = malloc(2 * sizeof *mynode->node_data.nodes ); // <- here
    mynode->node_data.nodes[0] = *a; mynode->node_data.nodes[1] = *b;
    return mynode;
}

void printtree (Node *n, int level) {
    if (!n) return;

    printf ("start %d\n", n->node_type);
    switch (n->node_type) {
        case 2:
            printf ("%*c2\n", level, ' ');
            printtree (n->node_data.nodes[0], level+1); // <-- here
            printtree (n->node_data.nodes[1], level+1); // <- and here
            break;
        case 0:
            printf ("%*c%s\n", level, ' ', n->node_data.string);
            break;
    }
    printf ("end %d\n", n->node_type);
}
于 2013-09-07T17:47:11.930 回答