TITLE: Teaching Compilers by Example
AUTHOR: Eugene Wallingford
DATE: January 07, 2008  7:07 PM
DESC: 
-----
BODY:
The most recent issue of <EM>inroads</EM> contained more than
just some articles on
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2008-01.html#e2008-01-03T15_25_09.htm">
   how to introduce computer science</A>
to majors and non-majors alike.  It also contained an experience
report at the intersection of topics I've discussed recently: a
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-07.html#e2007-07-09T19_28_38.htm">
   compiler course</A>
using a sequence of
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-07.html#e2007-07-17T20_17_04.htm">
   examples</A>.

Jos&eacute; de Oliveira Guimar&atilde;es
<!A HREF="XXXXX">
   describes a course</A>
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&atilde;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&atilde;es's code
in order to understand his course better.  (He has all of code
<A HREF="http://www.dc.ufscar.br/~jose/courses/cc-en.htm">
   on-line</A>,
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
<A HREF="http://www.amazon.com/gp/product/0201385937/">
   Fischer, LeBlanc, and Cytron</A>.
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
<I>ad hoc</I> 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&atilde;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.
-----