Overview

CSCI 468, Compilers, is a senior capstone course offered by the Computer Science Department at Montana State University. As part of this course, students must write a compiler in teams of three; when classSize mod 3 ≠ 0, some teams of two will also be formed.

The Compiler Project

The compiler project has some unique features compared to other programming projects that students might undertake.

A Common Project

All students undertake the same project: writing a compiler that translates a subset of Pascal (known as microPascal) into a predefined virtual machine language (known as the microMachine language). Translated code is executed by an interpreter that is a software implementation of the microMachine.

Concurrent Learning and Programming

For this course, students are learning about compiling at the same time as they are writing a compiler. Fortunately, standard compiler organization lends itself to this approach in that it has three distinct components: a scanner, a parser, and a semantic analyzer. Each of these topics is relatively self contained. That is, students can learn about scanning and write a scanner without knowing anything about parsing. Furthermore, the parser cannot be written without a functioning scanner. Similarly, a parser can be written without knowing anything about semantic analysis, and in semantic analysis cannot be completed in the absence of a parser. The course itself can thus be divided into four distinct sections that cover: scanning, parsing, semantic analysis, and advanced compiler topics, respectively. Students learn enough about scanning to begin writing a scanner, which they complete as they learn about parsing. They then write a parser as they begin learning about semantic analysis. Finally, they write the semantic analyzer as they learn about advanced compiler topics that are beyond the scope of their programming projects.

Standard Programming Practice

Compiler writing is well-founded on theory and also well understood in practice. One consequence of this is that there are only a few standard approaches for doing writing a compiler. Probably most often in practice, compilers are written with the help of scanner and parser generator tools, such as flex and bison. In this class, however, students are required to write their compilers by hand. It is believed that this not only inspires the learning of compilation at a deeper level, but that it also engenders

• a better and deeper understanding of the process of compiling
• clearer insight into the ramifications of compilation on programming in general.
• an appreciation for the differences between language processors that translate a high level language into native code and those that interpret some intermediate code or virtual machine language (concepts that are widely misunderstood in the wild).

Each of the three components of the compiler project—scanning, parsing, and semantic analysis—have standard implementation strategies. These standard implementation strategies are to be followed by all students unless they receive permission for a deviation from the instructor.