COMP 520 Compiler Design (Fall 2008)

This website has been updated for Fall 2008, however please note that some of the provided information may still change before the course begins. Please refer to this web page weekly to review the course material and to check for updated links. All class members are encouraged to follow changes to the public_html directory using Subversion; all important announcements will be made in class or via email.


News

13/12: I have commited your grades and a short solution to the exam questions into your personal SVN directories. Happy holidays!
28/11: Please sacrifice a few minutes of your time and fill in the course evaluation form on MINERVA. Your feedback is very important to me! Thanks!
28/11: I have decided to grant everybody a DEADLINE EXTENSION for submitting your WIG report and compiler. Both items are now due on Sunday, Nov. 30th, at 8am sharp.
21/11:
The slides for next week are online.
21/11: Congratulations to Ning Jia, Alexis Malozemoff and Wei Wu for winning the annual peephole contest! Slides on peephole contest (PDF) (PPTX)

Academic Integrity at McGill University

McGill University values academic integrity. Therefore all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures (see http://www.mcgill.ca/integrity/ for more information). A helpful article on how to avoid plagiarism can be found at: http://www.mcgill.ca/integrity/studentguide/.

In terms of this course, part of your responsibility is to ensure that you put the name of the author on all code that is submitted. By putting your name on the code you are indicating that it is completely your own work. If you use some third-party code you must have permission to use it and you must clearly indicate the source of the code.

About this course

Official course description
Philosophy of the course
Availability

People

Lecturer: Eric Bodden (McConnell 234)
Teaching assistant: Reehan Shaikh (McConnell 202)

Printed Readings

Course text (readings)
Lecture notes

Deadlines and Important Dates

Deliverables, milestones, and exercises
Week by week schedule
Midterm

Project

The project description
The A- source code (flex/bison/C)
The A- source code (SableCC/Java)
The A+ project
The A+ binary
JOOS examples
JOOS library source
JOOS extern classes

How to run Java and JOOS programs

How to use Subversion

Project

The project description
Original WIG grammar
Yacc-style grammar, most conflicts solved
Sablecc-style grammar (version 2, scanner might have issues with keyword-stealing)
How to run SableCC
WIG examples
How to compile and run WIG services

The <bigwig> project
The Mawl project

Need help? Let us and others help you out!

We have created a Google group that you can use to manage the creation of teams or to ask general questions about the lecture material etc. The list will be read by the instructor, the TA and other participating students.

Google Groups
Subscribe to COMP 520 Fall 2008
Email:




Visit this group

Please do not use this group to discuss private issues such as grading etc. but rather contact the TA or instructor directly in such cases. Important announcements will be sent to you directly and/or made available on this website. There is no need to join the group to receive such announcements.

Online documentation

The flex scanner generator
The bison parser generator
The SableCC compiler generator
The Java language specification
The Java virtual machine
The Java API documentation

HTML User Guides
CGI Programming
The HTML 4.0 specification
The CGI specification

Under The Hood articles:

Futher reading:

Peephole contest

Rules and prizes
Results and Winners


Week by week
Timeline
Timeline

Click on the image on the right for a timeline for this course. You may use this timeline as a planning aid. At any time, the timeline should tell you what would be a sensible thing to be working on rhight now. Note however, that some of the dates are still subject to change and that the timeline may be incomplete. All items in the timeline are clickable and may reveal additional information when clicked. Also note that the times of the day on the timeline are off (while the dates should be correct). Therefore refer to this website for exact submission deadlines etc.

Week 1: Introduction, bootstrapping a compiler

   September 2008
Su M Tu W Th F Sa
1 2 3 4 5 6
* *

Slides, 4-on-1

Reading C1: Introduction, Louden (Chapter 1), pages 1-30
Reading C2: Lexical Analysis, Appel (Chapter 2) pages 16-38
Reading
O1: Flex, version 2.5, by Vern Paxson

IMPORTANT: ALL students must read our Guide to using Subversion and ALL of the material in the Chapters 1 and 2 of Version Control with Subversion. Students must send their SSH key to the TA by Friday night (see the guide). Include information about which student(s) you would like to pair up with for the group project. Having trouble finding partners? Use our discussion group.

Students who do not have a background in regular languages and finite state automata should review this material on their own. A good online resource may be found here. This review should be done ASAP.

Voluntary background reading: The Scala Experiment

Week 2: Scanners and parsers

   September 2008
Su M Tu W Th F Sa
7 8 9 10 11 12 13
* * *

Slides, 4-on-1

Exercises Solutions
Reading
C3: Context-Free Grammars and Parsing, Louden (Chapter 3), pages 95-142
Reading
C4: Parsing, Appel (Chapter 3.2 - 3.5), pages 46-87

Week 3: Abstract syntax trees and SableCC

   September 2008
Su M Tu W Th F Sa
14 15 16 17 18 19 20
* * *

Slides, 4-on-1
SableCC Slides

Tiny expression language source code

Exercises

Reading O2: Bison, The YACC-compatible Parser Generator
Reading
O3: SableCC, Gagnon (Chapters 3-6)

WIG milestone: form groups and begin planning

Week 4:

   September 2008
Su M Tu W Th F Sa
21 22 23 24 25 26 27
* * *

Slides, 4-on-1

Exercises

WIG milestone: Try out each toolset on a Tiny example

Week 5:

   September 2008
Su M Tu W Th F Sa
28 29 30
*

October 2008
Su M Tu W Th F Sa
1 2 3 4
* *

Slides, 4-on-1

Exercises

JOOS deliverable: benchmark programs
JOOS deliverable: comments and desugaring

Reading O4: A Beginner's Guide to HTML
Reading O5: An instantaneous introduction to CGI scripts and HTML forms

Week 6: Symbol tables

    October 2008
Su M Tu W Th F Sa
5 6 7 8 9 10 11
* * **

Note: On October 10th, Andrew Casey will give a special lecture on using attribute grammars in JastAdd.

Regular lecture slides:  Slides, 4-on-1
Special lecture slides:   Slides, 4-on-1

There will be no exercises this week. If you have spare time please take the chance to work ahead on the next milestone!

WIG milestone: CGI vs. WIG

Reading C5: Symbol Tables, Louden (Chapter 6.3.1 - 6.3.4), pages 295-308
Voluntary reading: Enabling Static Analysis for Partial Java Programs

Week 7: Type checking

    October 2008
Su M Tu W Th F Sa
12 13 14 15 16 17 18
H * *

Monday, October 13th is a holiday. To make up for the lost time there will be an additioal class on Tuesday, December 2nd (course calendar).

Slides, 4-on-1

Exercises

WIG milestone: scanner and parser

Reading C6: Data Types and Type Checking, Louden (Chapter 6.4), pages 313-334

Week 8: Virtual machines

    October 2008
Su M Tu W Th F Sa
19 20 21 22 23 24 25
* * *

Slides, 4-on-1

Exercises

WIG milestone: symbol tables

Voluntary reading: Draft specification of Java bytecodes

Week 9: Code generation

    October 2008
Su M Tu W Th F Sa
26 27 28 29 30 31
** * *
(midterm)

November 2008
Su M Tu W Th F Sa
1

Slides, 4-on-1

Exercises

WIG milestone: type checking

midterm

Week 10: Optimization

   November 2008
Su M Tu W Th F Sa
2 3 4 5 6 7 8
* * *

Slides, 4-on-1

There will be no exercises this week. If you have spare time please take the chance to work ahead on the peephole patterns.

JOOS deliverable: stack limits

Week 11: Garbage collection

   November 2008
Su M Tu W Th F Sa
9 10 11 12 13 14 15
* * *

Note: The lectures on November 10th and 12th will be given by Chris Pickett.
Slides 13 through 17 from Chris' lecture are here.

Slides, 4-on-1

There will be no exercises this week. Time to work on your peephole patterns.

Week 12: Native code generation

   November 2008
Su M Tu W Th F Sa
16 17 18 19 20 21 22
** * *
(peepholes)

Slides, 4-on-1
Slides on peephole contest (PDF) (PPTX)
Exercises

JOOS deliverable: peephole patterns

Note the deadline on MONDAY!

Week 13: Static analysis

   November 2008
Su M Tu W Th F Sa
23 24 25 26 27 28 29
* * *

Slides, 4-on-1

WIG compiler and report due on Friday Sunday, 8am!

There will be no exercises this week. Better work on your WIG compiler & report.

Week 14: Presenting your compilers

   November 2008
Su M Tu W Th F Sa
30
December 2008
Su M Tu W Th F Sa
1 2 3 4 5 6
** **
(project)

Meetings of Groups

WIG deliverable: compiler
WIG deliverable: report

Week 15: Final exam

December 2008
Su M Tu W Th F Sa
7 8 9 10 11 12 13
**
The final exam is going to take place on Friday, December 12th, 9am-12pm, in room LEA 31.


Past courses:


2004 course: http://www.sable.mcgill.ca/~hendren/520/
2005 course: http://www.cs.mcgill.ca/~nnaeem/520/
2006 course: http://www.cs.mcgill.ca/~cs520/fall2006
2007 course: http://www.sable.mcgill.ca/~cpicke/520/

Maintained by Eric Bodden [HOME]