CMPT-379 - Fall 2006 - Principles of Compiler Design

Announcements

• Grading for the course:
  
• Final Exam: 30%
• 3 quizzes (closed book, in class): 13% each (total of 39%)
  
• Homeworks: 31%
  
• Important Dates:
• Tue, Sep 5: First day of classes
• Mon, Dec 4: Last day of classes
• Oct 2 (in class): Quiz #1 (Topics: 1 and 2 from Syllabus below)
  
• Nov 6 (in class): Quiz #2 (Topics: 3, 4 from Syllabus below)
• Nov 27 (in class) now Nov 29 due to snow day: Quiz #3 (Topics: 5, 6, 7, 8 from Syllabus below, plus generation of MIPS or similar target)
• Final Exam: Dec 6, 2006, Time: 3:30-6:30pm, Location: RCB 8100
• Mon, Oct 9: Thanksgiving Day
  
• Sat, Nov 11: Remembrance Day (no classes)
  
• Location of data files and software packages: ~anoop/cmpt379/ on the CSIL linux machines
• Wed, May 31, 2006: Course web page created
• Mon, Sep 11, 2006: Office hours and Quiz #1 date posted.
• Mon, Sep 11, 2006: RSS feed for course announcements created.

Assignments

1. Homework #1. Distributed on Mon, Sep 11, Due on Mon, Sep 18. Files are in ~anoop/cmpt379/hw1
2. Homework #2. Distributed on Mon, Sep 18, Due on Mon, Sep 25. Files are in ~anoop/cmpt379/hw2
3. Homework #3. Distributed on Mon, Sep 25, Due on Fri, Oct 6. Files are in ~anoop/cmpt379/hw3
   • You will need to refer to the Decaf language specification
4. Homework #4. Distributed on Mon, Oct 9, Due on Mon, Oct 23. Files are in ~anoop/cmpt379/hw4
5. Homework #5. Distributed on Mon, Oct 23, Due on Fri, Nov 3. Files are in ~anoop/cmpt379/hw5
• MIPS assembly and spim documentation
• The spim simulator is installed in ~anoop/cmpt379/spim.linux
6. Homework #6. Distributed on Wed, Nov 8, Due on Mon, Nov 20. Files are in ~anoop/cmpt379/hw6
7. Homework #7. Distributed on Mon, Nov 20, Due on Mon, Nov 27 (changed, see below). Files are in ~anoop/cmpt379/hw7
   • New Deadline: Homework #7 and Q.1 from Homework #8 is now due on Fri, Dec 1.
8. Homework #8. Distributed on Mon, Nov 27, Due on Mon, Dec 4 (changed, see below).
   • Q.1 merged with Homework #7. Other components of the homework are now optional but due on Dec 1. Do not submit this homework on Dec 4.

Important note on assignment submission and development: Your homework will be submitted electronically using the department-provided submission server. Connect to the submission server by going to the URL: https://submit.cs.sfu.ca/

It is expected that your program will compile and run using the standard gcc or g++ compiler on the Linux CSIL lab machines. If you are developing on a Linux or Windows machine at home, you have to ensure that the code will run on the CSIL machines before you submit the assignment. Please either visit the CSIL lab machines or you can use ssh to login to the CSIL Linux machines and also use scp to copy over and test your programs on the CSIL Linux machines before you submit them. Check the CSIL Layout map for the machine names.

Note that the C++ compiler for gcc version 2.96 and gcc version 3.3.2 are seriously broken and will not be compatible with gcc on the CSIL machines. Check the version you are using by running the command gcc --version

For Windows machines, you might want to look into the use of the cygwin environment and the dos2unix command on Linux. There will be no extensions for problems with non-CSIL machines, so don't ask.

On some CSIL Linux machines, in some rare cases, you might have to extend your CPU time limit for a process. If you are using tcsh then run the command "limit cputime 1800" to extend CPU time to 1800 secs or 30 mins. If you are using bash then use the command "ulimit -t 1800".

The files for each homework are available in the directory ~anoop/cmpt379/. The directory is accessible only on the CSIL linux machines.

Use a makefile to compile your program, and test and cleanup your program output. Two examples are provided: a simple one in ~anoop/cmpt379/hw1 and a more complex one in ~anoop/cmpt379/howto-make. In the directory howto-make try the commands make, make test, make clean and make tarball.

Textbook and References

• Textbook:
• Compilers: Principles, Techniques and Tools, A.V. Aho, R. Sethi, and J.D. Ullman, Addison-Wesley, 1986. ISBN: 0201100886
  
• Only for review:
• Sipser refers to Introduction to the Theory of Computation by Michael Sipser. 1996, PWS Pub. Co. ISBN: 053494728X
• Reference Textbooks: Material that I use from time to time, but not required reading for those taking the course.
  
