Spring 2011 Syllabus and Plan of Action
NOT completely UP TO DATE
Do not underestimate the difficulty of this course and do not underestimate the amount of time you will need to put into it to be successful. Most people are successful here, but also find it very stressfull. Generally, those who are not successful either give up and decide not to do the work or try to cut corners and lapse into various forms of dishonest work. There is no need for this. You will be given a tremendous amount of support. However, in order to be successful you need to have a solid level of programming skill in Java or a similar language. If you do not yet have this skill, or have written only very small programs, I suggest that you take a course first in which you can improve your skill. A course with a substantial programming project is a good choice. You will write a lot of Java code in this course. If you have doubts about your readiness for this course send me an email.
There are a number of goals of this course that go beyond learning how a compiler works and is built. It is a good test of your teamwork skills and your organizational ability. If you are not already a professional software developer this may be the largest program you have ever been asked to work on, so it introduces you to work on programs that are larger than you can conveniently understand all at once. Therefore the structure is important. Compilers are also a place in which the theory of computer science meets the practice and the practice won't work without the theory. The theory, by the way, is very beautiful. If you want to develop this theory further, the course on Computability is the right place to start. The project that you will work on in this course will also introduce you to the idea of software patterns that have become an important force in software development in the last decade.
The instructor will provide instructions for this at the first class period. The list server will be the main means of communication throughout the course. You must subscribe to it from one or more of your email accounts. Once you are subscribed, any message that you send to the list will be distributed to all subscribers.
This course has an associated interactive website (a wiki wiki web) to which you can post information. In particular, you can give anonymous feedback about the course at any time. The instructor will provide details about its URL. You may want to bookmark this site and visit it often. It uses a simple but sophisticated web technology that makes every page editable. The server (JWiki) is available in source format and is written in Java. Do not link to this site, however, or it will be spammed. Bookmarking is fine.
You will need a text book. The first is recommended, but the second is ok.
Crafting a Compiler With C by Charles N. Fischer, Richard J. Jr. Leblanc, Addison-Wesley Pub Co; ISBN: 0805321667
OR
Compilers : Principles, Techniques, and Tools by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman , Addison-Wesley Pub Co; ISBN: 0201100886
OR (less valuable for us, but a good book)
Programming Language Processors in Java by Watt and Brown
There is also be a set of course notes that are required. These are available in the Instructor and will be needed at the first class session. Notes For A Compiler Course by Bergin
The project is full of design patterns. To read more about this important topic see Patterns in Java by Mark Grand (Wiley) Volume 1.
Java coding style is shown on my home page (see the Java coding conventions) and also in the book: Essential Java Style: Patterns for Implementation, Langr, Prentice Hall, 2000
Refactoring by Martin Fowler (Addison-Wesley) is a good source for understanding how to improve and extend Object-oriented programs.
Design Patterns Explained by Shalloway and Trott (Addison-Wesley) is a good place to understand Object-orientation and design patterns. This is probably better than Grand.
There are also a number of books on the printed sylabus.
None of these are essential.
Here is a discussion of the Four Color Problem/Theorem from Mathematics. http://www.maa.org/devlin/devlin_01_05.html. It has become important in modern (optimizing) compilers. Why it is important will be explained during the course.
Ken Thompson's Turing Award Lecture. "Reflections on Trusting Trust" is a must read for any student of compilers. It is quite short and very interesting.
I have a page of recommendations on Java environments. We will use Eclipse, however.
If you don't already know Java you will need to know at least C++ and be familiar with object-oriented programming (at least a bit). I have a page of comparisons between Java and C++.
These can be downloaded from the main course page. They include various tools and the project skeletons and tests.
Java and Eclipse set up easily on your computer using tools with their respective distributions. If you use a Macintosh, it already has its own version of Java installed. Don't try to install a different one. On the Mac, Java comes from Apple, not from Sun.
Use a good programming style. This is required. There is a page on Java coding conventions.
Your faithful attendance is expected. It will be difficult to be a success otherwise.
The first two chapters of Fischer and LeBlanc will help with this. You will add one feature to a simple compiler using recursive descent compiling. This is due February 4 . There is a 10% late penalty. If the grade is less than you would like you may resubmit for regrading. NO late work will be accepted after April 15.
The starting point (skeletons) is with the materials in the MicroGCL directory.
Your submission must include the source code and all test runs. All changes from the original must be hilited.
Everything here (and everything in the course) should be printed SINGLE SIDED only, black and white preferred, in a readable font. Some of these rules may seem arbitrary, but they aid grading and let me focus on giving you the best feedback in the time available.
The instructor will spend most of the class time on the project. You should keep your work up to date to benefit from the class pace (fast). Don't work too far ahead or behind the instructor.
You will be expected to be a faithful team member. Any difficulties with other members should be brought to the attention of the instructor as early as possible. You are responsible individually for all of the project even if you are working in a team. Expect that some team difficulties will occur (illness, dropping the course...). You will still be held responsible for the entire project.
The instructor will provide a sample compiler that should implement all features. You will not have the source code for this, but may run it to see what code works for output from a correct compiler.
I suggest that you use the Pair Programming technique for all work on the compiler. This means two team members at the computer with one having control of the keyboard and the other watching for errors and making suggestions for improvements. The keyboard can switch hands frequently. I suggest, but do not require, that you do not divide up the work with different members doing different features. You will probably suffer on the final exam if you do this, and you will definitely suffer if a team member drops the course. If you choose to do this, make sure you coordinate closely and frequently. Here is the pair programming plugin for Eclipse: XPairtise. It can be used to do pair programming over the net.
Back up your work regularly. Crashes, viruses, lost work, etc are not valid reasons for not making progress and making deadlines.
If you have more than two members on your team, then you can use the chatroom features of AOL Instant messaging to work together without actually being together. You don't need to belong to AOL to use this. The client software is available (free) on the AOL web site. If you do belong to AOL you will still need the IM client to use the chatroom feature as this is not integrated into the regular AOL client.
If your compiler runs to completion (doesn't crash) the listing will include errors that were found. However, if it does crash, some of the errors are in the standard output, and perhaps not in the listing. In particular, null pointer errors and class cast errors show up in the standard output. Your listing may even indicate no errors.
Reports must be submitted in a simple plain manila folder with your names on it, printed single sided. All recent changes must be hi-lighted. Include your grammar (always) and any recently changed files and any recent test runs (compiler output and macc2 inputs and outputs only). If you don't meet this specification, I won't look at your work due to time constraints.
"Recent" means since the previous report. DO NOT include files that are not needed.
These submissions are not graded. You will get back comments on your progress and suggestions as needed.
As you build new things, make sure you don't break old things. Run old tests when you run new ones.
The large project is due on the last regular day of class (April 29) prior to the final exam . It must be submitted in a simple binding, including all of the following and nothing more. Submit ONE volume. It will be between 1 and 2 inches thick. Use an ACCO binding or similar, NOT a three ring binder. Find the binding early in the course. They are available at stationery stores in the area.
- Statement of correctness signed by all team members. This should tell what works and what doesn't. It should also say who built what or that you built all features jointly.
- Grammar: Your COCO grammar. All changes from the original hilited neatly.
- Source Code (ALL files including Scanner, Parser... even if you didn't modify the files during the course. All changes from the original hilited neatly. They should be in the same order as that in the compiler course notes: Grammar first ...Semacts last.
- Compiler output for any test completed. These are the test runs with the @c+ option turned on. DO NOT submit the original test files or the SAM2 outputs or codefiles. Submit ONLY the compiler runs. (see page 81 of notes). Again, DO NOT include the codefiles or the SAM2 runs.
- MACC2 inputs and outputs for any test completed. A macc2 run input and output for a test should immediately follow the corresponding compiler output. Do NOT collect all the macc2 runs together.
- Disk (or CD) with grammar and all Java files. This should be in an envelope that is taped to the inside back cover of your submission. The disk should also include a text file with the names of all team members and your statement of correctness. Put your names on the disk label
Plan to spend several hours preparing this final report. Make sure your printouts are readable and the left margins won't get lost in the bindings. The binding should be to the left of the pages and single sided printouts are required. Do not print in landscape mode. You should also make a complete copy for yourself as well.
If you can't complete the large project to your satisfaction, you may want to request an incomplete for the course. This must be in writing prior to the due date of the project.
The above submission requirements are STRICT, including the final submission deadline.
Bring a personal copy of your compiler to the final and a pencil with eraser. Pen is acceptable. You should also bring any books and notes that you think you may need. You will not be allowed to exchange any materials during the exam.
- Assignment 1. Due the third class period (February 4 ). Extend the MicroGCL Language from the course materials to include an IF THEN ELSE END statement, etc. 100 points. Individual assignment. May be redone if you don't like the grade you get initially. 10% late penalty.
- Project. Due the last regular class period (April 29). Extend the GCL language to add all features in the manual. 700 points. Team assignment. Teams of two persons should be formed by the third class period. This assignment is to be turned in in both hard-copy form and on diskette. The materials will not be returned.
- Final Exam (May 6 ) covering (primarily) comparative methods and compiler extensions. 200 points.
Final grade is the simple average of these 1000 points.
The large project will be graded according to the following outline. This assumes everything well done in good style. Note that the implication is that you don't need to do everything to pass. However, what you do should be well done. It will be essentially impossible to get better than a B+ if you do nothing with procedures. Partial credit will be given for incomplete work that has merit.
If you finish this and want more to do, the instructor can provide a few extensions.
Individual work is done by the individual alone without help from others. Team work is done by the team alone without help from others. No work is collaborative in any way except within the teams. Help may be sought via the instructor and the course list server. No code will be exchanged among the teams and no work from previous years will be examined or used. Any evidence to the contrary will be severly dealt with. Those who give their work to others are dealt with as severely as those who use it.
You may find answers to some of your questions in the course FAQ.
As I'm retiring in June 2011, this is the last compiler course. Here are most of the "victims." Thanks to you all. And thanks to the many students who have taken this course over the years.
Here are many of the undergraduate compiler builders after they turned in their projects in April 2001.
And below are some of the undergraduate students in May 2002 after their final exam. Hmmm. Not so many smiles.
Last Updated: April 30, 2011