Home | Calendar | Assignments

Vital Stats

John Lasseter

lasseter@lasseter.edu

Class time—MWF 3:00 - 3:55 (Gulick 208b), Th 3:05 - 4:30 (Rosenberg 009)

Contact

lasseter@hws.edu

(315)781-4652

Lansing 300

Office Hours

M 9:30 - 10:30

W 9:30 - 11:00

Th 1:00 - 2:55

or by appointment (or just drop by)

Introduction

This course will immerse you in the fundamental tasks behind the construction of a compiler. Compiler design is one of the oldest fields in computer science, and it is among the best-developed. Though targeted to a highly specific application—the translation a high-level source code implementation into a machine-executable program—compiler construction draws from an extraordinarily wide range of fields. There are few other systems that involve such a satisfying mix of theory, software architecture, operating systems, and language design.

In this course, you will learn the following:

Lexing/Parsing. Language translation begins by verifying that the high level source code conforms to the syntax rules for the language, then translating the source code into a tree-structured intermediate representation. We will study the theory underlying the definition of a language's syntax, we will learn how to implement the compiler components responsible for lexical analysis and parsing, and we will learn how to formulate syntax definitions as specifications that are used to automatically generate these components

Semantic Analysis. Many programming languages have rules that cannot be checked through syntax analysis alone. In particular, languages with static type systems generally require an additional pass over the syntax tree to verify that the program is not only syntactically correct but also well-typed.

Code Generation. Once we have verified that the source code to be translated is a syntactically and semantically valid program, we must translate it to another language. This target language is usually the native assembly code for some microprocessor, but it may also be instructions for a virtual machine (such as the JVM or .NET), or even another high-level programming language.

Optimization. A production compiler can usually discover transformations of the source program (at various levels of representation) that improve execution in some way: faster, less memory, less power consumption, etc. However, such transformations must be correct, in the sense that the optimized and unoptimized programs have the same behavior. Time permitting, we will study the analysis techniques that underlie such transformations.

Prerequisites
In addition to a solid foundation in programming, this course assumes a basic knowledge of data structures, machine organization, and automata theory. Experience with algorithms, discrete mathematics, and programming language design is helpful, but not essential.

Resources

Required Text
Engineering a Compiler (2nd edition), by K.D. Cooper and L. Torczon. Morgan-Kaufmann, 2012.
Optional Resources
Modern Compiler Implementation in Java (1st ed.) , by A. Appel. Cambridge University Press, 1998.
This is a terrific textbook, in some ways the clearest one I've ever seen. The first edition introduced the Tiger language, which we use as the basis of our study in this class. Both the first and second editions are excellent, though Tiger was replaced in the second edition with a much simpler language.
There are also versions of this text in C and Standard ML.
CPSC 433 Web Page
http://math.hws.edu/lasseter/teaching/S16/CPSC433/

Format of the Course

Participation and Preparation
Each class will be a mix of lecture time, discussion and clarification of readings, and group problem-solving. In advance of each class, you will be assigned reading and occasionally also problem sets. You will be expected to have completed these by the following class, in order to participate effectively.
Project
The center of this course is the soup to nuts construction of a compiler. This will occur over the course of several staged projects and a few exercises, each of which will contribute a portion of the final project grade.
Exams
There are no exams in this course, though there is a Final Project, which you will present to the class at our scheduled exam meeting time (Sunday May 11, from 1:30 - 4:30).

Policies

Attendance

To receive full credit, I expect your attendance at every class, on time, having completed any assigned preparatory work. Such preparation is essential, both to your own success and that of the larger classroom community.

You may take up to 2 unexcused absences. Each absence after that will cost 5% of your final grade, up to the maximum 15% participation component (see "Grading", below).

Late Policy
All homework comes with a due date, but if I haven't started grading the assignment yet, I'll still accept late work. Once graded and returned, I won't accept it.
One exception is work whose submission and presentation is a part of class time (and therefore vital to the class). Such assignments will be clearly identified, and late submissions will receive no credit.
That being said, do not get behind on the assignments. The material in this course is challenging, and the pace at times will be intense: if you let yourself get behind, you will be overwhelmed. If you are having trouble, please ask for my help, as early as possible.
Students with Disabilities:
Students with documented disabilities who may need accomodations, who have any emergency medical information an instructor should know of, or who require special arrangements in the event of an evacuation, should contact me as early as possible, preferably no later than the first week of classes.
Academic Honesty:

All students are expected to adhere to the college policy on academic honesty. I take this very seriously: a breach of academic honor will result in a failing grade for the course, and may be subject to further college sanctions.

Grading

Relative weights for your final grade are as follows

  • Project components: 65%
  • Participation/Preparation: 15%
  • Final Project: 20%

Contact

The best way by far to get in touch with me is in person, during office hours. Any kind of class-related discussion is encouraged, whether it be a specific question about a homework problem, a request for encouragement and help getting started on an assignment, a point of confusion about the reading, or just plain curiousity about some of the further scientific directions that are possible. I am often available outside of office hours to answer questions, offer further explanation, or just to shoot the breeze. I am always available during posted hours. I encourage you to drop by.

Barring that, your best bet is by email, which I check late, early, and often. In fact, email is very often the most effective way for you to ask a question, as the effort involved in articulating what you want to ask can help clarify many things. It also makes it easier for me to give succinct replies to which you can refer later.

Phone calls are, frankly, lousy. You're certainly invited to call, but it's difficult to communicate technical questions and answers clearly without reading or writing down anything. Phone messages are completely futile: don't bother.

^ TOP