Important Dates
- This page last updated on: $Date: 2007-11-27 21:13:06 $
- Grading for the course:
- Final Exam: 34%
- 3 quizzes (in class): 12% each (total of 36%)
- Homeworks: 30%
- Important Dates:
- Tue, Sep 4: First day of classes
- Thu, Sep 27: Quiz #1
- Thu, Nov 1: Quiz #2
- Thu, Nov 29: Quiz #3
- Final Exam: Dec 10, 2007, Time: 3:30-6:30pm, Location: WMC 2507
- Location of data files and software packages:
~anoop/cmpt379/on the CSIL linux machines or~anoop/cmpt379/on fraser.sfu.ca
Programming Assignments
Supporting files
In order to complete some parts of your assignments, you will need to refer to the following files:
- Decaf language definition (version of 9/10/07)
- MIPS assembly and
spimdocumentation
The MIPS virtual machine, spim is available in the directory ~anoop/cmpt379/spim.linux/ for the CSIL Linux machines, and the directory ~anoop/cmpt379/spim.solaris/ if you are running on fraser.sfu.ca
You can download spim but make sure you use version 6.5 and also you must make absolutely sure that your code runs on the CSIL Linux machines before you submit your homework code.
Homeworks
- Homework #1. Due Sep 25. 6%
- Homework #2. Due Oct 16. 6%
- Homework #3. Due Nov 6. deadline extended to Nov 8. 6%
- Homework #4. Due Nov 27. 6%
- Homework #5. Due Dec 4. 6%
Notes on assignment submission and development
You must use a makefile to compile your program, test and cleanup your program output. Running "make" should compile your program and running "make test" should run any tests on sample inputs.
- Sample makefiles are provided to you with Homework #1.
- A gentle make tutorial from U. Hawaii (en français).
- For hardcore hacking, refer to
info make.
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.
In addition, we will be using flex (preferably version 2.5.33) and bison (preferably version 2.3) in order to build our compiler.
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.
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".
Textbook and References
- Textbook:
- Compilers: Principles, Techniques and Tools (2nd Edition), Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison-Wesley, 2006: ISBN-13: 978-0321486813 (the purple dragon book)
- Reference text: (optional)
- lex & yacc. 2nd Ed. John R. Levine, Tony Mason and Doug Brown. O'Reilly. ISBN 1-56592-000-7
- 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.
Syllabus and Readings
- Introduction to Compiler Design
- Chp 1
- Notes #1 (9/5/07)
- 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)
- Lexical Analysis
- Chp 3
- Notes #2 (9/20/07)
- Code sample: adhocScanner.c
- Links: Historical Perspective: FORTRAN I
- Links: Regular Expression Matching Can Be Simple And Fast and Implementing Regular Expressions by Russ Cox.
- Links: Posix "regular expression" specification
- Links: Storing a sparse table. R. E. Tarjan and A. C. Yao. CACM 22(11), 1979.
- Formal languages and automata, Analysis of Ambiguity
- Notes #3 (9/10/07)
- Syntax Analysis, Deterministic Parsing and sub-classes of
CFGs
- Chp 4
- Notes #4 (10/4/07)
- Notes #5 (10/18/07)
- Notes #6 (10/18/07)
- Notes #7 (10/22/07)
- Links: tree.hh -- STL style tree class implementation
- Simple Syntax-directed translations, Abstract Syntax Trees
- Chp 2, esp 2.5
- Notes #8 (10/25/07)
- Syntax-directed Translation and Semantics
- Chp 5 and Chp 6.3 to 6.5
- Notes #9 (11/12/07)
- Notes #10 (11/27/07)
- Code sample: Implementing visitors in tree-matching code
- Translation to Intermediate Code
- Chp 6 (excluding Chp 6.3 to 6.5)
- Notes #11 (11/13/07)
- Run-time Environment, Stack frames and parameter passing
- Chp 7, 7.1-7.4
- Notes #12 (11/05/07)
- Code Generation and Register Allocation
- Chp 8
- Notes #13 (11/27/07)
- Code Optimization
- Chp 9, 9.1-9.6
- Notes #14 (11/27/07)
- Wrap-up
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: you will have 5 grace days which you can use throughout the semester; you can use all 5 days for one assignment or submit upto 5 assignments late by one day without penalty (or any other combination that adds up to 5 days). Once your grace days are used up you will be graded on 40% of the total grade for the assignment.
- If you must miss an exam because of a medical problem, you should make an attempt to contact me prior to the exam either by email or a message in my mailbox.
- To request an extension of the due date due to a medical problem, you must submit the offical SFU Health Care Provider statement. 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.
- 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.