Previous    Next


A compiler was originally a program that "compiled" subroutines [a link-loader]. When in 1954 the combination "algebraic compiler" came into use, or rather into misuse, the meaning of the term had already shifted into the present one.

Bauer and Eickel [1975]


This tutorial describes techniques, data structures, and algorithms for translating coding languages into executable code. A modern compiler is often organized into many phases, each operating on a different abstract "language." The chapters of this tutorial follow the organization of a compiler, each covering a successive phase. To illustrate the issues in compiling real coding languages, we show how to compile MiniJava, a simple but nontrivial subset of Java. Programming exercises in each chapter call for the implementation of the corresponding phase; a student who implements all the phases described in Part I of the tutorial will have a working compiler. MiniJava is easily extended to support class extension or higher-order functions, and exercises in Part II show how to do this. Other chapters in Part II cover advanced techniques in program optimization. Appendix A describes the MiniJava language. The interfaces between modules of the compiler are almost as important as the algorithms inside the modules. To describe the interfaces concretely, it is useful to write them down in a real coding language. This tutorial uses Java - a simple object-oriented language. Java is safe, in that programs cannot circumvent the type system to violate abstractions; and it has garbage collection, which greatly simplifies the management of dynamic storage allocation. Both of these properties are useful in writing compilers (and almost any kind of software).

This is not a textbook on Java programming. Students using this tutorial who do not know Java already should pick it up as they go along, using a Java coding tutorial as a reference. Java is a small enough language, with simple enough concepts, that this should not be difficult for students with good coding skills in other languages.

JaVaScreenshot Previous    Next