CS75/Engr23 Compilers
Spring 2011

Schedule | Grading | Project Policy

Class Information

Class: Tuesday, Thursday 2:40–3:55pm, SCI 181/240
Lab: Friday 3:30–5:00, SCI 252
Professor: Lisa Meeden
Office: Science Center 243
Phone: 8565
Office hours: Wednesdays 2-4pm, or you can stop by whenever my door is open.

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.

Required Textbook


05% Class participation
10% Project 1: Lexical Analyzer
20% Project 2: Parser
20% Project 3: Code Generator
10% Project 4: Code Optimizer

15% Midterm Exam: In class, March 17
20% Final Exam: May 10, 2-5pm

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 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 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)