Professor: Lisa Meeden
Course: Tuesdays and Thursdays 2:40-3:55, SCI L32
Email: meeden AT cs.swarthmore.edu
Office: SCI 243
Office hours: Wednesday 2-4pm, or by appointment
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.
Engineering A Compiler, Keith D. Cooper and Linda Torczon
Morgan Kaufmann Publishers (2004), ISBN 1-55860-698-X
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.
|1||Jan 23||Overview of compilation, Chapter 1
Translator for infix to postfix
|2||Jan 30||Scanning, Chapter 2||Project 1: Scanner
C-- Language Specification
|Feb 01||Last day to drop/add (Feb 02)|
|3||Feb 06||Top-down parsing, Chapter 3.1 - 3.3|
|4||Feb 13||Bottom-up parsing and Practical issues, Chapter 3.4, 3.6, 3.8||Project 2: Parser
Sample error handling
|5||Feb 20||Context-sensitive analysis, Chapter 4|
|6||Feb 27||Intermediate representations, Chapter 5|
|7||Mar 06||Procedure abstraction, Chapter 6.1 - 6.4|
|Mar 13||Spring Break|
|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|
|11||Apr 10||Instruction selection, Chapter 11||Project 3b: Complete Code Generator|
|12||Apr 17||Code optimization, Chapter 8|
|13||Apr 24||Register Allocation, Chapter 13||Project 4: Optimizations|
|14||May 01||Student presentations on other topics|
|May 15||Final Exam 2-5pm|