Bison 递归在链表中表现异常

Question

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

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

我有这个递归规则：

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

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

                        }
;

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

root 被定义为 NODE *root 之后，在主函数中，这样分配：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 { $$ = ; $$->next = ; }
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 的需要，因此可以正确组装复合语句。

Bison 递归在链表中表现异常

Bison recursion behaving strangely with linked list

c

parsing

yacc

bnf

bison