CSE logo University of Washington Computer Science & Engineering
 CSE P 501 Overview - Autumn 2009
  CSE Home   About Us    Search    Contact Info 


Instructor: Hal Perkins, perkins[at]cs, CSE 548; 206-543-4784. Office Hours: after class plus whenever the door is open (including before class if I'm not cramming for lecture) or by appointment.
Teaching Assistant: Jonathan Beall, jibb[at]cs. Office hours: Tue. 5:30 - 6:20, CSE 218.

Class Meetings

Tuesdays, 6:30-9:20 pm, CSE 305 and Microsoft building 99.
There will be one additional class meeting the week after Thanksgiving for an exam, on Thursday, December 3 from 6:30-8:00 pm. The exam will be offered simultaniously in the UW and Microsoft classrooms.


The course web site is www.cs.washington.edu/csep501/.   Registered students are automatically subscribed to a class mailing list and we also have an online discussion board. Links to these are on the course web main page.


The goal of the course is to understand how a modern compiler is structured and the major algorithms that are used to translate code from high-level to machine language. The best way to do this is to actually build a working compiler, so there will be a significant project to implement one that translates programs written in a core subset of Java into executable x86 assembly language. The compilers themselves will use scanner and parser generator tools and the default implementation language is Java. Variations on the project, particularly the implementation language, are possible; talk to the instructor if you want to try something different.

Most of the students in CSE P 501 have not taken a previous compiler course, so we will cover the basics, but we'll move right along so we can get to more advanced material. Talk to the instructor if you are not sure whether this is the course for you.


  1. Overview of compilers
  2. Scanners and lexical analysis
  3. Parsing (bottom-up LR; top-down LL and recursive descent)
  4. Static semantics, type checking, and symbol tables
  5. Runtime organization and code shape
  6. Code generation and instruction selection
  7. Register allocation and instruction scheduling
  8. Program analysis, optimization, and program transformations.
  9. Recent topics as time permits. Details tbd, but likely including compilers for dynamic languages, JITs, and others depending on class interests.


The nominal prerequisites for a compiler course are background equivalent to undergraduate courses in data structures and algorithms, formal languages and automata, and machine organization. Specifically:

We will review what we need of these topics, so it shouldn't be a problem if things are a bit rusty. If you're missing one of the background courses, it is normally possible to work around it, but you will be on your own to fill the gaps. Talk with the instructor if you're not sure whether you have the appropriate background.


There are three good, fairly recent compiler textbooks available, none of which clearly dominates the others. Lectures and course materials will draw on all three (among other sources). All three of these books have been used as the official text for the course at one time or another, and any of the three would be suitable as a choice. We picked the Cooper/Torczon book as the "recommended" one because it seems to have the best balance between traditional and more recent material (particularly SSA), but you are free to use whichever of these books you like.

Assignments and Grading

The course will be oriented around the project, covering topics in the order needed for it. The project will be due in phases, both to keep you on schedule, and so we can give you feedback at crucial points to be sure that all is well.

We suggest you work on the project in groups of 2 or 3. It is possible to work alone, but past experience is that this can be too much for one individual in a 10-week quarter (although some of the individual projects have been among the most impressive!). It is often helpful to have a partner to talk to about specific design details as the project evolves.

In addition to the project, there will be some written homework assignments to cover topics that don't fit into the project (particularly grammars and parsing at the beginning of the course, and maybe some analysis and optimization topics later). There will also be an exam after the Thanksgiving holiday. Assignments should be done individually.

The course grade will tentatively be computed as follows:

The bulk of the project grade will be based on the final results by the end of the quarter, but we will take into account the quality and timelines of the intermediate steps. The project will be graded primarily on how well it works, but reasonable code quality is expected - it'll be hard to do well without some attention to that. A short written report describing the project will be due at the end of the quarter, and there will be group meetings with the course staff to talk about the project and report during finals week.

We reserve the right to adjust these percentages if it seems appropriate.

Computing Resources

You are free to use any computer, programming environment, and Java implementation that you wish. We do ask that your code be standard Java, i.e., it will compile and run correctly with a recent version (5 or 6) of Sun's standard Java tools. If you wish to use another implementation language (C# has been used successfully in the past, ML, OCAML, and F# also good choices), please talk with the instructor first. Recent versions of many of these tools are installed in the instructional labs in the Allen Center, which you are free to use.

To execute the generated assembly language code, you will need access to a programming environment that can compile and run a C bootstrap program and x86 assembly language code. We will provide instructions for doing this with Visual Studio and the MASM assembler that is included with it, and for gcc and the GNU assembler. All of these are installed in the instructional labs and are available free for use on your personal machines (Visual Studio through the Microsoft software donation program for CSE students if you don't already have it). Again, other target machines are possible; discuss this if you want to try something different.

Space will be available on the department servers for project groups that wish to set up SVN or other repositories to manage their code or otherwise use centralized file space.

Academic Integrity

This should go without saying, but it needs to be written down to avoid any misunderstandings.

Your project assignments should be done only by members of your group. Other assignments should be done by you alone, unless otherwise specified. Any cases of cheating that we discover will be sent to the College disciplinary committee.

However, we also want to be clear on what is legitimate collaboration -- please help each other out in this class in appropriate ways! It is OK to help other students debug their programs, and to discuss general approaches to solving problems. However, it is not OK to just copy someone else's code or homework solution and turn it in as your own work - or to provide materials to others so they can do this.

Exams must of course be done on your own. The exam will be open book and open notes. Laptops, PDAs, pagers, and other devices will not be allowed.

Late Assignments and Incompletes

Assignments will be submitted online and are due at the time and date given in the assignment. We will try to be flexible about outside commitments (jobs, family events) that interfere with this. Please talk to the instructor if something happens that prevents you from submitting work on time.

Incompletes cannot be given simply because assignments were not done on time.   They are only appropriate when circumstances outside a student's control prevent them from completing the course on schedule (illness, family emergency, etc.). Again, please talk to the instructor if something happens where this might be an appropriate outcome.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]