Instructor: Hal Perkins, perkins at cs,
CSE 548; 206-543-4784. Office Hours: after class plus whenever
the door is open or by appointment.
Teaching Assistant: Yael Schwartzman, yaels at cs
. Office Hours: Tuesday 4:30 to 6:30 pm in CSE 218 or by appointment.
Scheduled for Tuesdays, 6:30-9:20 pm, EE1 037. There will be one exam about two-thirds of the way through the course on a Thursday evening from 6:30-7:50 pm. We'll try to pin down the exact date early in the quarter.
The course web site is www.cs.washington.edu/csep501/. Registered students will be automatically subscribed to a class mailing list and we will have a discussion board on the web. Links will be available from the course web site.
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 by default be written in Java and will use scanner and parser generator tools. Variations on the project, particularly the implementation language, are possible; talk to the instructor if you want to try something different.
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 should be 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 if you have the appropriate background.
This is an introductory compiler course; we will start at the beginning, although we'll move right along. If you've already had an undergraduate compiler course, this course will repeat the basics, but hopefully will introduce new material you haven't seen before. Again, talk to the instructor if you're not sure whether this is the course for you.
The main text for the course is Modern Compiler Implementation in Java by Andrew Appel (Cambridge University Press, 2nd edition, 2002). Be sure to get the 2nd edition - it contains the MiniJava compiler project that we will use as the basis for the course project.
The classic textbook for many years has been the Dragon Book (named for the creature on the cover): Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman (Addison-Wesley, 1986). The Dragon Book has a much more extensive treatment of parsing and language theory than we will cover. Another good, and recent, compiler textbook is Engineering a Compiler by Keith Cooper and Linda Torczon (Morgan-Kaufman, 2004). This book is particularly good for coverage of the design tradeoffs needed to build real compilers. Neither book is required for the course, but lecture material will draw from both of them as well as from the main text.
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 an individual (although some of the individual projects have been among the most impressive!). It's often helpful to have a partner to talk to as the work is done.
In addition to the project, there will be some written homework assignments (mostly on parsing and similar issues, earlier in the course), and an exam about 2/3 of the way through the quarter. These 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 on a project 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.
We reserve the right to adjust these percentages if it seems appropriate.
You are free to use any computer 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 of Sun's Java tools. If you wish to use another implementation language (C# has been used successfully in the past, ML is also a great choice), please talk with the instructor first. Recent versions of Java 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 Visual C++ (to run the bootstrap program that is written in C), and the MASM assembler (to assemble your code). MASM is included in recent versions of Visual Studio .Net. This is also installed in the instructional labs, and, as a CSE student, you can obtain a free copy if you don't have it already. Again, other target machines are possible, discuss this if you want to try something different.
Space will be available on the department web for project groups that wish to set up a CVS repository to manage their code or otherwise use a centralized file server.
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.
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.).