TITLE: Teaching Compilers by Example AUTHOR: Eugene Wallingford DATE: January 07, 2008 7:07 PM DESC: ----- BODY: The most recent issue of inroads contained more than just some articles on how to introduce computer science to majors and non-majors alike. It also contained an experience report at the intersection of topics I've discussed recently: a compiler course using a sequence of examples. José de Oliveira Guimarães describes a course he has taught annually since 2002. In this course, he presents a sequence of ten compilers, each of which introduces a new idea or ideas beyond the previous. The "base case" isn't a full compiler but rather a parser for a Scheme-like expression language. Students see these examples -- full code for compilers that can be executed -- before they learn any theory behind the techniques they embody. All ten are implemented from scratch, using recursive descent for parsing. If I understand the paper correctly, de Oliveira Guimarães teaches these examples, followed by five examples implemented using a parser generator, in the first eight weeks of a sixteen-week course. The second half of the course teaches the theory that underlies compiler construction. This seems to be a critical feature of a by-example course: The students study examples first and only then learn theory -- but now in the context of the code that they have already seen. One thing that makes this course different than mine is that students do not implement a compiler during this semester. Instead, they take a second course in which they do a traditional compiler project. I don't have this luxury -- I'm lucky to be able to teach one compiler course at all, let alone a two-semester sequence. I also feel strongly about the power of students working on a major project while learning about compilers that I'm not sure how I feel about the examples-and-theory first course. But what a neat idea! I look forward to studying de Oliveira Guimarães's code in order to understand his course better. (He has all of code on-line, along with the beginnings of a descriptive "textbook" for the course, translated into English.) In some ways, I suppose that what I do here bears some resemblance to this approach. In the first semester, students study programming languages using an interpreter-based approach, which gives them a low level of understanding of techniques for processing programs. They see several small program processors and implement a few others, in order to understand these techniques. They then take the compiler course, where we "go deep" both in implementation and theory. But there is no question that their compiler project requires some of the theory we study that semester. At the beginning of the second semester, before students begin work on their project and before I introduce any theory of lexical or syntax analysis, I spend two sessions presenting a whole compiler. This compiler is my implementation of a variant of a compiler described by Fischer, LeBlanc, and Cytron. I present this example first in order for students to see all of the phases of a compiler working in concert to translate a program. Because it comes so early in the semester, it is necessarily a simple example, but it does give me and the students a reference point for most of what we see later in the term. This is only one example, but I work incremental refinements to it as we go along. As we learn new techniques for each phase of the compiler, I try to plug a new component into the reference compiler that demonstrates the theory we have just learned. For example, my initial example uses an ad hoc scanner and a recursive descent parser; later, I plug in a regular expression-based scanner and a table-driven parser. Again, language compiled by the reference program is pretty simple, so these new components are still quite simple, but I hope they give the students some grounding before they implement more complex versions in their project. All that said, de Oliveira Guimarães's approach takes the idea of examples to another level. I look forward to digging into it further and seeing what I can learn from it. -----