C中相互依赖的结构

Question

我正在关注 Ruslan Spivak 的文章 series/tutorial“让我们构建一个简单的解释器”，这是在 Python 中构建一个简单的 Pascal 解释器的指南。我正在尝试在 C 中进行操作。我对添加抽象语法树的部分感到困惑。

我有这个头文件：

#include "tokens.h"
struct binopnode
{
    struct node left;
    token op;
    struct node right;
};

struct node
{
    union nvalue value;
    enum ntype type;
};

enum ntype
{
    NUM,
    BINOP,
};

union nvalue
{
    struct binopnode binop;
    struct numnode num;
};

struct numnode
{
    token tok;
};

其中 "tokens.h" 包含 token typedef 结构。

我的问题是我的编译器：

Apple clang version 12.0.5 (clang-1205.0.22.9)
Target: x86_64-apple-darwin20.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

抛出 Incomplete Type 个错误。

来自这些链接：
http://c-faq.com/decl/mutrefstructs.html
Circular definition in C
我的猜测是我必须使用指针，但我完全不知道在哪里。

Answer 1

在Python中，对象不能包含其他对象。 Python 中的对象只能包含对另一个对象的引用。

因此，在 Python 中，class BinOp 的对象包含三个引用 - self.left、self,right 和 self.op。但它实际上并不包含三个对象。

在C中，一个结构实际上可以包含其他结构。因此，struct binop 类型的对象（在 C 语言中，“对象”一词仅表示解释为特定类型的内存区域 - 不太像 Python 对象）将包含两个类型 struct node 以及 token.

类型之一

在 C 中，所有类型都必须有大小。让我们找到一些大小的下限（这些只是下限，因为我们必须考虑填充）。

sizeof(struct binop) >= sizeof(struct node) + sizeof(token) + sizeof(struct node)

sizeof(struct node) >= sizeof(union nvalue) + sizeof(enum ntype)

sizeof(union nvalue) >= min(sizeof(struct binop), sizeof(struct numnode)) >= sizeof(struct binop)

所以我们知道 sizeof(struct binop) >= sizeof(struct node) + sizeof(token) + sizeof(struct node) > sizeof(struct node) >= sizeof(union nvalue) >= sizeof(struct binop).

因此，sizeof(struct binop) > sizeof(struct binop).

这是个问题，因为数字不能大于它本身。所以 C 无法为您编译此代码，因为它不知道 struct binop 应该有多大。

事实上，任何时候 struct 以这种方式包含自己，没有指针，这将导致严重的问题。

好消息是我们可以通过重新定义来打破这个循环

union nvalue {
    struct binopnode* binop,
    struct numnode num
}

现在，我们可以将 union nvalue 的大小计算为 min(sizeof(struct binopnode*), sizeof(struct numnode))。这完全没问题，因为指针具有固定大小（在 64 位系统上，函数指针以外的任何指针的大小都是 8，无论它指向什么）。

Answer 2

您可以先声明结构，然后再将它们作为指针引用。

在 C 中，当一个结构 A 包含另一个结构 B 时，A 将需要 B 大小的内存区域。如果结构 A 包含结构 B 并且结构 B 包含结构 A，编译器无法决定它应该占用多少内存为每个结构分配。所以如果你想使用相互引用的结构，你应该至少使用其中之一作为指针。

#include "tokens.h"

struct binopnode;
struct node;
enum ntype;
union nvalue;
struct numnode;

struct binopnode
{
    struct node *left;
    token op;
    struct node *right;
};

struct node
{
    union nvalue *value;
    enum ntype type;
};

enum ntype
{
    NUM,
    BINOP,
};

union nvalue
{
    struct binopnode *binop;
    struct numnode *num;
};

struct numnode
{
    token tok;
};

C中相互依赖的结构

Mutually dependent structs in C

c

enums

struct

forward-declaration

unions