CSU665 Compilers (4 SH)

Studies the construction of compilers and integrates material from earlier courses in programming languages, automata theory, computer architecture, and software design. Examines syntax trees; static semantics; type checking; typical machine architectures and their software structures; code generation; lexical analysis; and parsing techniques. Uses a hands-on approach with a substantial term project.

CSU380, CSU660

There are many good textbooks for this course, including: Aho, Sethi, and Ullman. Compilers: Principles, Techniques, and Tools. Addison Wesley, 1986. Andrew Appel. Modern Compiler Implementation in Java, Second Edition, Cambridge University Press. (Also available: "in ML", "in C".) Charles Fischer, Richard LeBlanc, and Ron Cytron. Crafting a Compiler. Addison-Wesley.

Semantic analysis abstract syntax trees simple type checking scope of declarations lexical addresses Machine architecture from the compiler's perspective run-time structures expressed values environments, closures, objects continuations procedure calls registers runtime invariants instruction sets Code generation values and extent garbage collection instruction selection register allocation major optimizations assembly Construction of lexical analyzers regular expressions nondeterministic finite automata deterministic finite automata minimal deterministic finite automata Construction of efficient parsers LL or LR grammars deterministic top-down or bottom-up parsing syntax-directed translation construction of abstract syntax trees error recovery

Upon completion of this course, a student should have written a substantial portion of a compiler for a simple programming language understand the abstract syntax tree representation of programs understand at least one technique for expressing the scope and typing rules of a programming language understand the use of lexical addresses to generate code that refers to variables be able to write a code generator for a simple programming language be able to convert regular expressions into deterministic finite automata that recognize the generated language understand either LL or LR parsing well enough to write, from scratch, an efficient parser for the language generated by a simple LL(1) grammar

The course outcomes will be measured and verified by: Course project: a complete compiler for a small language The instructor should provide enough design, structure, and code for students to complete this project successfully. It is recommended that the project be broken up into three to five programming assignments. Possibilities include: abstract data type (ADT) of abstract syntax trees (ASTs) ADTs for symbols and compile-time environments lexical analyzer parser type checker static attribution of details needed for code generation (e.g. lexical addresses, record sizes, field offsets, tail calls) code generator assembler garbage collector It is recommended that the early assignments be graded by reading the code in addition to executing it. Midterm exam (optional at discretion of instructor) Final exam (optional at discretion of instructor) Electronic portfolio (optional at discretion of instructor)

CS U665 is an elective course that traditionally has been taken by juniors and seniors who are unusually good at programming and often have some industrial programming experience. The compiler project builds on their programming experience, and the course as a whole explains some of the mysterious things that students have witnessed while using compilers. After building a complete compiler, students are well-prepared to accept responsibility for significant programming tasks.

Omitted. Note: CS U665 has been mentioned as one model for a proposed "capstone" course in our curricula.