Building a C-Subset Compiler for the FRISC Architecture: From Formal Languages to Executable Code
Karlo Knežević · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
Building a C-Subset Compiler for the FRISC Architecture: From Formal Languages to Executable Code is a narrative monograph that follows a complete, working compiler from a deterministic subset of C all the way down to code that runs on the FRISC (FER Instruction Set Computer) educational architecture. Rather than presenting compilation as a catalogue of disconnected algorithms, the book builds a single real compiler end to end and explains every phase as it is implemented: lexical analysis (NFA construction, subset construction to a DFA, and maximal-munch tokenization), LR(1) parsing with an automatically constructed parse table, semantic analysis and type checking, lowering to a typed three-address intermediate representation, sixteen semantics-preserving optimization passes, and final code generation for the FRISC instruction set, followed by simulation. Part IV then revisits the same intermediate representation through two additional back ends — a tree-walking IR interpreter and a stack-based bytecode virtual machine — and uses them, together with the native FRISC back end, to study program behaviour and optimization impact through reproducible measurements on real example programs. The text is written in a deliberately accessible, first-person narrative voice, while preserving formal rigour: every optimization pass is accompanied by a semantic-preservation proof, and the formal language theory underlying each phase is presented precisely but without ceremony. Worked examples are drawn from a real compiler implementation; no traces or measurements are fabricated. The book is suitable for advanced undergraduate and graduate students, self-taught engineers, and anyone who wants to understand not just how a compiler is described in theory, but how one is actually built, optimized, and executed. A companion repository accompanies the book with a chapter-by-chapter "build-along" implementation of tinyC, an integer-only C subset, including starter code, reference solutions, and tests.