The University of Western Ontario
London, Canada

Department of Computer Science

CS 447a -- Compiler Theory

Course Outline -- Fall 2004

Course Description

The emphasis of this course is on solving problems universally encountered in designing a language translator. Indeed, few people are likely to build or even maintain a compiler. However, the ideas and techniques of compiler theory apply to many problems in software engineering and in other areas. For example, the string matching techniques for building the lexical analyzer of a compiler are also used by text editors or pattern matching programs. The techniques from graph theory for performing code optimization, such as coloring, are used to organize schedules. Hence, the student should come away from the course with a deeper understanding of what happens when they compile programs but also with an enriching experience with algorithms and computers.


Computer Science 208a/b and 331 a/b; Computer Science 212a/b/y or the former Computer Science 201.

A good knowledge and practice of C is assumed. Familiarity with a variety of programming languages is a bonus, although not required.

Unless you have either the requisites for this course or written special permission from your Dean to enroll in it, you will be removed from this course and it will be deleted from your record. This decision may not be appealed. You will receive no adjustment to your fees in the event that you are dropped from a course for failing to have the necessary prerequisites.


The former Computer Science 430a and 446y.


Name:Marc Moreno Maza
Office Hours: Tuesday and Thursday, 9:00-10:00
Phone:661-2111 x6891

Lecture Notes and Textbook

Notes of each lecture will be available on the course website, approximatively one week after the oral presentation. The format (Postscript, PDF, ...) of these notes will be announced later.

There is only one (highly) recommended text for the course. However, it not required since the course web site provides extended lecture notes and corrected exercises. The other references given below are for the curious reader.

Course Website

The course web site is accessible from:

Please check the site often for updates on lecture notes and errata. Also be aware that the course website is not a substitute for actual classroom attendance!

Lecture Topics

While they have not been finalized and there is no specific schedule at this time, the order of topics will be something on the order of:

  1. Introduction to Compilers
  2. Automata and Lexical Analysis
  3. Grammars and Syntax Analysis
  4. Syntax directed translation
  5. Type checking
  6. Run-time organization
  7. Intermediate Code Generation
  8. Code Optimization
  9. Code generation

Class Schedule

Lectures: 3 hours (Tuesdays from 4:00 to 6:00pm in MC105B, Thursdays from 4:00 to 5:00pm in MC105b)

Each student is expected to attend the lectures. In particular, quizzes (short written tests) may take place without notice.

Computing Facilities

Each student will be given an account on the Computer Science Department senior undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department's Rules of Ethical Conduct

Note: After-hours access to certain Computer Science lab rooms is by student card. If a student card is lost, a replacement card will no longer open these lab rooms, and the student must bring the new card to a member of the Systems Group in Middlesex College Room 346.

Email Contact

The instructor will occasionally need to send email messages to the whole class, or to students individually. Email will be sent to your GAUL email address. You must make sure that you read your email on GAUL on a frequent and regular basis, or have it forwarded to an alternative email address if you prefer to read it there.

However, you should note that email at ITS (your UWO account) and other email providers such as or may have quotas or limits on the amount of space they can use. If you let your email accumulate there, your mailbox may fill up and you may lose important email from the instructor. Losing email that you have forwarded to an alternative email address is not an excuse for not knowing about the information that was sent.

Students can ask questions via email, however if there are any large, somewhat complicated issues, it is recommended to discuss them during office hours. Moreover, you MUST use your UWO account or your GAUL account in order to write to the instructor. Emails from non-academic accounts will be automatically ignored.

Student Evaluation

The course is very assignment oriented. Assignments constitute 50% of the course mark. There is no midterm examination. In order to successfully complete the course, a student must achieve at least 50% on the final exam and at least 50% as an overall average over all assignments and quizzes. This is to prevent a serious lack of effort in either area. Thus, a student cannot get 100% on the final and barely pass the assignments or vice-versa.

There will be at least four quizzes given, but only your best two will count toward your mark.

All assignments will be programming assignments.

Assignment One (lexical analysis)10%
Assignment Two (parsing, syntax trees)15%
Assignment Three (semantic analysis, run-time, intermediate code)25%
Quizzes (best 2 out of all)10%
Final Exam (closed book)40%

If for any reason the assignment schedules given below cannot be adhered to, the assignment and quiz marks will be pro-rated. (The 3 assignments and 2 quizzes are worth 60% of the overall mark for the course. If an assignment or quiz has to be canceled for any reason, the remaining assignment and quiz weights will be prorated to add up to 60%.)

Every effort will be made to have assignments marked and handed back within 3 weeks of the hand-in date, preferably sooner.

Exam/Quiz/Assignment Schedule

All dates are tentative and currently subject to change, although it is doubtful by any significant amount.

Evaluation Technique Weight Posted Date (tentative!) Due Date (tentative!) Workload
Assignment One10%Thursday, Sept. 23Thursday, Oct. 14light
Assignment Two15%Tuesday 19, Oct. 14Tuesday, Nov. 16regular
Assignment Three25%Tuesday, Nov. 16Tuesday, Dec. 8heavy
Final Exam40%N/ATBAN/A

Quizzes may be held without being announced in advance.

The final exam will be closed book. No printed course notes or other sheets of paper will be allowed.


Assignments will be due on the (tentative) dates listed above. You must submit an Assignment Submission Form with your assignment. The assignment can be sent by email to the instructor or given to him on a floppy disk. Assignments are marked over 20.

The late penalty is 2**m where m is the smallest integer bigger or equal to n/2 where n is the number of days late, up to a maximum of four. Hence the successive values for 2**m are 2, 2, 4 and 4.

Extensions will be granted only by the course instructor. If you have serious medical or compassionate grounds for an extension, you should take supporting documentation to the office of the Dean of your faculty, who will contact the instructor.

Since the course is based on the implementation of a practical application, all assignments must work in order to achieve a satisfactory grade. By "work", it is meant that the assignment meets the specifications as set out in the assignment description.

Ethical Conduct

All assignments are individual assignments. You may discuss approaches to problems among yourselves; however, the actual details of the work (assignment coding, answers to concept questions, etc.) must be an individual effort. Assignments that are judged to be the result of academic dishonesty will, for the student's first offense, be given a mark of zero with an additional penalty equal to the weight of the assignment also being applied. You are responsible for reading and respecting the Computer Science Department's policy on Scholastic Offenses and Rules of Ethical Conduct.

Students must write their essays and assignments in their own words. Whenever students take an idea, or a passage from another author, they must acknowledge their debt both by using quotation marks where appropriate and by proper referencing such as footnotes or citations. Plagiarism is a major academic offense (see Scholastic Offense Policy in the Western Academic Calendar).

The University of Western Ontario uses software for plagiarism checking. Students may be required to submit their written work and programs in electronic form for plagiarism checking.

Marc Moreno Maza
Last modified: Frid Nov 22 5:11:44 EDT 2002