198:415 - Compilers

Announcements

• All homework sample solutions are not available.
• Final exam recitation on Friday, May 4, at 11:00am in CoRE A
• Homework problem set 7 is now available.
• Handin project ID now available for third project.
• Deadline extension for third project. New deadline: Tuesday, May 1, 11:59pm .
  
• The description of the third project has been updated.
  

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: Tuesdays 2:00-3:00pm
  
  
• John McCabe
  Office: Hill 367
  Office hours: Mondays 3:15-4:15pm or by appointment
  
  

Prerequisites, Lectures and Recitations

Textbooks

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

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 S07). 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 on Tuesday, May 8, noon-3:00pm, in Hill 254 (our regular class room). The exam will be a closed book, closed notes exam. If you have any conflict , please let me know Wednesday, April 25 .

Lecture Notes

• January 17, 2007 -- Lecture 1
  Course overview, what are compilers, why studying compiler design, multi-pass compilers, examples of classical compilers.
  Reading: EAC Chapter 1
  
  
• January 22, 2007 -- Lecture 2
  Lexical Analysis: DFA-NFA-RE, minimal DFA, scanner
  Reading: EAC Chapter 2.1 - 2.5
  
  
• January 24, 2007 -- Lecture 3
  Syntax Analysis: Left-most and rightmost derivations, parse tree, ambiguity
  Reading: EAC Chapter 3.1-3.2
  
  
• January 29, 2007 -- Lecture 4
  Syntax Analysis: Top-down parsing, back-tracking, predictive parsing
  Reading: EAC Chapter 3.3
  
  
• January 31, 2007 -- Lecture 5
  Syntax Analysis: FIRST and FOLLOW sets, LL(1) parsing, table-driven and recursive descent parsing
  Reading: EAC Chapters 3.3
  
  
• February 5, 2007 -- Lecture 6
  Recursive descent parser examples (interpreter and compiler)
  Reading: EAC Chapters 1.5
  
  
• February 7, 2007 -- Lecture 7
  register-register vs. memory-memory models, introduction to register allocation and assignment
  Reading: EAC Chapters 1.5, 13.1 - 13.3
  
  
• February 12, 2007 -- Lecture 8
  top-down and bottom-up allocation, left-factoring
  Reading: EAC Chapters 13.1 - 13.3, 3.3.4
  
  
• February 14, 2007 -- no class
  
  
• February 19, 2007 -- Lecture 9
  Bottom-up parsing, handle, LR(0) example construction (in class)
  Reading: EAC Chapters 3.4, 3.5
  
  
• February 21, 2007 -- Lecture 10
  LR(1) parsing, table-driven parsing, GOTO and ACTION tables, LR(1) cannonical collection
  Reading: EAC Chapters 3.4, 3.5
  
  
• February 26, 2007 -- Lecture 11
  LR(1) cannonical collection
  Reading: EAC Chapters 3.4, 3.5
  
  
• February 28, 2007 -- Lecture 12
  LR(0), SLR(0)
  Reading: EAC Chapters 3.4, 3.5
  
  
• March 5, 2007 -- Lecture 13
  LR(0), SLR(0), LALR(1), LR(1) examples
  Reading: EAC Chapters 3.4, 3.5
  
  
• March 7, 2007 -- Lecture 14
  error recovery, introduction to attribute grammars
  Reading: EAC Chapters 4.1 - 4.3
  
  
• March 12 and 14, 2007 -- spring break
  
  
• March 19, 2007 -- no class
  
  
• March 20 -- midterm recitation session --
  Time: 6:30pm, Location: CoRE A (301)
  
  
• March 21, 2007 -- midterm exam -- (in class, closed book, closed notes).
  
  
• March 26, 2007 -- Lecture 15
  attribute grammars, syntax directed translation schemes
  Reading: EAC Chapters 4.4
  
  
• March 28, 2007 -- Lecture 16
  syntax directed translation schemes, project 2 (flex and bison)
  Reading: EAC Chapters 4.4, 5.7
  
  
• April 2, 2007 -- Lecture 17
  type systems, symbol table
  Reading: EAC Chapters 5.7
  
  
• April 4, 2007 -- Lecture 18
  intermediate program representations
  Reading: EAC Chapters 5.1-5.6
  
  
• April 9, 2007 -- Lecture 19
  intermediate program representations, introduction to code generation
  Reading: EAC Chapters 5.1-5.6
  
  
• April 11, 2007 -- Lecture 20
  code generation, code shape
  Reading: EAC Chapters 7.1-7.6
  
  
• April 16, 2007 -- cancelled due to weather conditions
  
  
• April 18, 2007 -- Lecture 21
  introduction to code generation, discussion of code generation project
  Reading: EAC Chapters 7.1-7.6
  
  
• April 23, 2007 -- Lecture 22
  code generation
  Reading: EAC Chapters 7.1-7.6
  
  
• April 25, 2007 -- Lecture 23
  Procedure abstraction
  Reading: EAC Chapters 6.1-6.7
  
  
• April 30, 2007 -- Lecture 24
  Procedure abstraction
  Reading: EAC Chapters 6.1-6.7
  
  
• May 4, 2007 -- final exam recitation session, 11:00am, CoRE 301 (CoRE A conference room)
  
  
• May 8, 2007 -- final exam , noon-3:00pm, Hill 254
  
  

Homeworks

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

• Problem Set 1 due on Thursday, February 1, before recitation
  Sample Solution
  
  
• Problem Set 2 due on Thursday, February 8, before recitation
  Sample Solution , ReadMe (problem 4) , code (problem 4)
  
  
• Problem Set 3 due on Thursday, February 22, before recitation
  Sample Solution
  
  
• Problem Set 4 due on Wednesday, March 7, before class
  Sample Solution
  
  
• Problem Set 5 due on Thursday, April 5, before recitation
  Sample Solution
  
  
• Problem Set 6 due on Thursday, April 12, before recitation
  Sample Solution
  
  
• Problem Set 7 due on Monday, April 30, before class
  Sample Solution: problem 1 and 2 , Sample Solution: problem 3 ,
  
  

Projects

• local register allocation .
  Due date: March 6 (code) and March 8 (report)
  Please use the handin website to submit your project. You will need to submit your project code and your project report separately.
  
  
• Front-End and Code Generator .
  Due date: April 13 (Front-End) and May 1 (Code Generator)
  Please use the handin website to submit your project. Reminder: "tar" all the files together, including a ReadMe file to let the TA know about any problems or special "features" of your solution.

Acknowledgement

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