The Compiler Course -- Spring 2011 -- The Last Compiler Course

Bergin icon Joseph Bergin - - Pace University, New York

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.

Get Connected to the Course List Server

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.

Bookmark the Course Interactive Web Site

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.

Get a Book

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


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

Other Useful Books (and why)

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.

Some Interesting Papers

Here is a discussion of the Four Color Problem/Theorem from Mathematics. 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.

Get Java

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++.

Get the Course Materials and Tools

These can be downloaded from the main course page. They include various tools and the project skeletons and tests.

Set up Java

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 Good Java Style

Use a good programming style. This is required. There is a page on Java coding conventions.

Come to Class

Your faithful attendance is expected. It will be difficult to be a success otherwise.

Build and Submit the First Project (Individual Work)

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.

Build the Large Project (Group Work)

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.

Submit Reports Every Other Week

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.

Submit the Large Project

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.

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.

Take the Final Exam (May 6)

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.


  1. 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.
  2. 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.
  3. 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.

    1. Extension of the grammar to handle new tokens, rewriting the grammar rules to handle new syntax, use of parser generator to produce new Scanner and Parser. Multiple underscore problem. (100 points).
    2. Declarations of Boolean variables, Boolean literals(40 points)
    3. String constants and output of strings (50 points)
    4. User defined types. typedef, (20 points)
    5. Constant declarations and constant expressions, constant folding, Modulo operator(50 points),
    6. Not, And and Or operators and the additional operators such as relational operators(40 points)
    7. Semantic error recovery and typechecks. (70 points)
    8. Loop statements (do) (20 points)
    9. Range variables and forall statement (50) points.
    10. Array declarations, and subscript element references (50 points)
    11. Module list declarations and qualified name references for modules (50 points)
    12. Code optimization. E.G. don't add 0, don't repeat constants (30 points)
    13. Recursive procedures with no parameters (Declaration) (40 points)
    14. Procedure call. (30 points)
    15. Parameters for procedures and non local data access (30 points)
    16. Nested tuple field access, this, and the @ operator. (30 points)

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.

Course FAQ (Frequently Asked Questions)

You may find answers to some of your questions in the course FAQ.

How You May Look At The End Of The Course

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.

compiler 2011

Here are many of the undergraduate compiler builders after they turned in their projects in April 2001.

Compiler Students

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