mycc

A small, from-scratch C compiler that turns a well-defined subset of C into native x86-64 executables, with two interchangeable backends: a hand-written x86-64 assembly generator and an LLVM IR generator.

mycc is a complete, honest compiler. It has a hand-written lexer, a recursive-descent parser, a real semantic-analysis pass (scopes, symbol tables, a type system, constant folding), and code generation that respects the System V and Microsoft x64 calling conventions. It does not lean on flex, bison, or any parser generator. Every C construct it accepts is compiled down to machine code and validated against gcc by a differential test suite of 117 programs across 12 build stages, passing identically on both backends.

make                          # build ./mycc
./mycc program.c -o program   # compile to a native executable (asm backend)
./program                     # run it

---

Table of contents

• Why this project
• Feature tour
• Quick start
• The compilation pipeline
• Two backends
• The language mycc accepts
• Source layout
• Command-line interface
• Testing
• Build stages
• Deep-dive documentation
• Design decisions and limitations

---

Why this project

Most "toy compiler" tutorials stop at an interpreter or an AST printer. mycc goes all the way to a native binary you can run, and it does so twice, through two independent backends, so the same program produces the same observable behavior whether it is lowered by hand-written assembly or by LLVM. That dual path is more than a party trick: because both backends consume the same validated AST, any disagreement between them would immediately expose a bug in the shared frontend. Running both against gcc as an oracle gives three independent implementations that must all agree.

The codebase is written to be read. Every source file opens with a block comment explaining its role, and the accompanying docs go component by component in exhaustive detail.

---

Feature tour

Area	What is supported
Types	int (4 bytes), char (1 byte), pointers (T *), arrays (T[N]), struct
Expressions	full C operator set with correct precedence and associativity
Operators	+ - * / %, << >>, & | ^ ~, ! && ||, == != < > <= >=, ? :, assignment
Pointers	address-of &, dereference *, scaled pointer arithmetic, ptr - ptr, a[i]
Structs	. and -> access, System V field layout with padding, pass/return by pointer
Control flow	if/else, while, do/while, for, break, continue, ternary
Functions	definitions, prototypes, parameters, recursion, mutual recursion, variadic calls
Globals	file-scope variables with folded constant initializers (.data/.bss)
Literals	decimal/hex integers, char literals, string literals with escapes
Backends	--backend=asm (x86-64) and --backend=llvm (LLVM IR via clang)
Calling conventions	System V AMD64 (internal), Microsoft x64 (external libc, e.g. printf)

---

Quick start

Prerequisites

• gcc and GNU make (the assembly backend assembles and links with gcc).
• clang (only needed for the LLVM backend).

Build and run

make                              # produces ./mycc
./mycc examples.c -o examples     # asm backend (default)
./examples; echo $?               # run it; print its exit code

A tiny end-to-end program:

int printf(char *fmt, ...);

int square(int x) { return x * x; }

int main(void) {
    printf("%d\n", square(7));    /* prints 49 */
    return 0;
}

./mycc demo.c -o demo && ./demo
# 49

To see the intermediate the compiler produced, keep it:

./mycc demo.c -o demo --keep-asm        # keeps demo.s
./mycc demo.c -o demo --backend=llvm --keep-asm   # keeps demo.ll (and demo.o)

---

The compilation pipeline

mycc is a classic multi-pass compiler. Each pass has one job and communicates with the next through plain in-memory data structures.

flowchart LR
    SRC["source.c"] --> LEX["Lexer<br/>src/lexer.c"]
    LEX -->|tokens| PAR["Parser<br/>src/parser.c"]
    PAR -->|AST| SEM["Semantic analysis<br/>src/semantics.c"]
    SEM -->|annotated AST| SEL{"backend?"}
    SEL -->|asm| CGA["codegen.c<br/>x86-64 .s"]
    SEL -->|llvm| CGL["codegen_llvm.c<br/>LLVM .ll"]
    CGA --> GCC["gcc: assemble + link"]
    CGL --> CLANG["clang: .ll -> .o"]
    CLANG --> LINK["gcc: link"]
    GCC --> EXE(["native executable"])
    LINK --> EXE

Loading

