198:415 - Compilers

Announcements

• Project 3 DEADLINE EXTENSION: TUESDAY, MAY 5, 8:00am .
• The basic student code version for project 3 is now available ( parse.y, scan.l, attr.h, attr.c, symtab.h and symtab.c). The project subdirectory (~uli/cs415/spring09/projects/proj3) on the ilab cluster also contains a sample code generator ( scg ) and five testcases in subdirectory testcases. You are encouraged to use your solution from project 2 as the starting point of your project 3 solution . However, you may use the provided code as a starting point for your third projects as well. There is not impact on your grade.
• The last homework problem set is now available.
• Here is the midterm sample solution . Please look at the sample solution first if you have any questions. If question remain, please come and talk to me.

Description

Introduction to compiler construction. Course contents include the following: Formal translation of programming languages, program syntax and semantics. Finite state recognizers and regular grammars. Context-free parsing techniques such as LL(k) and LR(k). Attribute grammars, syntax-directed translation schema, type checking, register allocation, instruction selection, code generation, data flow analysis and code improvement transformations (code optimizations). There will be at least two programming projects, most likely three projects.

Staff

• Ulrich (Uli) Kremer (uli@cs.rutgers.edu)
  Office: CoRE 318
  Office hours: Tuesday, 3:00-4:00pm or by appointment
  
  
• John McCabe (jomccabe@cs)
  Office: CoRE 334
  Office hours: Thursday, 3:00-5:00pm
  
  

Prerequisites, Lectures and Recitations

Textbooks

• required (EAC): K. Cooper and L. Torczon: Engineering a Compiler
  Morgan-Kaufmann Publishers, 2004, ISBN 1-55860-698-X (hardback), ISBN 1-55860-699-8 (paperback)
  
  
• recommended (ALSU): Aho, Lam, Sethi and Ullman: Compilers: Principles, Techniques, and Tools (Dragon Book, Second Edition)
  Addison-Wesley, 2007, ISBN 0-321-48681-1

Academic Integrity

Read/Post questions

Please post questions regarding homeworks and projects using Rutgers's Sakai system . Select Discussion and Private Messages in our course group (198:415:01 S09). DO NOT send homework or project questions directly to John or me. THANKS!
You should read the news group at least every other day!

MIDTERM

There will be one midterm exam.

FINAL EXAM

There will be a final exam.

Lecture Notes

• January 21, 2009 -- Lecture 1
  Course overview, what are compilers, why studying compiler design, multi-pass compilers
  Reading: EAC Chapter 1
  
  
• January 26, 2009 -- Lecture 2
  Continuation of course overview, examples of classical compilers, register allocation (top-down and bottom-up)
  Reading: EAC Chapter 1, Chapters 13.1 - 13.3
  
  
• January 28, 2009 -- Lecture 3
  Register allocation and assignment (top-down and bottom-up)
  Reading: EAC Chapter 1, Chapters 13.1 - 13.3
  
  
• February 2, 2009 -- Lecture 4
  More register allocation and assignment (top-down and bottom-up); Lexical analysis
  Reading: EAC Chapter 1, Chapters 13.1 - 13.3
  
  
• February 4, 2009 -- Lecture 5
  Lexical analysis: regular expressions, finite state machines
  Reading: EAC Chapter 2.1 - 2.5
  
  
• February 9, 2009 -- Lecture 6
  Finite state machines, NFA, DFA, simulate NFA by DFA (subset construction)
  Reading: EAC Chapter 2.1 - 2.5
  
  
• February 11, 2009 -- Lecture 7
  Minimal DFA, examples, limits of regular expressions
  Reading: EAC Chapter 2.1 - 2.5, 3.1 - 3.2
  
  
• February 16, 2009 -- Lecture 8
  CFG, derivation, parse tree, ambiguity, introduction to parsing
  Reading: EAC Chapter 3.1 - 3.2
  
  
• February 18, 2009 -- Lecture 9
  Introduction to parsing, top-down parsing with backtracking, left-recursion removal
  Reading: EAC Chapter 3.1 - 3.3
  
  
• February 23, 2009 -- Lecture 10
  Predictive parsing, FIRST and FOLLOW sets, LL(1) property, recursive descent parser
  Reading: EAC Chapter 3.3
  
  
• February 25, 2009 -- Lecture 11
  Recursive descent parsing examples, left factoring, introduction to bottom-up parsing
  Reading: EAC Chapter 3.3 - 3.4
  
  
• March 2, 2009 -- Class canceled due to weather
  
  
• March 4, 2009 -- Lecture 12
  Bottom-up parsing, handle, LR cannonical collections
  Reading: EAC Chapter 3.4 - 3.5
  
  
