← Back to Projects
SystemsIteratingFeatured

C Compiler

OCaml compiler from a supported C subset to runnable x86-64, with TACKY IR and instruction fixups in between.

I got tired of treating compilers like magic, so I started building one. Nora Sandler's book gave me the roadmap; I wrote the passes myself. Lexer and parser into an AST, then TACKY to flatten nested expressions, then stack-backed x86 with a fixup pass when memory-to-memory ops are illegal. Right now it honestly covers return constants and nested unaries like return ~(-2);. Broader C is next, but only after each stage stays correct.

Engineering highlights

  • Recursive-descent parser that handles nested unaries like return ~(-2);
  • TACKY IR so nested expressions become temporaries before touching x86
  • Backend fixups rewrite illegal memory-to-memory ops through %r10d
Date
Spring 2026
Focus
Compiler Systems
Build stage
Actively Expanding
Disciplines
Frontend · IR · Backend · Testing
Source code
OCamlRecursive DescentASTSemantic AnalysisTACKY IRx86-64AT&T SyntaxMakeTesting
Pipeline visual
Full write-up below. The hero is the short version. This is the build story: what I designed, what broke, and why I made the calls I did.

Motivation

Why I started this

What pulled me in, and what I wanted to get better at.

Why I built it

I was calling clang for years without knowing what it actually did. Building a compiler seemed like the cleanest way to stop pretending.

What interested me

Parsing is not the hard part. Keeping the same program meaning while the representation gets less human and more machine-shaped is.

What I wanted to learn

Nora Sandler's book was the map. I still had to write the passes, break them, and debug the assembly myself.

System Overview

How the system fits together

mycc is my OCaml compiler for a small C subset. Source to tokens to AST to TACKY to x86 with fixups, then the host assembler and linker. Each stage should make the next one simpler. If it does not, the architecture is lying.

01

Lexer

Turns characters into typed tokens. Removes character-level noise before grammar work begins.

02

Parser

Builds an AST that preserves precedence, associativity, and nesting for the supported grammar.

03

Semantic / resolve passes

Resolves names and control-flow targets so syntax-valid programs are checked for contextual meaning.

04

TACKY IR

Flattens nested expressions into three-address form with temporaries. Separates C syntax from x86 constraints.

05

x86-64 backend

Lowers IR to AT&T assembly, stack-backed temporaries, prologue/epilogue, and scratch-register fixups.

06

Toolchain glue

Assembles and links generated assembly into a runnable binary; Make orchestrates the build.

Data flow

C source → tokens → AST → resolved AST → TACKY IR → x86 pseudo-assembly → operand/instruction fixups → AT&T x86-64 → assembler/linker → executable.

Control flow

Driver invokes passes in order. Early passes fail closed on malformed input; later passes assume prior invariants hold. Official tests currently lock return constants and nested unaries such as return ~(-2);.

Compilation pipeline
C compiler end-to-end pipeline with running example

Running example return ~(-2); shown from source through TACKY and stack-backed x86 with a scratch fixup.

Engineering Breakdown

Broken down by discipline

Each block covers the goal, the design, what broke, what changed, and what shipped.

01Lexing & Parsing

Lexing & Parsing

Goal

Convert raw C source into a structured AST that preserves operator precedence, associativity, and nesting for the supported subset.

Design

The lexer emits typed tokens. A recursive-descent parser maps tokens into AST nodes. Unary and binary uses of the same operator are disambiguated by grammar position. Surface syntax stays separate from later machine-specific concerns.

Challenges

  • Nested unary expressions such as ~(-2) force careful consume/produce order in the parser.
  • Malformed token streams need useful errors without poisoning later stages.
  • Precedence and associativity must be encoded in the parse structure, not patched during codegen.

Iterations

  • Return integer literals.
  • Unary negation and complement.
  • Nested unary combinations.
  • Scaffolding toward binary operators, statements, and control flow as the language grows.

Final implementation

A deterministic parser that produces an AST suitable for resolution and lowering. Syntax structure is frozen before semantic meaning is decided.

AST shape
AST representation for nested unary expressions

Nested unaries become explicit tree structure before IR lowering.

02Semantic Analysis

Semantic Analysis

Goal

Determine whether a syntactically valid program is also contextually meaningful before generating assembly.

Design

Resolve identifiers to declarations, track lexical scopes, detect invalid or duplicate symbols, assign unique internal names where needed, and validate context-sensitive constructs as those features land. Syntax alone cannot decide whether a name exists or which declaration it refers to.

Challenges

  • Shadowing and nested scopes reuse source identifiers that must map to distinct internals.
  • Control-flow statements are only valid inside particular contexts; catching that late looks like broken assembly.
  • Errors should fail before lowering so the backend is not debugging frontend mistakes.

