Introduction to Compiler Construction, Summer 2012

Prof. Kirsch, Department of Computer Sciences, University of Salzburg

Time, Location: Tue 10-12 s.t. and Th 3-4 s.t. in T03, Techno-Z. First lecture is on Tue, March 6, 2012. Check schedule (iCal) for updates.

Brief Overview:

Learn hands-on how to construct a self-compiling compiler in a non-trivial subset of C along with a DLX-based emulator as target and a linker for separate compilation, using nothing but a C compiler for bootstrapping. The course provides an undergraduate-level introduction to compiler construction, covering fundamental topics of compiler construction: scanning, parsing, type checking, error handling, register allocation, code generation, bootstrapping, separate compilation, and basic code optimization; considering fundamental programming language constructs and concepts: assignment, arithmetic and boolean expressions, arrays, records, pointers, conditionals, loops, modules, and procedures with parameters, return values, and local variables. At the end of the course you will be able to appreciate principled engineering of compilers but also know how to actually construct one from scratch and, as a consequence, through insights in programming language semantics that only a compiler can offer, become a fundamentally better programmer and computer scientist.

Teams of 2-3 students will be asked to design their own source language (with formal grammar), and implement their own compiler, linker, and target machine in programming languages of their choice. Each compiler must be able to compile itself in a live demo at the end of the semester. Therefore, source languages are constrained to subsets of programming languages for which executable compilers are available (unless students choose to apply manual bootstrapping techniques). Moreover, source languages must be typed (basic types, arrays, and records) and feature at least a concept for parameterized local hiding such as procedures with arguments and a concept for global hiding such as modules supporting separate compilation. There will also be a final exam at the end of the semester.

The course closely follows the textbook Compiler Construction by Niklaus Wirth but presents code examples written in a subset of C rather than Oberon.

Lecture videos as well as lecture notes and code examples are available in the iTunes Store and on iTunes U as well as on Vimeo in HD.

Goal of the course:

Learn, through compiler construction, how software-related concepts of programming languages such as data types and procedures work and translate into hardware-related concepts such as machine registers and code.

Assignments:

  • There will be biweekly homework assignments.
  • Teams of 2-3 students will design their own source language (with formal grammar), and implement their own compiler, linker, and target machine in programming languages of their choice. Each compiler will be demonstrated to compile itself at the end of the semester. Each team creates a wiki page that describes the project. See the requirements in the above overview.

Final exam:

  • There will be a final exam at the end of the semester.

Required Textbook:

  • Niklaus Wirth: Compiler Construction. Addison-Wesley, 1996.
  • Andrew Appel, Jens Palsberg: Modern Compiler Implementation in Java. Cambridge University Press, 2nd edition, 2003.
Recommended Textbooks:
  • Aho, Lam, Sethi, Ullman: Compilers: Principles, Techniques and Tools. Prentice Hall, 2nd edition, 2006.
Web sources:

Grading: 50% project, 50% exam.

Prerequisites: programming experience, basic knowledge of programming language concepts.

Technical contact: Michael . Lippautz @ cs . uni-salzburg . at
Administrative contact: Adriana . Pratter @ cs . uni-salzburg . at