I Built a Self-Compiling C Compiler from Scratch: acwj Exposed

I Built a Self-Compiling C Compiler from Scratch: acwj Exposed

What if I told you that the most intimidating concept in computer science—the C compiler itself—is something you could build with your own two hands?

Not by reading thousand-page theory textbooks. Not by memorizing dragon book algorithms you'll never implement. But by actually writing code, one working piece at a time, until suddenly you're staring at a compiler that can compile itself.

Sound insane? That's exactly what Warren Toomey did with acwj—"A Compiler Writing Journey"—and the results are nothing short of remarkable. This isn't another abandoned toy project or half-broken educational exercise. This is a real, self-compiling compiler for a substantial subset of C, documented across 64 painstakingly detailed steps that take you from zero to bootstrapped compiler.

If you've ever felt that compilers were some kind of dark magic reserved for language wizards at Google or the LLVM foundation, prepare to have that illusion shattered. The acwj repository proves that compiler construction is fundamentally a learnable, incremental craft—and the journey might just be the most rewarding programming experience of your career.

What is acwj? The Self-Compiling C Compiler That Demystifies Everything

acwj (short for "A Compiler Writing Journey") is an open-source educational project created by Warren Toomey, a computer scientist with deep roots in Unix history and systems programming. Hosted at , this repository documents the complete construction of a self-compiling compiler for a meaningful subset of the C programming language.

But here's what makes acwj genuinely special: it's not a dump of final source code with a "figure it out" attitude. Instead, Toomey meticulously documented every single incremental step of the build process across 64 numbered parts, each with its own detailed explanation, working code, and theoretical context. You don't just see what he built—you understand why he built it that way, what alternatives he considered, and what pitfalls he encountered.

The project emerged from a simple, radical premise: compiler theory is over-taught and compiler practice is under-taught. Traditional compiler courses drown students in LR(1) parsing tables and formal grammars before they've written a single line of scanner code. acwj flips this script entirely. You start with a basic scanner, build a recursive descent parser, generate actual assembly code, and progressively add real C features—variables, functions, pointers, structs, arrays, the preprocessor—until you have something that can compile its own source code.

This approach has struck a nerve in the developer community. In an era where software development increasingly feels like gluing together black-box dependencies, acwj represents something increasingly rare: deep, from-first-principles understanding. The repository has attracted attention from systems programmers, language enthusiasts, and self-taught developers who want to understand what happens when they type gcc hello.c.

The project has also evolved substantially. What began as a direct-to-assembly compiler later gained a QBE backend (a compiler infrastructure generating efficient assembly) and even a 6809 CPU target—demonstrating that the core compiler knowledge transfers across architectures. Toomey has since moved on to building alic, a new language from scratch, but acwj remains a complete, self-contained masterclass in compiler construction.

Key Features: What Makes acwj a Technical Marvel

The acwj compiler isn't a stripped-down toy that handles only arithmetic expressions. It implements a genuinely useful subset of C that demonstrates all major compiler phases and techniques:

Complete Compiler Pipeline: acwj implements the full chain from source code to executable—lexical analysis, parsing, semantic analysis, intermediate representation, optimization, and code generation. You see how characters become tokens, tokens become ASTs, and ASTs become assembly instructions that actually run on real hardware.

Recursive Descent Parsing with Operator Precedence: Rather than using parser generators like Yacc or Bison, acwj hand-rolls a recursive descent parser with Pratt parsing for expressions. This is the technique used in many production compilers (including early GCC versions) and teaches you to think about grammars as executable code, not abstract tables.

Multi-Architecture Code Generation: The compiler initially targeted x86-64 assembly directly, then gained a QBE backend for cleaner intermediate representation and optimization. The addition of a 6809 CPU target proves the architecture-agnostic nature of well-designed compiler frontends.

Self-Compilation (Bootstrapping): The ultimate test of any compiler—can it compile itself? acwj passes this triple test (compiling itself, then using that output to compile itself again, verifying identical results). This isn't just a party trick; it's how real compilers like GCC and Clang prove correctness.

Progressive Complexity with Working Code at Every Step: Each of the 64 parts represents a compileable, testable milestone. You're never more than a few hundred lines from a working program. This incremental approach means you can actually run and debug your compiler at every stage, building intuition through experimentation.

