CMPT 379 - D100
Principles of Compiler Design

Course Schedule

Course Information

Syllabus

• Formal-language theory: alphabets, words, languages, Chomsky hierarchy, regular expressions, finite automata
• Compiler design and implementation principles
• Lexical Analysis: scanners, symbol tables
• Parsing: context-free grammars, parse trees, ambiguity, top-down and bottom-up parsing
• LL(1) parsing:  efficient top-down parsing, left-factoring
• Shift-reduce parsers: bottom-up parsing
• SLR/LR parsing: efficient bottom-up parsing
• Type checking: typing rules, types as inferencing rules, context checking for programs
• Context and code generation: from high-level to machine code
• Optimization: basic-block optimizations, redundant instruction elimination, global optimization

Procedures and Policies

• Web-Page. This web page is the most accurate and reliable source of information for the course.
  In case you find an error or something that is not clear to you, please contact me immediately.
  
• E-Mail. You can contact me by e-mail (or make an appointment to see me).
  Make sure you include 'CMPT XXX' (and the assignment number) in the subject of all correspondence.
• Submission. Submit your solutions via e-mail to cmpt379-2009-1@googlegroups.com.
  Name your file appropriately, e.g., A3_Smith.pdf
  If you want to send more than one file, please send an archive, such as .rar, .tgz, .zip (if you use zip, rename the file extension to 'piz').
  Use plain text (.txt) or PDF format for all documents (you are welcome to include TeX or Word source files, but I can only read the TXT or PDF files).
• Grading. Your course grade will be based on the results of your homework assignments (30 %) and the report and implementation results of your course project (30 %), and the final exam (40 %).
  
• SFU policies. University code of academic honesty.

References (SFU Library)

• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques, & Tools. Addison-Wesley, 2007. SFU record.

Course Outline, Assignments, Reading Material

• Week 1 (2008-01-05):
• Mon: Class canceled due to snow conditions.
  
• Wed: Motivation, course outline, organization
• Fri: Introduction to alphabets, words, languages
• Reading: Chapter 1, Sections 1.1, 1.2, 1.3, 1.4
  
• No homework.
  
• Week 2 (2008-01-12):
• Mon: Formal languages, translation overview, syntax and grammars
• Wed: Chomsky hierarchy
• Fri: BNF, regular expressions and their transformation to type-3 grammars and vice versa
  
• Reading: Chapter 2, Section 2.2; Section 4.2
• Homework 1 (due 2009-01-23, 1 week): Exercises 2.2.1, 2.2.2, 2.2.3
• Week 3 (2008-01-19):
• Mon: Class canceled
  
• Wed: Example for transformation of type-3 grammar to regular expression
• Fri: Syntax trees
• Reading: Sections 3.1--3.4, 3.6
• Homework 2 (due 2009-01-30, 1 week): Exercises 4.2.1, 4.2.2 a), 4.2.3 a) b)
• Week 4 (2008-01-26):
  
• Mon: Prefix and postfix linearization/recovery
• Wed: Syntactical structure of programming languages, syntactical versus lexical analysis
• Fri: Implementation principles, modular structure, bootstrapping
• Homework 3 (due 2009-02-06, 1 week): Exercises 3.3.2 a), b), 3.3.3 a), b), 3.3.5 a), c), 3.4.1, 3.6.3, 3.6.4
• Week 5 (2008-02-02):
  
• Mon: Scanning, finite state machines, morphems, modified FSA
  
• Wed: Example FSA table for scanning, parsing strategies, top-down parsing
  
• Fri: Dead branches, bottom-up parsing
  
• Reading: Section 3.5
• Projectwork 1 (due 2009-02-20, 2 weeks): Write a scanner for the programming language used in your course project.
• Week 6 (2008-02-09):
  
• Mon: Project introduction, introduction of an example language
• Wed: Tutorial on excercises, lecture material
• Fri: Tutorial
  
• Week 7 (2008-02-16):
  
• Mon: No class -- SFU spring break (as approved by Senate)
  
• Wed: Push-down automata
  
• Fri: Parsing algorithm with back-tracking, Fast-back top-down parsing
• Week 8 (2008-02-23):
  
• Mon: Fast-back example, characterization of fast-back grammars
• Wed: Calculation of First_k sets, recursive implementation of fast-back, example
  
• Fri: LF(k) parsing
  
• Reading: Sections 4.3 and 4.4
• Homework 4 (due 2009-03-06, 1 week): Exercises 4.3.1, 4.3.2 a)
  
• Week 9 (2008-03-02):
  
• Mon: No class -- instructor sick
• Wed: Computation of table for LF, factorization, counterexample for LF and motivation for LL parsing
• Fri: LL(k) parsing, Calculation of L_k(A) sets, example for LL(3) with First sets, L sets
• Projectwork 2 (due 2009-03-13, 1 week): Implement an LF(k) parsing algorithm for the programming language used in your course project, according to the code skeleton that was presented in the lecture. Note that you can refactor the grammar and eliminate left-recursion to make it LF(1).
• Week 10 (2008-03-09):
  
• Mon: Principle of LL(k) algorithm, LL(k) algorithm with transformed grammar, control function, example sets, grammar, and control function
  
• Wed: LR(k) algorithm
  
• Fri: LR(k) algorithm cont., example
• Reading: Sections 4.5, 4.6, and 4.7
  
• Homework 5 (due 2009-03-20, 1 week): Exercises 4.5.1, 4.5.2, 4.5.3, 4.6.1 a)
• Week 11 (2008-03-16):
  
• Mon: Example for LR(1) with states, transitions, control functions
• Mon - make-up class: Checking context conditions, example and implementation skeleton
  
• Wed: Code generation (simple version for machine with accumulator stack)
  
• Fri: Code generation (extended version without accumulator stack)
  
• Reading: Section 4.9 (parser generators)
  
• Projectwork 3 (due 2009-03-27, 1 week): Implement checks for all context conditions in your compiler, according to the method and skeleton discussed in the lecture.
• Week 12 (2008-03-23):
  
• Mon: Example on code generation
  
• Wed: Storage allocation (static and dynamic)
  
• Fri: Optimization of target code, overview, local optimization
  
• Reading: Section 8.1
  
• Projectwork 4 (due 2009-04-06, 1 week): Implement the code generation for your compiler, using the introduced target language without accumulator stack.
• Week 13 (2008-03-30):
  
• Mon: Local optimization cont. and example, global optimization - loops
  
• Wed: Global optimization - strength reduction, introduction of control-flow automata for data-flow analysis
  
• Fri: Global optimization - loop splitting
  
• Week 14 (2008-04-06):
  
• Mon: Program analysis, data-flow analysis, constant propagation, intervall analysis
  

• Will be performed in groups of two students.