A Problem Course in Compilation: From Python to x86 Assembly

ABSTRACT. The primary goal of this course is to help students acquire an understanding of what happens “behind the scenes” when programs written in high-level languages are executed on modern hardware. This understanding is useful for estimating performance tradeoffs and debugging programs. A secondary goal of the course is to teach students the principles, techniques, and tools that are used in compiler construction. While an engi-neer seldom needs to implement a compiler for a general purpose language, it is quite common to implement small domain-specific languages as part of a larger software system. A tertiary goal of this course is to give the students a chance to practice building a large piece of software using good software engineering practices, in particular, using incremental and test-first development. The general outline of the course is to implement a sequence of compilers for increasingly larger subsets of the Python 2.5 pro-gramming language. The subsets are chosen primarily to bring out interesting principles while keeping busy work to a minimum. Nevertheless, the assignments are challenging and require a sig-nificant amount of code. The target language for this sequence of compilers is the x86 assembly language, the native language of most personal computers. These notes are organized as a prob-lem course, which means that they present the important ideas and pose exercises that incrementally build a compiler, but many de-tails are left to the student to discover