Compilers: How Computers Execute Their Programs

Intermediate—Fall

Compilers are often known as translators—and for good reason: Their job is to take programs written in one language and translate them to another language (usually assembly or machine language) that a computer can execute. It is perhaps the ideal meeting between the theoretical and practical sides of computer science. Modern compiler implementation offers a synthesis of: (1) language theory: how languages (both natural languages and programming languages) can be represented on, and recognized by, a computer; (2) software design and development: how practical software can be developed in a modular way—e.g., how components of one compiler can be connected to components of another compiler to form a new compiler; and (3) computer architecture: understanding how modern computers work. During the semester, we will write a program implementing a nontrivial compiler for a novel programming language (partly of our own design). Topics we will cover along the way include the difference between interpreters and compilers, regular expressions and finite automata, context-free grammars and the Chomsky hierarchy, type checking and type inference, contrasts between syntax and semantics, and graph coloring as applied to register allocation. Conference work will allow students to pursue different aspects of compilers such as compilation of object-oriented languages, automatic garbage collection, compiler optimizations, and applications of compiler technology to natural-language translation. Permission of the instructor is required. Students should have already taken at least one semester of computer programming (C, C++, or Java) and, preferably, a course in computer architecture.