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.
- 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.
- Required Text
Crafting a Compiler (2009 edition), by C. N. Fischer, R. K. Cytron, and R. J. LeBlanc. Addison-Wesley, 2009.
- There are earlier editions of this text, but they are almost 25 years old, and I don't recommend using them. The current edition offers some substantial changes over the older versions.
- Optional Resources
Modern Compiler Implementation in Java (2e) , by A. Appel. Cambridge University Press, 2002.
- 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
Format of the Course
- 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.
Relative weights for your final grade are as follows
- Project components: 65%
- Participation/Preparation: 15%
- Final Project: 20%
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).
- Instructor: John Lasseter
- Office:Lansing 300
- Office Hours: MW 12:30 - 1:30, Th 1:00 - 3:00, F 9:30 - 10:30 or by appointment (or just drop by)
- Phone: (315) 781-4652
- E-mail: email@example.com
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.