CS75: Compiler Construction
Spring 2007
Swarthmore College

Professor: Lisa Meeden
Course: Tuesdays and Thursdays 2:40-3:55, SCI L32
Email: meeden AT cs.swarthmore.edu
Office: SCI 243
Phone: 328-8565
Office hours: Wednesday 2-4pm, or by appointment

Course Description, Course Materials, Grading, Project Policy, Schedule

Course Description

CS75 is an introduction to compiling. We will study techniques used in the design and implementation of modern compilers. Subjects include scanning and regular expressions, context-free grammars and parsing, syntax-directed translation, abstract syntax trees, scoping, symbol tables, code generation, and code optimization. To make many of these concepts more concrete we will write a complete compiler for a non-trivial subset of the C programming language.

Course Materials

Engineering A Compiler, Keith D. Cooper and Linda Torczon
Morgan Kaufmann Publishers (2004), ISBN 1-55860-698-X

Grading

15% Project 1: Lexical Analyzer
20% Project 2: Parser
20% Project 3: Code Generator
15% Project 4: Code Optimizer

15% Midterm Exam: In class on Thursday, March 22
15% Final Exam: During finals week

Project Policy

The course consists of four projects, a scanner, a parser, a code generator, and a code optimizer, that together constitute a complete compiler for a significant subset of the C programming language, which we will call C--.

All projects will be written in the Python programming language. If you do not already know Python, you can quickly learn it. We will be using Python because it is much easier to construct an abstract syntax tree as the result of the parsing phase. This will allow us to more easily do both code generation and code optimization.

I highly encourage you to work with a partner on the projects. The first project is the most basic and can certainly be accomplished on your own. Each subsequent project is more complex and having a partner will be very beneficial.

Programming projects will be turned in online using handin75, which allows you to resubmit the same assignment multiple times up until the due date.

No late projects will be accepted unless you contact me at least 2 days in advance of the due date to explain why extra time is necessary.

Schedule

I expect you to have at least skimmed the weekly reading material prior to the first class meeting of the week.

WEEK DAY ANNOUNCEMENTS READING HW
1 Jan 23   Overview of compilation, Chapter 1
Translator for infix to postfix
Jan 25  
2 Jan 30   Scanning, Chapter 2 Project 1: Scanner
C-- Language Specification
Sample output
Feb 01 Last day to drop/add (Feb 02)
3 Feb 06   Top-down parsing, Chapter 3.1 - 3.3
Feb 08  
4 Feb 13   Bottom-up parsing and Practical issues, Chapter 3.4, 3.6, 3.8 Project 2: Parser
Sample error handling
Feb 15  
5 Feb 20   Context-sensitive analysis, Chapter 4
Feb 22  
6 Feb 27   Intermediate representations, Chapter 5
Mar 01  
7 Mar 06   Procedure abstraction, Chapter 6.1 - 6.4
Mar 08  
  Mar 13 Spring Break
Mar 15
8 Mar 20   Memory management, Chapter 6.5 - 6.8
Mar 22 Midterm Exam
9 Mar 27   Code shape, Chapter 7.1 - 7.6 Project 3a: Basic Code Generator
Mar 29 Last day to declare CR/NC (Mar 30)
10 Apr 03   Code shape, Chapter 7.7 - 7.11
Apr 05  
11 Apr 10   Instruction selection, Chapter 11 Project 3b: Complete Code Generator
Apr 12  
12 Apr 17   Code optimization, Chapter 8
Apr 19  
13 Apr 24   Register Allocation, Chapter 13 Project 4: Optimizations
Apr 26  
14 May 01   Student presentations on other topics
May 03  
  May 15 Final Exam 2-5pm