Compilers: How Computers Execute Their Programs

Catalog description

Prerequisite: Introduction to Computer Programming (COMP 2010) or equivalent and permission of the instructor 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—for example, 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. In this course, we will write a program implementing a nontrivial compiler for a novel programming language (partly of our own design). Topics covered will 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, just-in-time compilation, WebAssembly, and applications of compiler technology to natural-language translation. Programming experience is required. Familiarity with computer organization is recommended. The Computational Beauty of Nature