Production-Grade Features Implemented: Local and global variables, function declarations and calls with proper parameter passing, pointers and pointer arithmetic, arrays (both local and global), structs and unions with member access, enums and typedefs, the C preprocessor with #include and #define, control flow (if/else, while, for, switch, break, continue), the ternary operator, type casting, sizeof, static storage, and even constant folding optimization.

Use Cases: Where acwj Transforms Your Development Career

Systems Programming Interviews: When interviewers ask "how does a compiler work?" most candidates recite vague textbook answers. Imagine instead walking through how you implemented register spilling or designed struct layout. acwj gives you war stories that separate you from the pack.

Programming Language Design: Before you design your own language, you need to understand how existing languages are implemented. acwj's 64-part structure shows exactly which features interact dangerously (the "dangling else" problem, lazy evaluation semantics, lvalue rules) and how to resolve them.

Security Research and Reverse Engineering: Understanding compiler internals is essential for analyzing compiled binaries, writing decompilers, or finding compiler-introduced vulnerabilities. The ARM backend and QBE integration in acwj teach you how high-level constructs map to low-level instructions.

Embedded Systems Development: The 6809 backend demonstrates targeting constrained architectures. If you work with microcontrollers where every byte matters, understanding how your compiler generates code lets you write C that compiles to efficient assembly.

Educational Curriculum Design: Computer science educators use acwj as a complete, free alternative to expensive compiler textbooks. The progression from scanner to self-compilation maps perfectly to a semester-long course, with each part corresponding to 1-2 lectures plus lab time.

Contributing to Open Source Compilers: Projects like GCC, Clang, and Rust's rustc need contributors who understand compiler pipelines. acwj builds the mental models necessary to navigate these massive codebases and make meaningful contributions.

Step-by-Step Installation & Setup Guide

Getting started with acwj requires minimal dependencies—fitting for a project that values simplicity and understanding over complexity.

Prerequisites

You'll need a Unix-like environment (Linux, macOS, or WSL on Windows) with:

• A standard C compiler (GCC or Clang) for bootstrapping
• make for build automation
• git for cloning the repository

Clone and Explore

# Clone the repository
git clone https://github.com/DoctorWkt/acwj.git
cd acwj

# Explore the structure—each part is self-contained
ls -la
# You'll see directories like 00_Introduction, 01_Scanner, etc.

Building a Specific Part

Each part builds independently. Here's how to compile Part 4, the first "actual compiler":

cd 04_Assembly
# Examine the Makefile to understand the build process
cat Makefile
# Typically: make to build, make test to verify
make
make test

Bootstrapping the Full Compiler

For the complete self-compiling experience, navigate to the later parts (60+) where the triple test resides:

cd 60_TripleTest
# Read the README for specific bootstrap instructions
cat Readme.md
# The triple test typically involves:
# 1. Compile the compiler with your system GCC
# 2. Use that compiler to compile itself
# 3. Use the resulting compiler to compile itself again
# 4. Verify outputs 2 and 3 are identical
make tripletest

Setting Up the QBE Backend (Advanced)

cd 63_QBE
# Ensure QBE is installed on your system
# On Debian/Ubuntu: sudo apt-get install qbe
# On macOS: brew install qbe
make
# This generates QBE IL instead of direct assembly
# QBE then optimizes and generates target assembly

Environment Tips

• Start from the beginning: Don't jump to Part 60. The journey is designed sequentially; each part assumes you've understood previous concepts.
• Use diff extensively: Compare your modifications against the reference implementation when stuck.
• Keep a journal: Document what breaks and why—this mirrors real compiler debugging.

REAL Code Examples from the Repository

Let's examine actual code from acwj's progression, showing how the compiler evolves from simple scanner to sophisticated language processor.

Example 1: Basic Scanner Structure (Part 1)

The journey begins with lexical analysis—breaking source code into meaningful tokens. From 01_Scanner/scan.c:

// Skip whitespace and comments, then identify the next token
int scan(struct token *t) {
  int c, tokentype;

  // Skip whitespace: spaces, tabs, newlines are irrelevant to parsing
  c = skip();

  // Determine token type based on first character
  switch (c) {
    case EOF:
      t->token = T_EOF;
      return 0;
    case '+':
      t->token = T_PLUS;
      break;
    case '-':
      t->token = T_MINUS;
      break;
    case '*':
      t->token = T_STAR;
      break;
    case '/':
      t->token = T_SLASH;
      break;
    // ... additional single-character tokens
    default:
      // If digit, scan an integer literal
      if (isdigit(c)) {
        t->intvalue = scanint(c);
        t->token = T_INTLIT;
        break;
      }
      // Unknown character is a fatal error at this stage
      printf("Unrecognised character %c on line %d\n", c, Line);
      exit(1);
  }
  return 1;
}

