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.
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 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.
| WEEK | DAY | ANNOUNCEMENTS | TOPIC & READING | LABS |
| 1 | Jan 18 | Introduction Read Chapter 1 and Sections 2.1-2.6 |
||
| Jan 20 | ||||
| 2 | Jan 25 | Lexical analysis, Regular expressions, FSMs Review Section 2.6 Read Sections 3.1-3.4 and 3.6-3.9 |
C-- Grammar Project 1: Scanner Parts 1-3 Due 1/31 Part 4 Due 2/7 |
|
| Jan 27 | Drop/Add ends (Jan 28) | |||
| 3 | Feb 01 | Top-down parsing Review Sections 2.2, 2.4 Read Sections 4.1-4.4 |
||
| Feb 03 | ||||
| 4 | Feb 08 | Bottom-up parsing Read Sections 4.5-4.6 |
Project 2a: LL(1) Grammar Due 2/18 |
|
| Feb 10 | ||||
| 5 | Feb 15 | ASTs, Syntax-directed translation Review Sections 2.3, 2.5 Read Sections 2.8, 5.1-5.3 |
||
| Feb 17 | ||||
| 6 | Feb 22 | Symbol tables, Run-time environments Read Sections 2.7, 7.1-7.3 |
Project 2b: Recursive-Descent Parser Due 3/4 | |
| Feb 24 | ||||
| 7 | Mar 01 | Procedures, Parameter passing Review Sections 7.1-7.3 |
||
| Mar 03 | ||||
Mar 08 |
Spring Break |
|||
Mar 10 |
||||
| 8 | Mar 15 | Review | ||
Mar 17 |
Midterm Exam |
|||
| 9 | Mar 22 | Code generation Review Section 2.8 Read Sections 8.1-8.3 |
Project 3a: Code Generation Due 4/4 |
|
| Mar 24 | Last day to declare CR/NC or W (Mar 25) | |||
| 10 | Mar 29 | Code generation (continued) Review Sections 8.1-8.3 |
||
| Mar 31 | ||||
| 11 | Apr 05 | Optimizations Read Sections 8.4-8.8 |
Project 3b: Code Generation Due 4/18 |
|
| Apr 07 | ||||
| 12 | Apr 12 | Optimizations (continued) Read Sections 9.1-9.2 |
||
| Apr 14 | ||||
| 13 | Apr 19 | Automatic compiler construction tools Read Sections 3.5 and 4.9 |
Project 4: Optimizations Due 5/2 |
|
| Apr 21 | ||||
| 14 | Apr 26 | Advanced topics | ||
| Apr 28 | ||||
May 10 |
Final Exam (2-5pm) |
|||