How the First C Compiler Was Built Using Self‑Bootstrapping Subsets

Paying tribute to Dennis Ritchie, the piece notes that most modern compilers and interpreters are written in C, and that the portability of high‑level languages ultimately depends on the portability of ANSI/ISO C.

Because C is close to assembly, it is natural to implement system software like compilers in C. The author asks how the very first C compiler could have been written, given this reliance on C itself.

Historical Background

In 1970 Thompson and Ritchie created the B language from BCPL, and in 1973 they extended B to produce C. Before C, Thompson used B to write an operating system, showing that a pre‑C implementation was feasible.

Bootstrapping via Subsets

The early C compiler likely used a clever bootstrapping strategy: first write a compiler for a tiny C subset (C0) in assembly, then use that compiler to implement a slightly larger subset (C1), and repeat the process (C2, C3, …, CN) until the full language was covered. The process stops when the current subset is powerful enough to compile the next level.

Defining the Subsets

Starting from the full C99 keyword list, the author removes keywords that are primarily for optimization or advanced features, producing a minimal subset called C3. Further pruning of type specifiers yields C2, and eliminating complex type constructors (enum, struct, union) results in C1. Finally, by discarding all structured control‑flow constructs and even function definitions, only five keywords remain for C0: break, void, goto, int, and double.

Why This Works

Each reduced language still retains enough expressive power to implement the next larger subset because control flow can be expressed with simple goto statements, and data manipulation can be performed with the remaining types. By iteratively expanding the language, the original C compiler can be reconstructed without ever needing a full C implementation beforehand.

Conclusion

The minimal C0 language can be quickly written in assembly, and through successive self‑compilation steps the complete C compiler emerges, illustrating the ingenuity of early computer scientists and the elegance of self‑bootstrapping compilation.