通过递归下降解析创建 cons cell 结构

Question

我目前正在研究一个用 C 语言编写的 Scheme Interpreter。我正在尝试通过递归下降解析创建一个 cons 单元结构，除了 car 和 cons 之外，我还有一个包含 token 的字段我从词法分析器(提供给我们)收到的。我所描述的 struct 是这样的:

typdef struct node node;

typedef node* list;

struct node { 
    char* symbol;
    list car;
    list cdr;
};

因此，cons 单元将是(节点表示为 [symbol][car][cdr])，[null][car][cdr]，而符号将是 [symbol][null][null]。

例如，(a b c) 将表示为:

和(a (b c) d)，将表示为:

上一篇关于堆栈溢出的文章:Cons Cell data structure in C几乎是在处理相同的任务。在 Jason 对该帖子的最佳回答中，他的一个建议是在递归解析输入时将标记放入堆栈中，然后从该堆栈将其输入到 cons 单元结构中。

这是我现在正在努力的事情，因为它对我来说更容易理解，而且我之前已经在 C 中实现了一个堆栈，但我知道我可以递归地构建结构，我只是不确定如何。以下是我的伪代码:

list s_expression() {
    list local;
    list temp;

    if (token == "(") {
        token = getToken();
        local = new node;
        local -> car = s_expression()
        temp = local;

        while (token != ")") {
            temp -> rest = new node;
            temp = temp -> rest;
            temp -> first = s_expression()
        }

        temp -> rest = NULL;
        token = getToken();
    } else if (token == symbol) {
        list symbolNode = new node;
        symbolNode -> symbol = token;
        token = getToken()
        return symbolNode;
    } else {
        return local;
    }
}

s_expression 应该返回指向递归构建的 cons 单元结构的指针。我只是在弄清楚何时调用 getToken() 时遇到问题，因为我在错误的位置调用了 getToken 并且无意中跳过了一个标记，或者我调用了 getToken() 当我完成获取所有 token 时，从而导致我的程序继续从用户输入中搜索 token ，而不是继续执行程序的其余部分。

我应该什么时候调用 getToken()？

此外，在您通过用户输入时递归构建 cons cell 结构，或者将所有 token 放入堆栈中，然后使用该堆栈构建 cons cell 结构，哪个更好？

如果需要，我可以发布提供给我们的词法分析器。

Answer 1

我在想，如果你读到的第一件事是一个符号，那么就没有其他标记，所以符号读取不应该得到新的标记。当你读完一份 list 时也是如此。

当标记为“(”并读取一个符号或表达式后，您将不会有新标记。因此在 while 中的谓词之前，您需要读取新标记，因为您知道您正在搜索结尾列表。这意味着在您进入 while 循环之前和在您读取正文中的 s_expression 之后。

其他观察结果

谓词 token == symbol 看起来很奇怪。你只允许使用相同的符号吗？除了列表和符号之外，是否还有其他数据类型可以证明这里不仅有 else ？

最后的 else(替代)永远不会被命中。因此，在阅读列表时，您永远不会返回任何内容。