• Modern Compiler Implementation in {C,ML,Java} by Andrew W. Appel. 2002, Cambridge Univ Press.
  
• Theory of Parsing, Translation and Compiling (Vol 1: Parsing and Vol 2: Compiling) by A. V. Aho and J. D. Ullman. 1972-1973, Prentice Hall.
• Advanced Compiler Design and Implementation by Steven S. Muchnick. 1997, Morgan Kaufmann.
• Course materials: From Compilers courses taught at SFU and elsewhere. Typically I read and use materials from these courses for my lecture notes and for assignment ideas. I mention them here to acknowledge their work.
• CMPT 379: SFU
  
• CS 143: Stanford University
  
• 6.035: MIT
• CISC 672: University of Delaware

Syllabus and Readings

1. Introduction to Compiler Design
   
• Chp 1
• Notes #1
• Code sample: duff-a.c
• Links: Reflections on Trusting Trust, Ken Thompson. CACM 27(8), pp. 761-763, 1984.
• Code sample: dylib.ar, dynamic linking in unix (to extract files, run ar -x dylib.ar)
2. Lexical Analysis
• Chp 3
• Notes #2
• Code sample: adhocScanner.c
• Links: Historical Perspective: FORTRAN I
• Links: Posix regular expression specification
• Links: Storing a sparse table. R. E. Tarjan and A. C. Yao. CACM 22(11), 1979.
3. Formal languages and automata, Analysis of Ambiguity
• Chp 0, 1 (Sipser)
• Notes #3
4. Syntax Analysis, Deterministic Parsing and sub-classes of CFGs
   
• Chp 4
• Notes #4
• Notes #5
• Notes #6
• Notes #7
• Demos: nltk_demos.ar, parsing demos using nltk-lite v0.6 (to extract files, run ar -x nltk_demos.ar).
  Note that you will need to install the Python-based open-source toolkit called nltk before you can run the demos.
  It will run only on nltk-lite version 0.6.
• Links: tree.hh -- STL style tree class implementation
5. Abstract Syntax Trees
• Chp 2, 2.5
• Notes #8
6. Stack Frames and Parameter Passing
• Chp 7, 7.1-7.5
• Notes #9
• Code sample: fact.decaf converted to mips-fact.mips versus gcc-fact.mips
7. Syntax-directed Translation and Semantics
• Chp 5 and 6
• Notes #10
• Notes #11 (pages 16-57 not covered)
• Code sample: funcptr.cc
• Code sample: Implementing visitors in tree-matching code
8. Translation to Intermediate Code
• Chp 8
• Notes #12
9. Code Generation and Register Allocation
   
• Chp 9
• Notes #13
• Code sample: using-heap.mips
• Code sample: global-vars.mips
• Code sample: array-vars.mips
10. Code Optimization
• Chp 10, 10.1-10.4
  
• Notes #14
11. Wrap-up
• Conclusion
  

Course Expectations and Policies

• All course information on this web page is tentative and could be in error. It can also change at any time. Confirm crucial dates or information with me in person during class. Double check with SFU calendar or schedule information for official class times and final exams time and location.
• Students are expected to attend all classes: announcements about assigned readings, homeworks and exams will be made available at the start of each class. Such announcements may not be made on this web page, so don't rely on information here instead of attending class.
• Lecture notes or other materials put up on this web page are only additional material and not an alternative to the readings assigned. Only reading the lecture notes will not be enough to prepare for the assignments or the exams.
• Late assignments will be graded as follows: marks earned for assignments submitted after 11:45pm on the due date will be multiplied by a 0.8 penalty. Submissions two days late will get a penalty of 0.6 * grade, and any submission three days or more will be 0.4 * grade (Sat, Sun and holidays are included). Any submission identical to a solution key will get zero marks.
• If you must miss an exam because of illness, you are required to contact me prior to the exam either by email or a message in my mailbox. A valid note from a medical doctor is required specifying date of absence and reason. If you miss an exam due to valid medical reasons you will be graded on your performance on the rest of the course. Make up exams will not be given under any circumstances.
• Email policy: Use the prefix "cmpt-379: " on all your messages. If you do not include the prefix, then the mail might go unanswered. Do not send general questions about the class or the material to me directly. Instead use the class mailing list "cmpt-379 @ sfu.ca" to post your question.
• For personal advising come during my office hours (posted above).
• Copying on assignments or exams will be taken very seriously. If you are caught cheating on an assignment or an exam you will be hauled off for disciplinary action. There will be no assignments to be solved as a group. Despite this, students often meet to discuss the assignments. You have to be very careful that you do not take any notes or copy during these meetings.
• For more on academic dishonesty read the University code of academic honesty.
• I will give partial credit on exams. If you provide an incorrect answer but your work shows some understanding you will get partial credit, but if you have the correct answer, and your work shows a misunderstanding of the course material you will lose marks.