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|
Read Chapter 1 and Sections 2.1-2.6
|2||Jan 25||Lexical analysis, Regular expressions, FSMs
Review Section 2.6
Read Sections 3.1-3.4 and 3.6-3.9
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
|4||Feb 08||Bottom-up parsing
Read Sections 4.5-4.6
|Project 2a: LL(1) Grammar
|5||Feb 15||ASTs, Syntax-directed translation
Review Sections 2.3, 2.5
Read Sections 2.8, 5.1-5.3
|6||Feb 22||Symbol tables, Run-time environments
Read Sections 2.7, 7.1-7.3
|Project 2b: Recursive-Descent Parser Due 3/4|
|7||Mar 01||Procedures, Parameter passing
Review Sections 7.1-7.3
|9||Mar 22||Code generation
Review Section 2.8
Read Sections 8.1-8.3
|Project 3a: Code Generation
|Mar 24||Last day to declare CR/NC or W (Mar 25)|
|10||Mar 29||Code generation (continued)
Review Sections 8.1-8.3
Read Sections 8.4-8.8
|Project 3b: Code Generation
|12||Apr 12||Optimizations (continued)
Read Sections 9.1-9.2
|13||Apr 19||Automatic compiler construction tools
Read Sections 3.5 and 4.9
|Project 4: Optimizations
|14||Apr 26||Advanced topics|
Final Exam (2-5pm)