CMPU 331: Compiler Design (Spring 2018)

This is the syllabus page for the Compiler Design class. It will evolve over the course of the semester, so check back regularly. You are responsible for keeping up-to-date with any changes here.

An online discussion group will be set up in due course.

Personnel

Faculty

  • Professor Simon Ellis. Website.
  • Office hours: Tuesday, 12.30 - 2.30 p.m.; Thursday, 12.30 - 2 p.m..
  • Location: Sanders Classroom 220.

Coach

  • Mr George Whiteside.
  • Office hours: Tuesday, 6 - 10 p.m.; Sunday, 7 - 8 p.m..
  • Location: Asprey Lab..

Textbook

Aho, Alfred V., Lam, Monica S., Sethi, Ravi & Ullman, Jeffrey D., Compilers: Principles, Techniques, and Tools (2nd edition).

Course Requirements

  1. Weekly readings.
  2. Written examination. (40%)
  3. A significant programming project. (60%)

Examination

The examination will be a 48-hour take-home exam and will be available on Tuesday, 1st May.

You must collect a copy of the exam from Mrs Colabella in the CS Department Office. The time you take the exam will be noted. You must return it by that time on Thursday, 3rd May. Exams returned late will not be accepted except in the case of extenuating circumstances.

Project

The project consists of implementing a compiler front-end, in four parts: lexical analysis routines, a parser, symbol table management routines, and semantic routines. Each piece must be integrated with what has been completed previously.

The project should be implemented in either Java or Python.

  • If you use Java, I recommend the IntelliJ IDE, or NetBeans as an alternative.
  • If you use Python, I recommend the PyCharm IDE.

All of the IDEs named above are available on the CS department Linux systems. Downloads are available here.

Class Schedule

This schedule is provisional and subject to change. You are responsible for keeping yourself apprised of the current status of this schedule.

It is expected that you will have completed the appropriate readings before the corresponding class(es). You are responsible for keeping up with the readings and for ensuring that you have adequate notes of material covered in class, some of which may not be in the textbook: this includes lectures, assignments, hand-outs, additional reading, and so forth.

If you miss a class, it is your responsibility to make arrangements with classmates to acquire information presented.

Topics and Readings

Week Beginning Topic Reading Slides
0 22nd January Introduction Ch. 1, 2.1-2.5. Full Handout
1 29th January Lexical analysis. Ch. 2.6, 3.1-3.5, 3.8. Full Handout
2 5th February Languages, syntax and parsing. Ch. 4.1-4.3. Full Handout
3 12th February Top-down parsing. Ch. 4.4. Full Handout
4 19th February Bottom-up parsing.
More powerful bottom-up parsing.
Ch. 4.5-4.6.
Ch. 4.7.
Full
Handout
5 26th February Symbol tables. Ch. 2.7, 7.1-7.3. Full Handout
6 5th March
Spring Break
7 26th March Syntax-directed translation. Ch. 5. Full Handout
8 2nd April Intermediate code generation. Ch. 2.8, 6.1-6.3. Full Handout
9 9th April Runtime environments.
The Vassar Interpreter
Arithmetic expressions.
Ch. 6.4-6.5, 7.1-7.4. Full Handout
Full Handout
Full Handout
10 16th April Optimisation and code generation. Ch. 9.1-9.4, 8.4-8.5, 8.7-8.8. Full Handout
11 23rd April Relational expressions and control flow.
Optimisation and code generation I (conclusion).
Ch. 6.6-6.7. Full Handout
12 30th April Procedure and function declaration and calls. Ch. 7.1-7.3.
13 7th May
End of classes

Project

Component Specification Date released Date due Weighting
Lexical analyser (lexer) Lexical analyser (lexer) Thursday, 1st February Thursday, 15th February 10%
Parser Parser Tuesday, 20th February Tuesday, 6th March 7.5%
Symbol table routines Symbol table routines Tuesday, 27th March Friday, 6th April 2.5%
Semantic actions (part 1) Semantic actions 1 5%
Semantic actions (part 2) Semantic actions 2 Thursday, 5th April Friday, 20th April 7.5%
Semantic actions (part 3) Semantic actions 3 Thursday, 19th April Friday, 4th May 12.5%
Complete compiler Complete compiler Thursday, 26th April Tuesday, 15th May 15%
Extra credit Corrections to errors in phases I-VI. Tuesday, 15th May 10%
TOTAL 70%
Extra Credit

If you have made revisions to code in phases I-VI and would like the code reviewed for extra credit, you must state this in the README file for the final submission, as follows:

  1. Include a section called 'Extra Credit'.
  2. For each module you have changed (e.g. Lexical Analyser, Parser), write a list outlining the major changes you have made.
  3. Include function names or line numbers if appropriate.

This will help me to find the updated code quickly and run appropriate tests. The extra credit will be added to your total grade for the project.

Project Score Cap

The score for the project component will be capped at 60% of the total for the course. In other words, the project can count for a maximum of 60% of the grade for the course, with the exam. making up the remaining 40% of the total.

Test files

Test files are available in the directories listed here.

To upload a test file, use the following command:

331upload [lexer|parser|code] <filename>

Submission policy

All components are due by 11.59:59 pm on the date specified. See the submission guidelines for further information.

Late work will be subject to the late policy as described.

Please note that the due date for the complete compiler is the latest time possible under Vassar College legislation.

Examination

This will likely be a 48-hour take-home exam scheduled towards the end of the semester, not in the final exam block.

Policies & Procedures

I support wholeheartedly and implement all the general policies of Vassar College, including but not limited to those relevant to students with disabilities, plagiarism, and respectful classroom etiquette.

Academic accommodations are available for students registered with the Office for Accessibility and Educational Opportunity (AEO). Students in need of disability (ADA/504) accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course that have been approved by the Office for Accessibility and Educational Opportunity, as indicated in your AEO accommodation letter.

Classroom Policy

Attendance

Attendance is not required, but it is strongly recommended: in-class discussions and explanations will likely not be posted online.

Participation

While most of this class takes the form of lectures, I welcome and encourage discussion and questions on the subject under discussion. If you are unsure about something, if you are just curious, if you want to play “Devil's advocate” (within reason) — please ask questions.

"Failure-Okay Zone"

I endeavour to foster an atmosphere in which it feels safe to fail. My classroom is a failure-okay zone: in fact, I welcome failure, since we frequently learn more by failure than by success.

Mobile phones

Please set your mobile telephone to silent and put it away.

Laptops

I prefer students not to use laptops in class, if possible. Please bring [(paper)+] and [(pen)+|(pencil)+|(stylus)+] to make notes.

Late Policy

Work submitted late will be subject to an incremental 10% penalty per day or part day late. Work received more than 96 hours (four days) late will automatically receive a grade of 0.

Exceptions to this policy may be made in the case of extenuating circumstances.

Extenuating Circumstances

I accept and recognise that there may be occasions where significant problems occur. I am more than willing to work with students who are having genuine difficulties with their work because of life events beyond their control (e.g. illness or bereavement). However, I ask that you make me aware of such situations as soon as possible, and I require documentary evidence of some form in order to be able to make any accommodation.

Backup Policy (a.k.a. "The Internet Ate My Homework")

The compiler is a significant programming project and should be treated like any other major piece of work. It is expected that you will make regular backups of your work and develop your code incrementally: together, these steps will increase the likelihood of you being able to recover from a significant loss of work.

As it is expected that you will make backups, the excuse, “I couldn't submit my work because [computer-related reason],” is no longer generally acceptable.