This scanner is intentionally minimal—just enough to recognize arithmetic operators and integer literals. The key insight: you don't need a perfect scanner on day one. You need one good enough for your current parser, then you extend it. Notice the struct token abstraction that separates lexical representation from syntax processing.

Example 2: Recursive Descent Expression Parsing (Part 3)

Operator precedence is where parsers get interesting. From 03_Precedence/expr.c, acwj implements Pratt parsing—a top-down operator precedence technique:

// Parse a primary expression: integer literals or parenthesized expressions
static int primary(void) {
  int n;

  switch (Token.token) {
    case T_INTLIT:
      // For integer literals, load the value and advance
      n = Token.intvalue;
      scan(&Token);
      return n;
    case T_LPAREN:
      // Parentheses: scan past '(', parse inner expression, expect ')'
      scan(&Token);
      n = binexpr(0);
      rparen();
      return n;
    default:
      printf("syntax error on line %d\n", Line);
      exit(1);
  }
  return 0;  // Unreachable, but satisfies compiler
}

// Binary expression parser with precedence climbing
int binexpr(int ptp) {
  int left, right;
  int tokentype;

  // Get the left-hand side
  left = primary();

  // If no operator follows, we're done
  tokentype = Token.token;
  if (tokentype == T_SEMI || tokentype == T_RPAREN)
    return left;

  // While current token is a binary operator with sufficient precedence
  while (op_precedence(tokentype) > ptp) {
    scan(&Token);  // Consume the operator
    
    // Recursively parse the right side with higher precedence
    // This handles left-associativity naturally
    right = binexpr(op_precedence(tokentype));
    
    // Generate code for this operation (simplified here)
    left = arithop(tokentype, left, right);
    
    tokentype = Token.token;
    if (tokentype == T_SEMI || tokentype == T_RPAREN)
      return left;
  }
  
  return left;
}

The ptp parameter ("previous token precedence") enables elegant precedence climbing without explicit grammar levels. When parsing 2 + 3 * 4, the * binds tighter because op_precedence(T_STAR) > op_precedence(T_PLUS), causing the recursive call to consume 3 * 4 as a unit before addition occurs.

Example 3: Generating Actual Assembly (Part 4)

The moment of truth—producing runnable code. From 04_Assembly/gen.c:

// Generate code to load an integer literal into a register
void cgload(int value) {
  // Get next free register
  int r = alloc_register();
  
  // x86-64: movq $value, %r
  // The 'r' register names are abstracted: r0=%r8, r1=%r9, etc.
  fprintf(Outfile, "\tmovq\t$%d, %s\n", value, reglist[r]);
  
  return r;
}

// Generate code for addition: left + right
int cgadd(int r1, int r2) {
  // x86-64 addq: destination += source
  // We use r2 as destination, free r1 (dead after use)
  fprintf(Outfile, "\taddq\t%s, %s\n", reglist[r1], reglist[r2]);
  free_register(r1);
  return r2;  // Result is now in r2
}

// Generate code for multiplication
int cgmul(int r1, int r2) {
  fprintf(Outfile, "\timulq\t%s, %s\n", reglist[r1], reglist[r2]);
  free_register(r1);
  return r2;
}

This is real x86-64 assembly generation—not bytecode, not IR, but actual instructions that gcc can assemble into an ELF executable. The register allocator is deliberately simple (round-robin through a small set), yet sufficient for expression evaluation. The key design decision: abstract register names (r0, r1) that map to actual x86-64 registers, making later architecture ports feasible.

Example 4: Function Call Generation (Part 25)

By Part 25, acwj handles the full complexity of C function calls—argument passing, stack frames, and register preservation. From 25_Function_Arguments/cg.c:

// Generate code to call a function with arguments
int cgcall(int r, int numargs) {
  // x86-64 System V AMD64 ABI: first 6 integer args in registers
  // rdi, rsi, rdx, rcx, r8, r9
  // Our simple compiler puts arguments on the stack, so we need to
  // pop them into the correct registers (in reverse order)
  
  int outr = alloc_register();
  int i;
  char *argregs[6] = {"%rdi", "%rsi", "%rdx", "%rcx", "%r8", "%r9"};
  
  // Pop arguments from our stack into ABI registers
  for (i = numargs - 1; i >= 0; i--) {
    fprintf(Outfile, "\tpopq\t%s\n", argregs[i]);
  }
  
  // Call the function
  fprintf(Outfile, "\tcall\t%s\n", gsym(r));
  
  // Return value is in %rax, move to our register
  fprintf(Outfile, "\tmovq\t%%rax, %s\n", reglist[outr]);
  
  return outr;
}

