CS75: Principles of Compiler Design and Construction
Spring Semester, 2005
TTH 11:20am-12:35pm
Science Center 264

Professor: Tia Newhall
Office hours: 2:30-3:30 Wed, 4-5 Thurs
Office: 249 Science Center
Phone: 690-5637


Final Exam 2-5pm May 12th in SCI 264

Exam Review Session Tues, May 10 5:30-6:30 in the CS Lab


Course Description
Programming Projects
Schedule (Topics, Readings, Assignments)
On-line Resources

Course Description

CS75 is and 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 actually write a compiler for a non-trivial subset of the C programming language.

Required Course Text


20% midterm exam
20% final exam
50% project
10% homework and class participation

Programming Projects

The course project consists of three parts that together implement a compiler for most of the C programming language. You will work with a partner on the project assignments.

All programming projects will be in the C programming language. There are several C language references in the CS Lab that you may use. If you want to buy your own C language reference, here are two recommendations:

Late Work Policy

Collaboration Tools

Since programming projects will be done with a partner, you need to set up your development environment so that you and your partner can access your joint project files while still protecting them from others. In addition, I recommend using some type of revision control software to help you coordinate shared accesses to project files by you and your partner and to allow a way for you to back-up working versions of your code. I'd recommend using CVS. However, RCS is also available on our systems. See the
On-line Resources section for more information about safely sharing code and using cvs.

Academic Integrity

Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes sharing solutions after the due date of the assignment. Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. If you are in doubt about some help that you received, then credit the person(s) from whom you got help by citing them in a comment at the top of the file and discuss the situation with your instructor.

Tentative Schedule

The following schedule is tentative; it will be updated as we go along.

I highly recommend at least skimming through the week's reading prior to the first class meeting of that week.

week 1 (1/17) Overview Chapter 1, 2.1-2.2
week 2 (1/24) Lexical Analysis, Regular Expressions, FSMs Chapter 2.6, 3.1-3.4, 3.6-3.7
week 3 (1/31) Lexical Analysis
Intro to Parsing, CFG
Chapter 3.6-3.7, 2.4
Project part1
week 4 (2/7) Top-Down Parsing, LL(1) grammers
Thursday's class in the CS Lab (room 240)
Chapter 2.4, 4.1-4.3
week 5 (2/14) Top-Down Parsing
part 1 checkpoint due Tues 2/15
Chapter 4.1-4.4
week 6 (2/21) Parsing, Error Recovery, Syntax Directed Translation
part 1 due Tues 2/22
no class Thursday, 2/24
Office hours this week: Tues 4-5pm, Wed 1-2pm
Project part2
week 7 (2/28) Syntax Directed Translation, ASTs
Symbol Table
Chapter 2.3, 5.1, 7.6
***** Spring Break *****
week 8 (3/14) Run-time Environments and Symbol Table
part 2 checkpoint due, Thurs 3/17
Midterm, Thursday in class
Chapter 7.1-7.6
week 9 (3/21) Parameter Passing, variable access --
week 10 (3/28) Code Generation
part 2 due Tues 3/29
Project part3: code generation basic functionality
week 11 (4/4) Code Generation --
week 12 (4/11) Bottom-up Parsing, LR grammers Chapter 4.5, 4.7 up to page 221
Project part4: complete C-- compiler
week 13 (4/18) Bottom-up Parsing, SLR(1) parse tables, a.out files Chapter 4.7 to page 229
week 14 (4/25) Compiler Optimization --
finals week Final Exam May 12, 2-5pm, SCI 264 -- --

On-line Resources

Unix and C help

  • cs75handin
  • Compiling, Linking and Debugging Tips for C, gdb, ddd, valgrind, make, ...
  • C Code Style Guide Read this early and often.

  • CS Deptpartment's Unix Help Pages
  • My Unix Documentation make, tar, cvs, rcs, debugging tools, editors, email, sharing files, C style guide, ...
  • Recovering Lost Files What to do if you accidentally delete a file

    Collaboration Tools

  • Using Revision Controll Software cvs and rcs
  • Safe File Sharing for Group Projects