198:415 - Compilers

Announcements

• I will offer office hours on Tuesday, May 8 at our usual time.
• All sample solutions are now available.
• Sample midterm solution .

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, 1:30pm - 2:30pm, or by appointment
  
  
• Jeff Ames (jca105@cs.rutgers.edu)
  Office: Wednesday, 1:00pm - 2:00pm, or by appointment
  Office hours: Hill 402
  
  

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)
  This is the first edition. The second edition of the book can also be used.
  
  
• recommended (ALSU): Aho, Lam, Sethi and Ullman: Compilers: Principles, Techniques, and Tools (Dragon Book, Second Edition)
  Addison-Wesley, 2007, ISBN 0-321-48681-1
  This is the second edition. The first edition of the book can also be used.

Academic Integrity

Please read carefully.

Read/Post questions

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

MIDTERM

There will be a midterm exam on March 7, 2012. This is a closed book, closed notes exam of 80 minutes.

FINAL EXAM

There will be a final exam on May 9, 2012, noon - 3:00pm. This is a closed book, closed notes exam.

Lecture Notes

• January 18, 2012 -- Lecture 1
  Course overview, what are compilers, why studying compiler design, front end, back end, middle end, register allocation, instruction scheduling
  Reading: EAC Chapter 1
  
  
• January 23, 2012 -- CLASS IS CANCELED
  
  
• January 25, 2012 -- Lecture 2
  Register allocation: ILOC; register-register vs. memory-memory model; aliasing problem; code shape issues; top-down allocation; live ranges
  Reading: EAC Chapters 13.1 - 13.3
  
  
• January 30, 2012 -- CLASS IS CANCELED
  
  
• February 1, 2012 -- Lecture 3
  Register allocation: top-down and bottom-up allocation; different heuristics;
  Reading: EAC Chapters 13.1 - 13.3
  
  
• February 6, 2012 -- Lecture 4
  Introduction to instruction scheduling; notion of dependence (true, anti, output), dependence graph, list scheduling algorithm
  Reading: EAC Chapters 12.1 - 12.3
  
  
• February 8, 2012 -- Lecture 5
  Forward list scheduling algorithm, different heuristics
  Reading: EAC Chapters 12.1 - 12.3
  
  
• February 13, 2012 -- Lecture 6
  Introduction to scanning, regular expressions, NFA and DFA, mapping regular expressions to NFAs
  Reading: EAC Chapters 2.1 - 2.4
  
  
• February 15, 2012 -- Lecture 7
  NFA to DFA construction, minimization of DFA; special scanning challenges
  Reading: EAC Chapters 2.1 - 2.4
  
  
• February 20, 2012 -- Lecture 8
  Introduction to parsing, CFGs, derivations, parse trees, ambiguity
  Reading: EAC Chapters 3.1 - 3.2
  
  
• February 22, 2012 -- Lecture 9
  Top-down parsing, left-recursion elimination, FIRST and FOLLOW sets, LL(1) grammars
  Reading: EAC Chapter 3.3
  
  
• February 27, 2012 -- Lecture 10
  LL(1) parse tables, resursive descent parsing, example parse
  Reading: EAC Chapter 3.3
  
  
• February 29, 2012 -- Lecture 11
  Left-factoring; bottom-up parsing, examples, shift-reduce parser
  Reading: EAC Chapter 3.4
  
  
• March 5, 2012 -- Lecture 12
  More bottom-up parsing examples, handle, reductions, table-driven bottom-up parsing
  Reading: EAC Chapter 3.4
  
  
• March 7 - midterm exam, in class
  
  
• March 12 - 16, 2012 -- spring break
  
  
• March 19, 2012 -- Lecture 13
  Table-driven bottom-up parsing, ACTION and GOTO tables, LR(1) items, LR(1) cannonical collection
  Reading: EAC Chapter 3.4
  
  
• March 21, 2012 -- Lecture 14
  Larger LR(1) cannonical collection example, LR(0), SLR(1), LALR(1)
  Reading: EAC Chapter 3.4
  
  
• March 26, 2012 -- Lecture 15
  Error recovery in YACC; introduction to static semantics; attribute grammars, synthesized vs. inherited attributes, S-attributed, L-attributed, syntax-directed translation schemes (SDL)
  Reading: EAC Chapter 4.1 - 4.3
  
  
• March 28, 2012 -- Lecture 16
  Syntax-directed translation schemes (SDL), comparison to attribute grammars, second project overview
  Reading: EAC Chapter 4.1 - 4.4
  
  
• Apri 2, 2012 -- Lecture 17
  Type systems, type checking, inference rules
  Reading: EAC Chapter 4.1 - 4.2;
  
  
• Apri 4, 2012 -- Lecture 18
  Symbol tables, intermediate representations
  Reading: EAC Chapter 5.1 - 5.3, 5.5; 7.1 - 7.3
  
  
• Apri 9, 2012 -- Lecture 19
  Code shape, code generation, array layouts
  Reading: EAC Chapter 7.1 - 7.3
  
  
• Apri 11, 2012 -- Lecture 20
  More code generation, representation of boolean values, code for control constructs
  Reading: EAC Chapter 7.1 - 7.3
  
  
• Apri 16, 2012 -- Lecture 21
  Vectorization vs. parallelisation, dependence analysis
  Reading: TBA
  
  
• Apri 18, 2012 -- Lecture 22
  Dependence analysis, vectorization
  Reading: EAC Chapter 6.1 - 6.5
  
  Reading: TBA
  
  
• Apri 23, 2012 -- Lecture 23
  Common subexpression elimination; Procedure abstraction, runtime environment
  Reading: EAC Chapter 6.1 - 6.5
  
  
• Apri 25, 2012 -- Lecture 24
  Activation records, dynamic vs. static scoping, access links,
  Reading: EAC Chapter 6.1 - 6.5, 7.1 - 7.2
  
  
• Apri 30, 2012 -- Lecture 25
  Dynamic vs. static scoping, access links and displays, implementation of linkage conventions
  Reading: EAC Chapter 6.1 - 6.5, 7.1 - 7.2
  
  
• May 9 - final exam, in class, noon-3:00pm
  
  

Homeworks

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

• Problem Set 1 , due: February 1, 2012 (sample solution)
• Problem Set 2 , due: February 8, 2012 (sample solution)
• Problem Set 3 , due: February 15, 2012 (sample solution)
• Problem Set 4 , due: February 22, 2012 (sample solution)
• Problem Set 5 , due: February 29, 2012 (sample solution)
• Problem Set 6 , due: March 28, 2012 (sample solution)
• Problem Set 7 , due: April 4, 2012 (sample solution)
• Problem Set 8 , due: April 11, 2012 (sample solution)
• Problem Set 9 , due: April 18, 2012 (sample solution)
• Problem Set 10 , due: April 25, 2012 (sample solution)
• Problem Set 11 due: will not be graded. (sample solution, problem 1 and 2) , (sample solution, problem 3 and 4)

Projects

For the projects, we use the machines in the ilab cluster. The ilab cluster page contains the listing of valid hostnames available for projects. Be aware that ilab.rutgers.edu, pasta.rutgers.edu and soup.rutgers.edu are NOT to be used . Remember to use a type of pasta (macaroni.rutgers.edu), etc. You have the same home directory across all machines of the ilab cluster .

• Local instruction scheduler; NEW DUE DATE: March 5 (code) and March 5 (report), 2012
  
  
• A Pacal Subset Compiler Front-End ; NEW DUE DATE: April 20, 2012
  
  
• A Pacal Subset Compiler Code Generator; DUE DATE (no extension): May 6, 2012
  
  

Acknowledgement

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