CS4410/6410: Compilers

Fall 2025

Contact information

Lectures

Other

Course schedule (lectures, projects, exams) (This is the central file for course-related information.)

Piazza: https://piazza.com/northeastern/fall2025/cs44106410

Assignments

1. Lexer (due Wed 9/17 midnight)

Resources

Books

• The course textbook is Modern Compiler Implementation in ML, by Andrew Appel. Try to get the edition that says "Reprinted with corrections, 1999" on page iv; previous editions had lots of errors. (This is, of course, not an issue today unless you're buying a very old, used copy.) You can order the book from Barnes & Noble or Amazon.

  Appel's text comes in multiple versions: one for C, Java and ML. Make sure you get the ML version.

  Appel maintains a web page for the text book, which includes various files to begin your compiler with, and a a list of errata for the different editions of the book. It will save you confusion later if you take 15 minutes and go through the errata, applying them to your copy.

• If you are not an experienced SML programmer, then you will almost certainly need to get an introductory text on SML. I recommend Larry Paulson's ML for the Working Programmer.

  You can also find some useful tutorials on the Net. Several are listed below.

MIPS and SPIM

• James Larus's Assemblers, Linkers, and the SPIM simulator . This is Appendix B of Hennessy & Patterson's standard architecture textbook Computer Organization and Design: The Hardware/Software Interface, published by Morgan Kaufman. (It's appendix A of older versions of the book). It includes documentation on the MIPS R2000, its assembly code, and the SPIM simulator.
• SPIM documentation, in PostScript and PDF format. NOTE: the description of MIPS calling conventions in here is older than that in the Hennessy & Patterson book.
• The SPIM simulator runs on Windows, Macs and Linux. It has its own wikipedia page, which provides links to places you can obtain it. But most linux distros provide it as a package.
• Tiger Runtime System -- needed to actually run your programs.

ML

• Other ML tutorials
• Standard ML of New Jersey home page
• SML/NJ "Basis" Library documentation
• SML/NJ Library Manual
• User Manual for CM , an SML/NJ Configuration Manager
• User Manual for ML-Lex, a lexical analyzer generator for ML
• User Manual for ML-Yacc, a parser generator for ML
• You are strongly encouraged to develop and debug SML using emacs. In particular, emacs comes with two special modes: one for editting sml source code, and one for running an sml process inside emacs.

Improved Canonicaliser

Appel provides a module of code for the Tiger-compiler project called the "canonicaliser," which lowers a program in the IR language to a form closer to machine code. This code is hard to read, as the invariants of the lowered/canonicalised form are not expressed in the type of the result form. Well, and the code isn't commented, either.

I rewrote this code using a target data type that makes the new form explicit in the type structure. It is much clearer and type-driven (as well as voluminously commented). It also has a slightly better commutativity analysis.

The code comes in two forms. The first version is exactly as described above. Then I took that, and converted the improved code to use the original IR data type for the target, producing a version that is a drop-in replacement for Appel's code.

So, read the first version but use the second.