C语言中的Cons单元数据结构

Question

我是C语言的新手，正在构建一个小型Scheme解释器的早期阶段。在这个项目的这一部分中，我正在尝试构建一个简单的cons单元数据结构。它应该像这样内部表示：

(a b c)

并将其表示为:

[ ][ ] -> [ ][ ] -> [ ][/]
 |         |         |
 A         B         C 

为了测试它是否正常工作，我有一个打印函数来输出输入。以下是不起作用的代码：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "lexer.h"
#include "parse.h"

char token[20]; 


struct conscell {
    char *data;
    struct conscell *first, *rest;
};

void S_Expression ()
{   
    /* function from lexer to receive input a split into tokens no greater than 20 */
    startTokens(20);

    /* gets the next token */
    strcpy(token, getToken());

    /* List is a typedef for the struct conscell */
    List tree = createList ();
    tree = nextNode (tree);
    printList(tree);

}


List createList ()
{
    List node = malloc(sizeof (List));

    if (node == NULL) {
        printf("Out of memory!\n");
        exit(1);
    }
    node->data = NULL;
    node->first = NULL;
    node->rest = NULL;

    return node;
}

/* Recursive function to build cons cell structure */
List nextNode (List node)
{
    node = createList ();

    if (token[0] == '(')
    {         
       strcpy(token, getToken());
       node->first = nextNode(node->first);
       node->rest = nextNode(node->rest);         
     }

    else
    {
       if (token[0] == ')')
       {
          node = NULL;
       }

       else
       {
           List temp = createList();
           temp->data = token;
           temp->first = NULL;
           temp->rest = NULL;

           node->first = temp;

           strcpy(token, getToken());
           node->rest = nextNode(node->rest);            
       }
   }
   return node;
}

/* Prints output. So far, just trying to print symbols */
void printList(List node)
{
    if (node != NULL)
    {
      if (node->data != NULL)
      {        
        printf("%s", node->data);

      }
    }
}

到目前为止，什么都无法打印出来。我几乎可以确定这是一个指针问题。如果有人能够指点我（没有双关语），那将不胜感激。

谢谢。

- illmatic

---

那不是一个 cons 单元；cons 单元只有两个成员，car 和 cdr。nextNode 中也存在内存泄漏问题。你还在将指针复制到随后被覆盖的缓冲区中。 - Fred Foo

你尝试过在调试器中逐步执行代码吗？或者添加printf语句来显示代码中变量的值吗？此外，你还没有提供“List”的定义。 - Oliver Charlesworth

@larsmans 谢谢您的反馈，现在更有意义了。 - illmatic

@Oli Charlesworth 是的，在整个代码中，我使用 printf 语句来显示不同的值，但是没有注意到缓冲区每次都会被覆盖。我在发布问题时将它们删除了。忘了提一下，List 是 conscell 的 typedef。 - illmatic

Answer 1

首先，我假设List是struct conscell*的typedef。如果不是，它应该是，否则你的代码将无法编译，会出现大量警告。

Scheme cons单元格应该是一个简单的单向链表，而不是双向链表。因此，你的单元格应该更像：

typedef conscell 
{
    unsigned char *data;   //<== use unsigned char for a memory buffer
    struct conscell* next; //<== only a "next" pointer needed
} conscell;

我看到你目前只是想打印符号，所以使用char而不是unsigned char可以实现这个目的。但是当你使用更通用的数据结构，如lambda等时，你需要切换到unsigned char*或void*以引用保存这些类型更复杂的数据结构的内存缓冲区。

另一个有点令人困惑的问题是，你把每个cons单元格都变成了另一个cons单元格，例如，这些代码行：

if (token[0] == '(')
{         
   strcpy(token, getToken());
   node->first = nextNode(node->first);
   node->rest = nextNode(node->rest);         
 }

你正在以递归方式将cons单元格作为“first”和“rest”添加...但这不是链表应该像的样子。 它应该具有指向列表节点的指针作为列表的“头部”（而不是另一个cons单元格，就像你在这里做的那样），然后列表中的每个节点都指向某些数据和列表中的下一个节点。

接下来，在您的 createList()函数中存在诸多内存泄漏问题，因为您使用它分配了内存，但从未删除该内存（也就是说，您有类似 node = NULL 的代码，实际上是内存泄漏，因为您已经失去了对最初指向的分配内存位置的内存引用 node ）。在将 NULL 赋值给它之前，必须在节点指针上调用 free（）。

最后， printList（）除了打印传递给它的列表的第一个元素之外，什么也没做...没有递归调用或循环来循环到链接列表中的下一个节点。 所以你不会用这个功能打印太多东西。它应该看起来更像：

void printList(List node)
{
    List current = node;

    while (current != NULL)  //<== guard for the end-of-list
    {
      if (node->data != NULL)
      {        
        printf("%s", node->data);
      }

      current = current->next; //cycle to the next node in the linked list
    }
}

因此，总结一下，1）您的cons数据结构应该表示由一个结构数据类型组成的单向链表，该数据类型具有数据元素和指向下一个节点的指针。通过一个头指针指向第一个节点来访问连接列表。2）在解析输入时，应将节点添加到链表的前面，因为Scheme的cons操作，以及实际上Scheme中的所有操作都是递归的，并且“向右折叠”，这意味着它们从基本情况开始（即两个元素的连接），然后在该基本情况上扩展。因此，如果您有像（cons'd（cons'c（cons'b（cons'a''））））这样的东西，则会打印列表（d c b a）。如果您愿意，也可以在递归解析输入时将标记放入堆栈中，然后从堆栈中输入到链接列表中（就像RPN计算器的工作方式一样）。

- Jason

---

哇，非常感谢您详细的回复。我应该提到我想要一个递归下降解析器，这会改变什么吗？它与使用单向链表有什么不同吗？我喜欢堆栈的想法，谢谢。今晚将根据您的建议进行工作。 - illmatic

一个递归解析器和一个单向链表是两个不同的东西。你正在将解析后的数据存储在一个单向链表中。你应该将这两个概念分开，以便无论你决定如何解析输入数据，它都将以一种良好抽象的格式存储，以便于应用该数据。 - Jason

Answer 2

还要在你的printf语句中加入\n以确保输出被刷新到stdout：

printf("%s\n", node->data);

- eyalm