Iterations

  • Global symbol handling for the current subset.
  • Local scope maps and unique renaming as variables arrive.
  • Loop-label and control-flow resolution on the roadmap once statements expand.

Final implementation

A resolved AST where names and control-flow targets are explicit before TACKY generation. Semantic validity is an invariant the IR pass can trust.

Source contract
Source program entering semantic analysis

Syntax-valid input still needs contextual checks before lowering.

03Intermediate Representation

Intermediate Representation

Goal

Separate the meaning of the C program from both surface syntax and x86-64 operand restrictions.

Design

Lower AST expressions into three-address-style TACKY instructions. Replace nesting with temporaries. Represent operations and control flow in a linear, architecture-independent form so register, stack, and instruction constraints stay in the backend. Example: return ~(-2); becomes tmp.0 = -2; tmp.1 = ~tmp.0; return tmp.1.

Challenges

  • Preserving evaluation order while deleting tree nesting.
  • Generating unique temporaries and labels without leaking AST shape into the backend.
  • Direct AST-to-assembly works for return 2; and collapses once expressions and control flow grow.

Iterations

  • Direct assembly for constant returns.
  • Recognition that nested expressions duplicated backend logic.
  • Introduction of temporaries and explicit TACKY instructions.
  • Expansion path toward structured control flow and locals.

Final implementation

A linear IR that acts as the contract between frontend and backend. The IR is where the compiler becomes intellectually interesting: meaning is explicit, target constraints are still deferred.

TACKY lowering
TACKY IR flattening nested expressions

Nesting becomes temporaries; the backend sees a linear instruction stream.

04x86-64 Backend

x86-64 Backend

Goal

Translate architecture-independent IR into legal x86-64 assembly that follows the target ABI and preserves semantics.

Design

Map temporaries to stack slots. Emit AT&T syntax. Generate function prologue and epilogue. Place return values in %eax. Use scratch registers when an IR instruction cannot map to one legal machine instruction. Assemble and link with the system toolchain. Developing on Apple Silicon while targeting x86-64 requires explicit architecture handling.

Challenges

  • x86-64 generally forbids memory-to-memory arithmetic and moves; illegal forms must be rewritten through a scratch such as %r10d.
  • One IR op often becomes several machine instructions.
  • Stack offsets, widths, and calling convention details must stay consistent or the program returns the wrong code while still assembling.

Iterations

  • Emit assembly for constants.
  • Allocate each temporary to a stack slot.
  • Introduce pseudo-instructions.
  • Add a fixup pass that rewrites illegal memory-to-memory ops through %r10d.
  • Compare generated exit codes against expected behavior.

Final implementation

A backend that lowers TACKY into valid x86-64, applies instruction fixups, and produces executables through the host assembler and linker.

Assembly output
Generated x86-64 assembly with stack slots and fixups

Illegal memory-to-memory forms are rewritten through a scratch register.

05Testing & Validation

Testing & Validation

Goal

Prove each stage preserves meaning, not only that the final binary runs.

Design

Unit coverage for lexer tokens, AST snapshots for parser output, IR snapshots for lowering, assembly inspection for the backend, and end-to-end compile-and-run checks. Differential comparison against clang/gcc for supported programs. Stage tests localize defects that end-to-end tests bury.

Challenges

  • A compiler can emit a plausible AST, wrong IR, illegal operands, or legal assembly with the wrong exit status.
  • End-to-end failures alone do not identify which pass broke the invariant.
  • Official regression currently concentrates on return constants and nested unaries; broader features need matching fixtures as they land.

Iterations

  • Start with return constants.
  • Add unary cases including ~(-2).
  • Freeze expected intermediates when a stage stabilizes.
  • Read generated assembly on failure before guessing at the frontend.

Final implementation

An incremental validation workflow that isolates frontend, IR, and backend defects. Correctness and clean lowering stay ahead of optimization.

Key Design Decisions

Calls I actually made

What else was on the table, what I picked, and why it still made sense once the hardware was real.

01

OCaml for the implementation language

The problem

Which language makes compiler data structures and pattern matching honest?

Alternatives considered

  • C++
  • Rust
  • Python
  • OCaml

Tradeoffs

Python is fast to sketch and weak for algebraic IR/AST work. C++/Rust add systems power and more ceremony. OCaml matches AST/IR variants and recursive passes.

Why I chose this

OCaml. Pattern matching on AST and TACKY variants keeps each pass readable and hard to leave incomplete.

02

Recursive descent versus a parser generator

The problem

How should the grammar become an AST?

Alternatives considered

  • Parser generator
  • Parser combinator library
  • Hand-written recursive descent

Tradeoffs