Stage	File	Input	Output
Lex	src/lexer.c	source text	flat token array
Parse	src/parser.c	tokens	AST (src/ast.h)
Analyze	src/semantics.c	AST	annotated AST (offsets, types, frame sizes)
Generate	src/codegen.c or src/codegen_llvm.c	annotated AST	.s or .ll
Assemble/link	gcc (and clang for llvm)	.s/.ll	native executable

Everything above the backend split is shared and backend-agnostic. For the full story, read docs/architecture.md.

---

Two backends

mycc ships two code generators that consume the identical annotated AST.

mycc source.c -o prog                  # default: asm backend
mycc source.c -o prog --backend=asm    # x86-64 assembly (codegen.c), linked with gcc
mycc source.c -o prog --backend=llvm   # LLVM IR (codegen_llvm.c), lowered by clang

• asm (default) emits x86-64 AT&T assembly and invokes gcc to assemble and link. It is the "teaching" backend: it shows exactly how C constructs map to instructions, stack frames, and calling conventions. See docs/codegen-asm.md.
• llvm emits textual LLVM IR and lets clang's backend do instruction selection, register allocation, and optimization when lowering the .ll to a native object, which is then linked. See docs/codegen-llvm.md.

The LLVM backend models every scalar SSA value as an i64 (mirroring the untyped 64-bit registers the assembly backend uses); memory objects keep their natural width (i32/i8/i64, or an opaque [N x i8] blob for aggregates addressed by manual byte offsets), and 32-bit integer semantics are preserved by normalizing each arithmetic result through trunc/sext.

Toolchain and runtime parity

The --backend=llvm link step is controlled by three environment variables:

Variable	Default	Purpose
MYCC_CLANG	clang	clang executable
MYCC_LLVM_TARGET	x86_64-w64-windows-gnu	clang --target triple
MYCC_LLVM_LINKER	gcc	linker driver for the object

On a Windows/mingw host the reference toolchain is mingw gcc, whose C runtime differs from clang's default MSVC runtime in two user-visible ways: text-mode stdout (\n becomes \r\n) and how a negative main() return value maps to the process exit code. Lowering with clang's gnu target and linking the object with gcc makes the LLVM backend use the same runtime as the reference, so the two backends agree byte-for-byte and on exit codes. On Linux, set MYCC_LLVM_TARGET= (empty) and MYCC_LLVM_LINKER=clang to let clang drive the whole compile and link.

Both backends pass all 117 tests across stages 1-12 identically.

---

The language mycc accepts

A concise EBNF of the accepted grammar (full version in docs/parser.md):

Program     ::= ( StructDef | Function | Global )*
Function    ::= BaseType "*"* IDENT "(" ParamList ")" ( ";" | Block )
Global      ::= BaseType "*"* IDENT ArraySuffix? ( "=" Expr )? ";"
StructDef   ::= "struct" IDENT "{" ( BaseType Declarator ";" )+ "}" ";"
Statement   ::= "return" Expr ";" | "if" ... | "while" ... | "do" ...
              | "for" ... | "break" ";" | "continue" ";" | Block | Expr ";"
Expr        ::= Assignment                (* full C precedence via climbing *)
BaseType    ::= "int" | "char" | "struct" IDENT