• March 9, 2009 -- Lecture 13
  LR(1) cannonical collections, ACTION and GOTO tables, skeleton LR(1) parser
  Reading: EAC Chapter 3.4 - 3.5
  
  
• March 11, 2009 -- Lecture 14
  LR(1), LR(0), SLR(1), LALR(1) parsing
  Reading: EAC Chapter 3.5, 3.6.4
  
  
• March 16 and 18, 2009 -- Spring Recess, no classes
  
  
• March 23, 2009 -- Lecture 15
  SLR(1), LALR(1), language and grammar hierarchy
  Reading: EAC Chapter 4.1, 4.3
  
  
• March 25, 2009 -- Midterm exam
  
  
• March 30, 2009 -- Lecture 16
  Introduction to context-sensitive analysis, attribute grammars
  Reading: EAC Chapter 4.1, 4.3
  
  
• April 1, 2009 -- Lecture 17
  More attribute grammars, examples, syntax-directed translation scheme, initial project #2 discussion
  Reading: EAC Chapter 4.1 - 4.4
  
  
• April 6, 2009 -- Lecture 18
  Syntax-directed translation scheme, examples, attribute value allocation project #2 discussion, type systems
  Reading: EAC Chapter 4.1 - 4.4
  
  
• April 8, 2009 -- Lecture 19
  Type systems, symbol table, intermediate representations
  Reading: EAC Chapter 4.1 - 4.4
  
  
• April 13, 2009 -- Lecture 20
  Intermediate representations, DAG construction, quadrupels and triples
  Reading: EAC Chapter 5
  
  
• April 15, 2009 -- Lecture 21
  Intermediate representations, code generation
  Reading: EAC Chapter 7.1 - 7.3, 7.5, 7.8
  
  
• April 20, 2009 -- Lecture 22
  Code generation for simple expressions (tree walk and SDT scheme), assignment statements
  Reading: EAC Chapter 7.1 - 7.3, 7.5, 7.8
  
  
• April 22, 2009 -- Lecture 23
  Storage mapping for arrays; code generation for control structures
  Reading: EAC Chapter 7.1 - 7.3, 7.5, 7.8
  
  
• April 27, 2009 -- Lecture 24
  Introduction to procedure abstractions: control, name space
  Reading: EAC Chapter 6
  
  
• April 29, 2009 -- Lecture 25
  Project 3 implementation hints; activation records, access links
  Reading: EAC Chapter 6
  
  
• May 4, 2009 -- Lecture 26
  Procedure abstraction: lexical scoping, access links, displays, linkage conventions.
  Reading: EAC Chapter 6
  
  
• May 7, 2009 -- final exam 8:00-11:00am, in class
  
  

Homeworks

Homeworks must be handed in at the beginning of your recitation.

• Problem Set 1 due date Wednesday, February 4
  Sample Solution
  
  
• Problem Set 2 due date Wednesday, February 18
  Sample Solution
  
  
• Problem Set 3 due date Wednesday, February 25
  Sample Solution
  
  
• Problem Set 4 due date Wednesday, March 4
  Sample Solution Recursive Descent Parser (C), Sample Solution for other problems
  
  
• Problem Set 5 due date Monday, March 23 (before class)
  Sample Solution
  
  
• Problem Set 6 due date Wednesday, April 8
  Sample Solution
  
  
• Problem Set 7 due date Wednesday, April 22
  Sample Solution
  
  
• Problem Set 8 due date Wednesday, April 29
  Sample Solution
  
  

Projects

• local register allocation .
  NEW Due date: March 3 (code) and March 6 (report)
  Please use SAKAI to submit your project. Note: You will only to be able to submit your project once. If you need to resubmit your project, please do so via email (uli@cs.rutgers.edu, jomccabe@cs.rutgers.edu). Due to the failure of Sakai, you have until Wednesday night (March 4) to submit your project code (part 1) via Sakai. Your project has to be submitted via Sakai, that is, your Sakai submission is the one that counts. We only accept email submissions if you had submitted a Sakai version earlier! All other forms of submission (for instance you only emailed your project without submitting to Sakai first) are not accepted.
  
  
• A Pascal Subset Compiler Front-End .
  New due date: Thursday, April 23. NO LATE SUBMISSIONS!
  
  
• A Pascal Subset Code Generator .
  Due date: May 5, 8:00am! NO LATER SUBMISSIONS!
  No need to implement break statements
  Basic student code version will be made available Friday, April 24.

Acknowledgement

This course has been based on courses taught by Keith Cooper at Rice University and Chau-Wen Tseng at the University of Maryland.