This reveals the ABI compliance challenge: your compiler must speak the platform's calling convention to interoperate with system libraries. The code shows pragmatic evolution—early parts used simpler (non-standard) calling conventions, but real C compatibility requires following the System V AMD64 ABI used on Linux.

Advanced Usage & Best Practices

Study the Refactoring Parts: Parts 29, 52, 57, and 62 are explicitly about refactoring. Compare before and after to learn how compiler codebases evolve. Notice how early design decisions create technical debt that must be paid.

Implement Your Own Backend: After understanding the QBE backend (Part 63), try targeting another architecture. The 6809 backend (Part 64) demonstrates that even 8-bit vintage CPUs are viable targets—perfect for retrocomputing projects.

Extend the Language: Add a feature C lacks—nested functions, algebraic data types, or array bounds checking. This forces you to understand every phase the feature touches, from scanner to code generation.

Benchmark Against GCC: Compile identical programs with acwj and GCC. Compare assembly output to understand optimization gaps. The constant folding (Part 44) is just the beginning—what would strength reduction or loop unrolling look like?

Use for Teaching: The 64-part structure maps to approximately 15 weeks of instruction. Each part includes exercises: "modify the scanner to handle hex literals," "add the do-while statement," etc.

Comparison with Alternatives

Why choose acwj? If you specifically want to understand C compilation, systems programming, or bootstrapping, nothing else matches. LLVM tutorials teach you LLVM's API, not fundamental code generation. Crafting Interpreters is brilliant but targets a higher-level language. acwj sits in a unique sweet spot: real enough to compile itself, simple enough to understand completely.

FAQ: Your Burning Questions Answered

Is acwj a production-ready C compiler? No, and it's not intended to be. It implements a substantial subset of C but lacks features like full standard library support, complex optimizations, and complete C99/C11 compliance. It's a learning tool that happens to be remarkably capable.

How long does it take to work through all 64 parts? Dedicating 5-10 hours per week, most developers complete the journey in 3-4 months. The early parts (1-10) are rapid; the middle sections (20-40) require deeper engagement with type systems and memory layout.

Do I need prior compiler knowledge? Absolutely not. That's the entire point. Basic C programming proficiency is assumed, but no formal language theory. Toomey introduces concepts like precedence climbing and lvalues exactly when needed.

Can I use acwj code in my own projects? Yes, under GPL3 for code and CC BY-NC-SA 4.0 for documentation. Be aware of the SubC heritage noted in the README—some ideas derive from Nils M Holm's public domain work.

What's the difference between acwj and the newer alic project? acwj is a C compiler; alic is an entirely new language. Toomey started alic to apply lessons learned without C's historical baggage. Follow alic for greenfield language design, acwj for understanding existing C infrastructure.

Why not just read the Dragon Book? The Dragon Book (Aho, Ullman, Sethi) is an invaluable reference but a terrible first introduction. It's like learning to drive by studying thermodynamics. acwj gets you driving immediately, then points to theory when relevant.

Does acwj work on ARM Macs or Apple Silicon? The ARM backend (Part 14) and QBE backend provide paths for ARM support. However, macOS-specific ABI details may require additional work—the project was developed primarily on Linux.

Conclusion: Your Compiler Journey Starts Now

Warren Toomey's acwj represents something rare in modern software education: a complete, honest, incremental path to understanding one of computing's most fundamental tools. In 64 carefully crafted steps, you transform from someone who runs gcc as a black box into someone who could, given time, build the box itself.

The self-compiling achievement isn't merely technical—it's philosophical. It embodies the bootstrapping principle that underlies all software: we build tools with tools, then use those tools to build better tools. Understanding this cycle makes you not just a better programmer, but a more empowered creator who can shape the computational infrastructure others merely consume.

Whether you're preparing for systems interviews, designing your own language, or simply satisfying years of curiosity about what happens when you press "compile," acwj delivers. The repository at awaits—64 parts, zero prerequisites, infinite depth.

Stop treating compilers as magic. Start your journey today.