Mutually dependent structs in C

Question

I am following Ruslan Spivak's article series/tutorial "Let's Build A Simple Interpreter", which is a guide for building a simple Pascal interpreter in Python. I am trying to follow along in C. I'm stumped at the part about adding an Abstract Syntax Tree.

I have this header file:

#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;
};

where "tokens.h" includes the token typedef'd struct.

My problem is that my compiler:

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

throws out Incomplete Type errors.

From these links:
http://c-faq.com/decl/mutrefstructs.html
Circular definition in C
my guess is that I have to use pointers, but I have absolutely no idea where.

Answer 1

You can declare structs first then reference them as pointer later.

In C, when a struct A includes another struct B, A will need memory area for size of B. If struct A includes struct B and struct B includes struct A, compiler can't decide how much memory it should allocate for each structs. So if you want to use structs referencing each other, you should use at least one of them as pointer.

#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;
};