Location
Announcements
Assignments
References
Weekly Readings
Course Policies (first time here? read this)
Anoop Sarkar
Location: Wed. AQ 5007; Fri. AQ 5005
Time: 9-10:20am; Wed, Fri
gosfu Term: 1047
gosfu Class Number: 9899
Mailing List: cmpt-755 @ sfu.ca
Mailing list archives
Office: ASB 10830
Office hours: Thurs 10:30a-12:30p
Compiler Theory is an Area II course in Computing Systems. Algorithms used in building a compiler and their underlying foundations from formal language theory will be covered. We will cover each component of a compiler including lexical analysis, parsing, code generation, code optimization and type checking. This course will also cover advanced topics in parsing theory and implementation for arbitrary and deterministic grammars. Students will also implement a working compiler for a high level programming language
More details: Course outline (ps)
Announcements |
- Grading for the course:
- Final Paper or Final Exam: 30%
- 2 quizzes (take-home):
20% each (total of 40%)
- Homeworks: 30%
- Important Dates:
- Sep 8, 2004: First day of class
- Dec 1, 2004: Last day of class
- Oct 15: Quiz #1
(take-home, distributed on Oct 13, topics
and example questions)
- Nov 19: Quiz #2 (take-home, distributed on Nov 17, topics and example questions)
- Location of data files and
software packages:
/cs/fac1/anoop/cmpt755/from any of the CS machines
- Mon, Aug 23, 2004: Course web page created
- Thu Sep 9, 2004: Important: The room for this course has changed: Wed. AQ 5007; Fri. AQ 5005
- Tue, Sep 28, 2004: First version of the Decaf language specification posted. Copies will be handed out in class on Wed, Sep 29.
- Mon, Oct 4, 2004: Second version of Decaf language specification posted. Changes: Fixed typo, added missing underscore to defn of identifier in Section 4.2.
- Sat, Oct 9, 2004: Posted Quiz #1 topics and example questions.
- Wed, Oct 20, 2004: Third version of the Decaf language specification posted. Changes: Changed HEX to INTCONST in Section 4.2, added \r to charConstant, removed \' from stringConstant, added \\ to stringConstant.
- Mon, Nov 15, 2004: Posted Quiz
#2 topics and example questions.
Assignments |
A brief 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://onara.cs.sfu.ca/
It is expected that your program will compile and run using the standard gcc or g++ compiler on the CS Linux machines. If you are developing on a Linux or Windows machine at home, you have to ensure that the code will run on the CS machines before you submit the assignment. Please either visit the CS graduate lab machines or you can use
ssh
to login to the CS Linux machines and also use scp to
copy over and test your programs on the CS Linux machines before you
submit them. The following Linux machines are available for your use: oak.fas,
cmpt-gl01.cs, cmpt-gl02.cs, cmpt-gl03.cs,
nitinat.cs, tsusiat.csNote 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 CS machines. Check the version you are using by running the command
gcc
--versionFor 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-CS machines.On some 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
/cs/fac1/anoop/cmpt755.
The directory is
accessible only from SFU CS machines.- Homework #1. Distributed on Fri, Sep
10, Due on Fri, Sep 17. Files are in
/cs/fac1/anoop/cmpt755/hw1 - Homework #2. Distributed on Mon, Sep 20; Due on Mon, Sep 27.
- Homework #3. Distributed on Wed, Sep
29, Due on Wed, Oct 6. Files are in
/cs/fac1/anoop/cmpt755/hw3 - Homework #4. Distributed on Wed, Oct
6, Due on Wed, Oct 20. Files are in
/cs/fac1/anoop/cmpt755/hw4 - Homework #5. Distributed on Fri, Oct
22, Due on Fri, Oct 29. Files are in in
/cs/fac1/anoop/cmpt755/hw5 - Homework #6. Distributed on Mon, Nov 1, Due on Mon, Nov 8.
- MIPS
assembly and
spimdocumentation - The
spimsimulator is installed in/cs/fac1/anoop/cmpt755/spim.linux - Homework #7. Distributed on Tue, Nov 9, Due on Tue, Nov 23.
- Homework #8. Distributed on Thu, Nov
25, Due on Thu, Dec 2.
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.
- Engineering a Compiler by Keith D. Cooper and Linda Torczon. 2003, 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; Lexical Analysis review
- Chp 1,2,3
- Notes #1
- Notes #2
- Code sample: duff-a.c
- Links: Historical Perspective: FORTRAN I
- Reflections on Trusting Trust. Ken Thompson. CACM 27(8), pp. 761-763, 1984.
- Storing a sparse table. R. E. Tarjan and A. C. Yao. CACM 22(11), 1979.
- Syntax Analysis, Deterministic Parsing and sub-classes of
CFGs
- Chp 4
- Notes #3
- Notes #4
- Notes #5
- Transforming LR(k) Grammars to LR(1), ... Mickunas, Lancaster and Schneider. JACM 23(3), 1976.
- Parsing arbitrary CFGs
- An efficient context-free parsing algorithm. Jay Earley. CACM 26(1). 1983.
- An Improved
Context-Free
Recognizer. Susan L. Graham, Michael A. Harrison and Walter L.
Ruzzo. ACM Transactions on
Programming Languages
and Systems, Vol. 2, No. 3, pp. 415--462, 1980.
- Polynomial time and space shift-reduce parsing of arbitrary context-free grammars. Yves Schabes. Proceedings of the 29th conference on Association for Computational Linguistics, Berkeley, California, pp. 106--113, 1991.
- Abstract Syntax Trees
- Chp 2, 2.5
- Notes #6
- Stack Frames and Parameter Passing
- Chp 7, 7.1-7.5
- Notes #7
- Syntax-directed Translation and Semantics
- Chp 5 and 6
- Notes #8
- Notes #9
- Code sample: funcptr.cc
- Error correction
- Robert A. Wagner, Order-n correction for regular languages. Communications of the ACM. Volume 17, Issue 5 (May 1974) pp. 265-268.
- Translation to Intermediate Code
- Chp 8
- Notes #10
- Code Generation and Register Allocation
- Chp 9
- Notes #11
- Code sample: fact.decaf converted to mips-fact.mips or to gcc-fact.mips
- Code sample: global-vars.mips
- Tree Transducers
- Comon et al. Chapter 6, Tree Automata Techniques and Applications. unpublished book.
- J.W. Thatcher, Tree automata: an informal survey, Currents in the Theory of Computing (Alfred V.Aho, ed.), chapter 4, pp. 143--172, Prentice-Hall, 1973.
- Code Optimization
- Chp 10
- Notes #12
- Deductive Parsing and Semirings
- Principles and implementation of deductive parsing. Stuart M. Shieber, Yves Schabes, and Fernando C. N. Pereira. Journal of Logic Programming, 24(1-2):3-36, July-August 1995. Also available as cmp-lg/9404008
- On The Complexity Analysis of Static Analyses. David McAllester. JACM 49(4): 512-537, 2002.
- Semiring Parsing. Joshua Goodman. Computational Linguistics, Vol. 25, No. 4, pp. 573--605, December 1999.
Course Expectations and Policies |
- Students are expected to attend all classes and to arrive
on
time: announcements about assigned readings, homeworks and exams will
be made available at the start of each class.
- Students are expected to have read all assigned readings (from the required reading material) before class. Simply attending the class will not provide adequate preparation for the exams. You will need to work out examples from the reading materials before you come to 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 755: " 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-755 @ 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.
anoop at cs.sfu.ca