Computer_Science
 Home | People | Curriculum | Projects | Resources | Media

CMSC 350b: Compiler Design

Instructor: David Wonnacott

Semester & Year: Spring Semester of even years (e.g., S '16)

Schedule: as posted in the course guide

Prerequisites: CMSC 245 Concurrent enrollment in this and two other CMSC lab courses requires permission of the instructor.

Texts:

Other Resources:

Description: An introduction to compiler design. Students undertake a semester-long laboratory project, building a compiler to turn Andrew Appel's "Tiger" language into an equivalent HERA assembly language program that can then be executed on the HERA-C simulator or assembled using the Hassem assembler and run on (simulated) HERA microprocessors created in CMSC 240. Lectures combine practical topics such as the use of compiler construction tools and techniques with more abstract discussions of the algorithms upon which these tools are based and discussions of techniques that are beyond the scope of our one-semester lab project.

This course covers the classic steps of compilation, specifically

In so doing, it also serves as a vehicle for several advanced topics in the design, analysis, and use of algorithms and data structures:

Requirements: Midterm and Final exam, the lab project, "mini-homework" assignments and other class participation.

Late Submission of Work: The lab work for this course is cumulative, and getting behind on one can cause a "cascade of lateness" that can leave an insurmountable amount of work for the end of the semester. While most of the lab credit will be based on having a complete, working compiler at the end of the semester, weekly lab review meetings will be used to assign class participation points (based in part on timely completion and git push'ing of milestone goals), and to provide feedback.

Collaboration: You are encouraged to discuss the lecture material and the weekly labs and "mini-homework" problems with other students, subject to the following restriction: for the lab, the only "product" of your discussion should be your memory of it - you may not write up solutions together, or exchange written work or computer files. Unlimited collaboration is allowed on "mini-homework" assignments, which may be written up jointly. Collaboration is not allowed on exams.

Lab Work: Lab 1: Write a Compiler is due at the end of the semester, but "class participation" credit is based, in part, on timely progress.

Note that this project is similar to the classic "write a compiler" lab in its scope, though with somewhat more emphasis on software engineering and less on compile-time optimization. For example, we spend significant time discussing and comparing approaches to creating trees with varied but definite structure, and approaches to performing operations on those nodes (e.g. via ad-hoc traversal algorithms as in Appel's C code, techniques for using inheritance to organize such traversals, the visitor pattern, aspect-oriented programming, and lazy evaluation). We leave topics such as tile-based instruction selection, data-flow analysis, and graph-coloring-based register allocation for homework and on exams.

Additionally, since about 2014, our the lab has differed substantially in structure from the classic approach, e.g. as assigned in Appel's textbook. Instead of moving through compiler stages such as lexical analysis, parsing, AST construction, symbol table construction, etc., our milestones move through language features, producing first a complete compiler for arithmetic expressions and integer constants, then for function calls and strings, then for control-flow expressions, etc. The above lab assignment makes use of C++ files designed to work with Appel's textbook. Anyone outside of Haverford who is interested in these files, or planning to use Appel's book with C++, is encouraged to contact davew.

Mini-homework assignments:

Mini-homeworks will be assigned regularly to review or prepare for a given class. The mini-homework assigments will be posted on Moodle as they are relevant.

Haverford College Page maintained by John Dougherty, David Wonnacott, and Rachel Heaton.
Computer Science Department, Haverford College.