c - Bison 递归在链表中表现异常

Question

我有一个类似链表的结构:

typedef struct NODE
{
  NODE_TYPES type;
  struct NODE* curr;
  struct NODE* next;
} NODE;

我有这个递归规则:

lines: stmt             {
                            root -> next = $1;
                            $1 -> next = NULL;
                            $$ = $1;

                        }
| lines stmt            {
                            $1 -> next = $2;
                            $2 -> next = NULL;
                            $$ = $2;

                        }
;

stmt 始终是指向 NODE 结构的指针。

root 被定义为 NODE *root 之后，在 main 函数中，这样分配:root = malloc(sizeof(NODE));

但是，从 root 开始递归地打印我的节点列表，我只得到最后一个节点。为什么我会丢失 root 和最后一个节点之间的数据？

Answer 1

显然，问题在于您将 stmt 的语义值设置为指向堆栈分配的局部变量。由于局部变量的生命周期在语义操作完成后立即到期，因此该值是一个悬空指针并且使用它是未定义的行为。 (但在这种情况下，您可能会发现所有指针都指向同一个内存块，每次重复使用该特定堆栈帧时，其内容都会发生变化。)

您需要确保 stmt 的值是指向新分配的 NODE 的指针:

stmt : /* ... something ... */ 
                  { $$ = malloc(sizeof *$$);
                    $$ = (NODE){/* ... */, .next = NULL; }

这很重要。如果没有某种堆分配新 NODE 的函数，就没有好的方法可以做到这一点。您可以尝试通过保留一个 NODE 池并自己回收它们来减少 malloc 开销，但是由于大多数现代 malloc 实现在回收小型固定大小分配方面做得很好，这是过早的优化。

链表代码适用于简单的语句，但依靠全局变量来维护链表头部的可扩展性不是很好。这将使解析复合语句(例如条件和循环)变得不可能，因为您最终将重用 root 作为内部语句列表。最好以自然的方式构建列表(这将是倒退的)并在最后反转它:

stmts: stmt       /* Default action is fine */
     | stmts stmt { $$ = $2; $$->next = $1; }
line : stmts      { $$ = reverse($$); }

在这个简单的代码中，每次 stmts: stmts stmt 减少时，它都会将新的 NODE 推到列表的前面，这显然是反向创建列表命令。所以当 line 减少时(这将在所有 stmt 被解析之后)，列表需要被反转。可以原地反转:

NODE* reverse(NODE* last) {
  NODE* next = NULL;
  while (last) {
    NODE* tmp = last->next; 
    last->next = next;
    next = last;
    last = tmp;
  }
  return next;
}

这完全消除了对全局 root 的需要，因此可以正确组装复合语句。