CPS 292.2 Compiler Construction : Fall 2011

This course will cover development of a compiler from start (lexical analysis) to finish (assembly output). We will cover basic optimizations and data flow anaylsis.

Contact information

Professor: Dr. Andrew (Drew) Hilton
Office Hours: Mon 3-4, Wed 2-3, or by appointment. LSRC D213
E-mail: adhilton@cs.duke.edu

TA: Asic Demberel
Office Hours: Tuesday 1-2, Thursday 2-3, or by appointment. LSRC D307
E-mail: asic@cs.duke.edu

Practice Final Exam

You can download a full length practice final exam and the solutions for it to help you study.

Practice Midterm Exam

You can download a full length practice exam and the soultions for it to help you prepare for your midterm exam.

Warmup SML Excercise

There is an ungraded warmup excercise here.
I encourage you to work together on it, ask me or your TAs for help and advice, etc.
The answers are posted here

A few SML resources:

One of your classmates sent me this link.
Olin Shivers has some intro to SML slides here
The SML basis library has documentation here

Note that sml, emacs sml-mode, ml-lex, and ml-yacc are all installed on linux.cs.duke.edu now. You can use them there if you do not want to install them on your own computer.

Project Notes

Turning in Projects

To turn in your project, e-mail them to your TA (asic@cs) and CC Drew (adhilton@cs).
Please make the subject line:
CPS296.2 Project X Turnin
Please be sure that you include the names of all group members in your submission.
Your project is due at midnight
.

Project 1: Lexer

You can find the project description in the section titled "Program: Lexical Analysis" at the end of Chapter 2 of the book.
Be sure to download the files Appel provides to start from. They can be found here.
Note 1: You can download them all as a tar from the link at the bottom of the page
Note 2: You will need to make three changes to "sources.cm" for it to work with the version of SML on linux.cs.duke.edu.

First, find the line that says "smlnj-lib.cm" and change it to read "$/smlnj-lib.cm" (that is, add $/ to the front).
Second, add a line that says "$/basis.cm" (right after the "$/smlnj-lib.cm" line is fine).
Third, replace the line that says "tiger.lex" with one that says
tiger.lex : shell (target: tiger.lex.sml ml-lex %s)

Once you have done those things, you should be able to run sml and type CM.make "sources.cm"; at the sml prompt to build the skeleton code.

Consult Appendix A for language reference as needed. You may omit the special handling of \^c in string literals.

Project 2: Parser

From Chapters 3 and 4 in your book

Project 3: Typechecker

From Chapter 5 in your book.

Feel free to add a BOTTOM type, and give break type BOTTOM, and exit type int -> BOTTOM
Feel free to modify the types, environment etc. I personally find it preferable to add an ARROW type for functions, and VarDec vs. FunDec distinction.
The book says that all cycles of a mutually recursive type definitions must pass through a record or array type. Feel free to require that they pass through a record type.
One point extra credit if you make your types purely functional. That is, there should be no refs (nor arrays) in your type data structure. This will involve deleting NAME completely and making RECORDs have a function type (i.e., ... -> ...).
If you want to make other improvements to your type system, please check with me first to be sure they are sound. As long as they are sound, I encourage you to add any cool features you might want.

Project 4: Frame Analysis and Translation to IR

From Chapters 6 and 7 in your book.

Project 5: Instruction Selection

From Chapter 9 of your book (note: chapter 8 done for you)

Extra credit for dynamic programming instead of Maximal Munch

Project 6: Liveness Analysis and Register Allocation

Chapter 10 and 11.

Minimum for full credit: allocate and spill (spilling can be simple/stupid).
Extra Credit: Heuristics for smart spilling
Extra Credit: Live range splitting
Extra Credit: Spill slot colloring
Extra Credit: Coallescing
Extra Credit (!!!!): Interprocedural Register Allocation

Wrapping it all up

Chapter 12. This contains the last little bits to make it all work.

Extra credit available for anything extra you want to add: optimizations, language features, etc. Ask me about whatever you have in mind.

Resources and Information

Olin Shivers teaches a similar course at Northeastern University. His course website has links to a variety of SML and SPIM resources.

Andrew Hilton

Last modified: Tue Nov 29 12:21:07 EST 2011