Instructor: Hal Perkins, perkins@cs.washington.edu,
Sieg 208; 206-543-4784. Office Hours: TTh after class plus whenever the door
is open.
Teaching Assistant: Nan Li, annli@cs.washington.edu
. Office Hours: tba
Scheduled for TTh, 6:30-7:50pm, Sieg 322 (on campus) and at Microsoft (distance). Students are welcome to attend at either location, and should feel free to switch locations as needed.
The course web site is www.cs.washington.edu/582/. 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 normally 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.
We can also schedule a "Java bootcamp" early in the quarter if there are students who are not familiar with Java who would like a quick introduction to the language.
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 background to take the course.
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 Engineering a Compiler by Keith Cooper and Linda Torczon. This book is still in draft form, due to be published early next year by Morgan Kauffman. Copies of the latest draft are available for CSE582 students from Professional Copy & Print, 4200 University Way (the Ave & 42nd St.).
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. This book is not required for CSE 582, but some lecture material will draw on it.
A recent book is Modern Compiler Implementation in Java by Andrew Appel (Cambridge University Press, 1998). The CSE582 project will use some compiler tools developed for this book. Be sure to check the errata page for corrections (http://www.cs.princeton.edu/~appel/modern/java/errata.html) if you use this book.
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.
You may work on the project yourself, or you may work in groups of two or three. We encourage you to work in a group, but that has the usual tradeoffs: other people to share the workload vs. having to coordinate with those people. It may be easier for a group to implement a more ambitious project, but often some of the most spectacular projects are done by individuals.
In addition to the project, there will be some written homework assignments (mostly on parsing and similar issues), 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 also how well it is written (i.e., code quality counts for something). A written report describing the project will be due at the end of the quarter, and students will meet with the instructor 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 (either Java 1.3 or 1.4 will be fine for the project). If you wish to use another implementation language, please talk with the instructor first. Recent versions of Java are installed in the instructional labs in Sieg Hall, 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). These are also installed in the instructional labs. Either Visual Studio 6 and Visual Studio .NET is fine; instructions for installing (if necessary) and running the assembler will be provided on the course web site.
Space will be available on the department web for project groups that wish to set up a CVS repository to manage their code.
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.
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.)