What is intentionally not supported: the preprocessor (#include, #define), float/double codegen, unsigned/long/short, enum, union, typedef, switch, goto, and passing/returning structs by value. See Design decisions and limitations.

---

Source layout

CCompiler/
|-- Makefile              # builds ./mycc from every src/*.c
|-- README.md             # this file
|-- docs/                 # in-depth documentation (start at docs/README.md)
|-- src/
|   |-- lexer.h/.c        # tokenizer: text -> token stream
|   |-- parser.h/.c       # recursive descent + precedence climbing -> AST
|   |-- ast.h/.c          # AST node types, constructors, recursive free
|   |-- type.h/.c         # type model (int/char/pointer/array/struct), arena
|   |-- semantics.h/.c    # scopes, symbol tables, offsets, folding, checks
|   |-- codegen.h/.c      # x86-64 AT&T assembly backend
|   |-- codegen_llvm.h/.c # LLVM IR backend
|   |-- main.c            # CLI + driver: orchestrates passes and toolchain
|-- tests/
    |-- run_tests.sh      # differential test harness (compares against gcc)
    |-- stage0/           # standalone lexer test
    |-- stage1/ ... stage12/  # per-stage .c programs

File	Responsibility	Deep dive
src/lexer.c	tokenization, maximal munch, positions	docs/lexer.md
src/parser.c	grammar, precedence climbing	docs/parser.md
src/ast.c	tagged-union tree, ownership	docs/ast.md
src/type.c	sizes, alignment, decay, struct layout	docs/types.md
src/semantics.c	scopes, offsets, folding, checks	docs/semantics.md
src/codegen.c	x86-64 lowering, ABIs	docs/codegen-asm.md
src/codegen_llvm.c	LLVM IR emission	docs/codegen-llvm.md
src/main.c	CLI, backend selection, linking	docs/driver.md

---

Command-line interface

mycc <source.c> -o <output> [--backend=asm|llvm] [--keep-asm]

Option	Meaning
-o <output>	Output executable path (required).
--backend=asm	x86-64 assembly backend (default).
--backend=llvm	LLVM IR backend.
--keep-asm	Keep the intermediate .s/.ll (and .o) instead of deleting it.

Full details, including the read/lex/parse/analyze/generate/link flow and exit codes, are in docs/driver.md.

---

Testing

Each stage has a directory of .c programs. The harness tests/run_tests.sh validates mycc against gcc as a reference: for every file it compiles with both, runs both binaries, and compares stdout and exit code. It prints PASS/FAIL per file and an X/Y passed summary, exiting non-zero on any failure so it drops straight into CI.

make
tests/run_tests.sh tests/stage1

Extra flags are forwarded to mycc via MYCC_ARGS, which is how the LLVM backend is exercised through the same harness:

MYCC_ARGS=--backend=llvm tests/run_tests.sh tests/stage1

The full methodology is documented in docs/testing.md.

---

Build stages

mycc was built in twelve incremental stages, each adding one coherent language feature plus its tests, and never regressing.

flowchart LR
    S1["1 return"] --> S2["2 unary"] --> S3["3 binary"] --> S4["4 locals"]
    S4 --> S5["5 if/ternary"] --> S6["6 blocks"] --> S7["7 loops"] --> S8["8 functions"]
    S8 --> S9["9 globals"] --> S10["10 pointers"] --> S11["11 char/strings"] --> S12["12 structs"]

Loading

Stage	Adds	Tests
1	integer return	6
2	unary operators	8
3	binary operators, precedence, short-circuit	14
4	local variables, assignment	10
5	if/else, ternary	11
6	blocks, scoping, shadowing	8
7	loops, break, continue	13
8	functions, calls, recursion, printf	12
9	global variables	7
10	pointers, arrays, pointer arithmetic	12
11	char, char/string literals	6
12	structs, . and ->, field layout	10

Total: 117 tests, all passing on both backends. Details in docs/stages.md.

---

Deep-dive documentation

The docs/ folder is the full technical reference. Start at docs/README.md, which links every page:

• Architecture - the whole pipeline and data flow.
• Lexer, Parser, AST.
• Type System, Semantic Analysis.
• Assembly Backend, LLVM Backend.
• Driver and CLI, Testing, Build Stages.

---

Design decisions and limitations

• Correctness over optimization. The assembly backend is a straightforward stack-machine-style generator (values flow through %eax/%rax). It is easy to read and verify; the LLVM backend is there when optimized code matters.
• One stack slot per declaration. Semantics never reuses stack slots, so shadowing and block re-entry are trivially correct at the cost of a slightly larger frame. See docs/semantics.md.
• Two ABIs on purpose. Internal calls use System V AMD64; external libc calls (like printf) use Microsoft x64 on the Windows host. See docs/codegen-asm.md.
• Structs by pointer only. By-value struct arguments/returns are unsupported because the ABI's register/stack classification rules for aggregates are out of scope; pointers to structs cover the interesting cases. See docs/types.md.
• No preprocessor and a limited type set. #include/#define, floating point codegen, and unsigned/long/enum/union/typedef/switch/goto are not implemented. Prototypes such as int printf(char *, ...); are written out explicitly in test programs.