Implementation of "Writing a C compiler" in Zig

This repository contains an implementation of a C compiler as described in the book "Writing a C compiler" by Nora Sandler. This is not a compiler that supports the full C standard, only what is covered by the book. It does implement all the extra features from the book though. The generated assembly is made for Linux systems, not for macOS, since that is what I am using.

The implementation also doesn't follow the book to the letter. In fact, I tried to apply Zig's data-oriented design as much as possible and minimize the data I keep and the number of allocations I make. I am aware that it can still be significantly improved on these fronts, but I will do that when I write my own language :D.

It took me 10 months in total. I worked on it mostly after work and on weekends, except during the final month and a half, when I had more free time and worked on it most days.

Project Structure

The compiler is organized into several key components, each handling a specific phase of the compilation process:

src/
├── main.zig         - Main entry point and compilation pipeline orchestration
├── driver.zig       - Compiler driver handling file I/O and process management
├── lexer.zig        - Lexical analysis (tokenization)
├── Ast.zig          - Abstract Syntax Tree definitions and operations
├── Parser.zig       - Syntax analysis and AST construction
├── Sema.zig         - Semantic analysis
├── Tacky.zig        - Tacky IR definitions
├── TackyGen.zig     - Intermediate code generation (Tacky IR)
├── Optimizer        - Optimizer for Tacky IR
├── codegen.zig      - x86_64 assembly code generation
├── RegAllocator.zig - Does register allocation and coalescing on assembly instructions
└── emit.zig         - Assembly code emission

The lexer and AST structure are basically copied from the Zig compiler itself. An AST node looks like this:

pub const Node = struct {
    tag: Tag,
    main_token: TokenIndex,
    data: Data = .{},

    pub const Data = struct {
        lhs: Index = Index.empty,
        rhs: Index = Index.empty,
    };

    pub const Index = enum(u32) {
        empty = 0,
        _,
    }

    pub const Tag = enum(u8) {
        program,
        func_decl,
        func_def,
        func_call,
        block,
        return_stmt,
        ...
    }
}

What Data.lhs and Data.rhs contain depends on the type of the node. For example:

• .constant contains nothing
• .return_stmt contains the index of its value node in lhs
• .func_def contains the start and end index in the extras array which is just std.ArrayList(u32).
  • extras[start] contains the index of the func's body block node,
  • extras[start+1] contains the number of variables used in the body, which will be useful in the next phase to preallocate space for them,
  • extras[start+2] contains the function ID. This is a number that is actually an index of this function in the array of all functions,
  • extras[start+3] contains the function's return type,
  • extras[start+4] is useful only for function declarations, which share a similar structure, and represents a boolean that says whether the declaration is local or global,
  • extras[start+5..end] contains indices of function parameter nodes.

For nodes that keep a lot of data in extras, like .func_def, I also made a helper structure that extracts all the data from extras and gives you readable getters to fetch that data.

Tacky IR instructions are represented similarly:

pub const Instr = struct {
    tag: Tag,
    data: Data,

    pub const Data = packed struct(u64) {
        lhs: Index = Index.empty,
        rhs: Index = Index.empty,
    };

    pub const Index = enum(u32) {
        empty = 0,
        _,
    };

    pub const Tag = enum(u8) {
        constant,
        string_constant,
        copy,
        copyf,
        get_local,
        ...
    }
}

The book says to represent an IR instruction in such a way that it contains two operands and a result location that needs to be named and then referenced by name. I decided to have the instruction itself represent its result, so if a following instruction needs to use the result of the instruction at index #x as its operand, it will just have the number #x in its data.lhs or data.rhs. For example:

// return ~(-2):
0: constant 2
1: negate %0
2: bit_not %1
3: ret %2

So the instruction at index 0 is a constant instruction whose value is 2. At index 1, we have a negate instruction that needs to negate the "result" of the instruction at index 0, which is the constant. Then, at index 2, we have a bit_not instruction that needs to complement the result of the instruction at index 1, and finally, at index 3, we have a ret instruction that needs to return the result of the instruction at index 2.

Finally, in codegen.zig, I represent assembly instructions like this:

pub const Instr = struct {
    tag: Tag,
    data: Data = .{},

    pub const Data = struct {
        dst: Operand = .empty,
        src: Operand = .empty,
    };

    pub const Index = enum(u32) { empty = 0, _ };

    pub const OperandTag = enum(u8) {
        none,
        val,
        val_index,
        reg,
        stack,
        rax_ptr,
        rdx_ptr,
        rax_rdx_ptr,
        rsp_ptr,
        pseudo,
        pseudo_mem,
        data,
        data_offset,
        priv_data,
        priv_data_offset,
        ro_data,
        label,
    };

    pub const OperandWidth = enum(u8) {
        none,
        byte,
        word,
        dword,
        qword,
        double, // qword but for float data
        string, // used only during code generation itself
    };

    pub const Operand = struct {
        tag: OperandTag,
        width: OperandWidth = .none,
        val: u32,

        pub const empty = Operand{ .tag = .none, .val = 0 };
    }
}

At times, I had to be really imaginative in order to fit all the data I need into such small representations.

Build and usage instructions

Since many Zig programmers use VS Code and Zed editors, I included configuration files for those two editors. The file called tasks.json in them contains commands for:

1. building the compiler: zig build -freference-trace=12 --summary all,
2. building and running the compiler: zig build run -freference-trace=12 -- --optimize --all fixtures/example.c (everything after -- is passed as arguments to the built compiler),
3. Running the book's test suite: ./test_compiler ../wcc/zig-out/bin/wcc --chapter 20 --stage run -f --extra-credit

And, if you are interested in enhansing debugging experience with Zig and LLDB, look at .zed/debug.json for some useful tricks.

AI disclaimer

Not a single line of code was written by AI. It wasn't even used as an autocomplete tool. But AI was used. Total usage amounted to $35 of Codex plus some free usage of web chat interfaces of ChatGPT, Gemini and Grok. Some approximate estimates of how it was used are:

1. 90% of all queries were: "My compiler generated example.s from example.c. Find what is wrong with it, ignoring any optimization issues." This helped me quickly find what I generated incorrectly in longer assemblies, and I could usually find and fix the problem on my own from there.
2. A handful of times I would follow the above with something like: "That problem must have come from some code in <some.zig> file. Can you find where is the problem and just explain it to me without changing any code".
3. The last chapters of the book, dealing with higher-level and lower-level optimizations, were really tricky. I tried AT&T syntax at the start, but I just couldn't read it, so I switched to Intel syntax. However, the tests for the last few chapters actually try to parse and analyze the generated assembly. I used AI to make changes to the local copy of the test project so that it could parse Intel syntax instead of AT&T syntax.
4. In these last chapters, I would also ask AI something like: "My compiler generated example.s from example.c, but the test suite from the 'Writing a C compiler' book is reporting . Look at the reference implementation and my implementation and find what I am doing wrong. Just explain it to me without changing any code."
5. Lastly, I used the free web chat interfaces to ask questions about some corner cases of the C standard or how best to do some things in Zig (since I only had some experience with Zig before this project).

My goal with this project was to learn as much as I could about writing a compiler. I did many of the above things on my own as well, and only when things got very complicated would I ask AI for help.