Generators scale for large grammars but hide control. Hand-written descent makes precedence and error paths explicit while learning.

Why I chose this

Recursive descent. Ownership of token consumption matters more than grammar-file convenience at this scale.

03

Introduce TACKY IR versus direct AST-to-assembly

The problem

Where should architecture constraints enter?

Alternatives considered

  • Direct AST lowering
  • Early SSA
  • TACKY-style three-address IR

Tradeoffs

Direct lowering works for literals and explodes for nesting. Full SSA is valuable later; TACKY is the right intermediate contract now.

Why I chose this

TACKY IR. Flatten expressions once; keep the backend focused on ISA and ABI legality.

04

Stack-backed temporaries versus early register allocation

The problem

How should IR values map to machine storage?

Alternatives considered

  • Immediate register allocation
  • Stack slots for all temporaries
  • Hybrid with a simple allocator

Tradeoffs

Early allocation couples correctness work to a hard optimization problem. Stack slots are slower and make fixups and ABI behavior easier to reason about.

Why I chose this

Stack-backed temporaries first. Register allocation is a later pass once lowering is trusted.

05

Correctness before optimization

The problem

When should speed work start?

Alternatives considered

  • Peephole early
  • Constant folding during AST
  • Correct lowering then optimize

Tradeoffs

Fast wrong code teaches nothing useful. Optimization without stable IR invariants is churn.

Why I chose this

Correctness-first. Expand the language subset with stage tests; optimize after meaning is preserved.

06

Incremental language features

The problem

How wide should the supported C subset be at once?

Alternatives considered

  • Broad subset immediately
  • One feature family per milestone

Tradeoffs

Broad subsets create entangled bugs across passes. Incremental growth forces each new construct to earn frontend, IR, backend, and test support.

Why I chose this

Incremental features. Official tests currently lock constants and nested unaries; binaries, locals, and calls expand with matching fixtures.

Evolution

How it got here

Bench bring-up, CAD fits, soldering, and the demos in between. Not just the final photo.

  1. Stage 1

    Return integer constants

    End-to-end path from source through assembly for return N;. Proved the driver, emit path, and toolchain glue before expression complexity arrived.

    No media for this milestone yet.

  2. Stage 2

    Unary operators

    Negation and complement required nested AST nodes and forced the first real lowering decisions.

    No media for this milestone yet.

  3. Stage 3

    TACKY and stack lowering

    Nested expressions stopped going straight to assembly. Temporaries and linear IR became the contract.

    No media for this milestone yet.

  4. Stage 4

    Instruction fixups

    Illegal memory-to-memory forms surfaced during real x86 emission. Scratch-register rewrite became a dedicated pass.

    No media for this milestone yet.

  5. Next

    Locals, control flow, calls

    Each new language feature must extend resolve, TACKY, backend, and stage tests together. Optimization and register allocation stay future work.

    No media for this milestone yet.

Results & Validation

What held up

What worked in the end, what I can show for it, and where it's still limited.

Source-to-executable path

Official fixtures include return_42.c and unary.c with return ~(-2);

Supported programs compile through mycc into linked x86-64 binaries via the host toolchain.

Stage-local debugging

Snapshot-style intermediates and assembly reading during bring-up

Failures are inspected as AST, TACKY, or assembly mismatches instead of treating compilation as one opaque step.

Honest scope

README current-support notes and official test set

The public claim stays at constants and nested unaries until broader fixtures land. Scaffolding is not marketed as shipped language coverage.

Photos and clips

The runs and stills that match the results above.

E2E view
Full compiler pipeline diagram

Every arrow adds an invariant and removes a class of complexity.

Limitations

  • Supported C subset is intentionally narrow today; do not read scaffolding as full C.
  • No register allocation, SSA, or optimization pipeline yet.
  • Apple Silicon hosts still require explicit x86-64 target handling for generated binaries.

Reflection

Looking back

What surprised me, what I'd redo, and questions I'm still chewing on.

What surprised me

  • Most complexity is preserving meaning across representations, not recognizing syntax.
  • Direct AST-to-assembly felt productive until one nested unary forced a redesign.

What I would redesign

  • Stronger source-location tracking on every diagnostic.
  • Clearer typed errors between resolve and TACKY.
  • Sharper separation between IR construction and backend lowering helpers.

Future improvements

  • Binary operators, locals, conditionals, loops, and function calls with ABI-correct lowering.
  • Register allocation after stack lowering is trusted.
  • Constant folding and dead-code elimination only after correctness fixtures cover the new features.

Questions that emerged

  • How do production compilers optimize while proving semantic preservation?
  • Where does SSA pay for itself relative to a simple three-address IR?
  • How should ABIs shape IR design before the backend exists?