Compilers: Backend to Frontend and Back to Front Again

Compilers are perceived to be magical artifacts, carefully crafted by the wizards, and unfathomable by the mere mortals. This paper attempts to dispel this myth. We build a simple compiler for a simple language in a step-by-step fashion. The input language accepted by the compiler starts minimal, and grows as our knowledge of how to build compilers grows. The final language is almost Scheme. Although the compiler is written in the Scheme programming language, only minimal knowledge of Scheme is required. Essentially, the reader is assumed to be comfortable reading and writing recursive Scheme functions to the level presented in The Little Schemer. Additionally, we recommend the freely available tutorial Teach Yourself Scheme in Fixnum Days for people familiar with other programming languages but not Scheme. The Scheme Programming Language is an invaluable resource for understanding Scheme’s semantics. You will find it most useful when you give up in thinking how list? detects circular data structures. Our compiler targets the Intel-386 architecture, the dominant architecture for personal computing. The output of our compiler is assembly code that can be assembled by gas, the GNU assembler, which is freely available for most operating systems. No knowledge of assembly language or the Intel-386 architecture is assumed beyond the basics: binary numbers, memory layout, and basic pointers. If you are familiar with arrays in C, and know how the bit-level operations (and, or, xor, and not) work, then you’re good to go. Contents Preface v 1 Basic Concepts 1 1.1 Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Immediate Constants . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Unary Primitives . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 Conditional Expressions . . . . . . . . . . . . . . . . . . . . . 15 1.5 Binary Primitives . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Local Variables . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.7 Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.8 Iteration via Proper Tail Calls . . . . . . . . . . . . . . . . . . 31 1.9 Heap Allocation . . . . . . . . . . . . . . . . . . . . . . . . . 35 A Tables 41 A.1 ASCII Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 A.2 Object Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43