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


The goal of the course is to understand how a modern compiler is structured and the major algorithms used to translate code from high-level to machine language. One of the best ways 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 - instruction selection and scheduling
  7. Register allocation
  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.

Schedule (subject to change)

01-Apr Tue Class 1 – Overview, Regex
07-Apr Mon Homework 1 – regex
08-Apr Tue Class 2 – grammar, LR(1)
14-Apr Mon Homework 2 - grammars
15-Apr Tue Class 3 – LL(1), ASTs, IR
21-Apr Mon Project 1 - Scanner
21-Apr Mon Homework 3 - grammars
22-Apr Tue Class 4 – Semantics, x86
28-Apr Mon Project 2 – Parser, ASTs
29-Apr Tue Class 5 – Codeshape
06-May Tue Class 6 – Optimizations, Dataflow
13-May Tue Class 7 – Loops, SSA
19-May Mon Project 3 – Semantics, Symbol Table
20-May Tue Class 8 – Instruction Selection, Scheduling, Reg alloc
27-May Tue Class 9 – Calling Conventions
28-May Wed Exam
03-Jun Tue Class 10 – Inlining, Multi-thread, GC
09-Jun Mon Project 4 – CodeGen
10-Jun Tue Project 5 - Report


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 four good, fairly recent compiler textbooks available, none of which clearly dominates the others. Lectures and course materials will draw on all of them (among other sources). Most of these books have been used as the official text for the course at one time or another, and any of them 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, but you are free to use whichever of these books you like. All four books are on reserve in the Engineering Library.

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. It is possible to work alone, but past experience has been 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 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 other topics later). There also will be a single exam. Assignments (and exams, of course) should be done individually.

The course grade will be computed roughly as follows:

The bulk of the project grade will be based on the final results at the end of the quarter, but we will take into account the quality and timeliness 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 for you to do well or for us to evaluate your work 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 brief group meetings with the course staff to talk about the project after everything is done.

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 on attu. We will also require that all compilers have a uniform entry point, regardless of what language they are written in. If you wish to use another implementation language (C# has been used successfully in the past, Haskell, ML, OCAML, and F# are also good choices), please talk with the instructor first.

To execute the generated code you will need access to a programming environment that can compile and run a C bootstrap program and x86 assembly language code. The default environment will be gcc and its associated assembler, but we should also be able to provide instructions for using Visual Studio and the MASM assembler that is included with it. All of these are installed in the CSE instructional labs and are available free for use on your personal machines. (Visual Studio can be obtained 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 CSE department servers for project groups that wish to set up code repositories or otherwise use shared 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 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. This also applies to using code or solutions from previous quarters or other courses.

Exams must of course be done on your own. The exam will be open book and open notes. Computers, tablets, smart phones, 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 your control prevent you from completing the course on schedule (illness, family emergency, etc.). Again, please talk to the instructor if something happens where this might be a necessary 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 Nat Mote]