CS 132: Compiler Design
Fall 2007

Announcements

• None right now.

References

• General
  • Reflections on Trusting Trust, Ken Thompson. 1983 Turing Award Lecture.
    


• Parsing
  • Parsing Techniques: A Practical Guide. Full text of an interesting (out-of-print) book covering parsing and context-free languages in depth.
  • Information on using parser generators specifically for Standard ML:
    • Official ml-lex manual (used for arith-LR.lex)
    • Official ml-yacc manual (used for arith-LR.grm)
    • A third-party Users Guide to ML-Lex and ML-Yacc
    • ml-ulex and ml-antlr manual (used for arith-LL.lex and arith-LL.grm)
    
    


• Register Allocation
  • Register Allocation & Spilling via Graph-Coloring, Chaitin.
• Improvements to Graph-Coloring Register Allocation, Briggs, Cooper, and Torczon.
• Iterated Register Coalescing, Appel and George.
• Quality and Speed in Linear-Scan Register Allocation, Traub, Holloway, and Smith.
  


• Intel IA32 (aka x86)
  • Intel's Official Documentation
  • A description of the calling convention used by GCC
  • More official documentation of the calling convention
  • Linux Assembly HOWTO


• Other
  • Jasmin assembler for the Java Virtual Machine bytecode
  • Warren's Abstract Machine: A Tutorial Reconstruction
    Describes the basic machinery used by most Prolog implementations.
  • Implementing Functional Languages: A Tutorial
    Describes the implementation of lazy functional languages (e.g., Haskell) using techniques derived from graph-reduction.


• Running Standard ML

  Generally the class will assume you are using version 110.65 of the Standard ML of New Jersey compiler, a free compiler developed at Bell Labs. This can be run on turing using the command sml, (or even better rlwrap sml, which makes the up and down arrow keys scroll through your command history), but if you'd rather use your own computer, you can download it for most operating systems, including Windows, Linux, and OS X.

  The CS 131 guide to using SML/NJ contains some very useful information on the mechanics of running the compiler, using it with emacs, and (perhaps most importantly) interpreting error messages.

  Because SML has an official definition, there are several other good, freely-available compilers available for the language that you may use instead, including Moscow ML (for many operating systems; it can also be run on turing via the command mosml), Poly/ML (for many operating systems) and MLton (for x86 machines). Each implementation has its own advantages.



• Learning Standard ML

  If you've done some SML programming in the past, the shortest way to get up to speed may be to read through the SML Overview for CS 131. This is meant to summarize the minimum knowledge about SML needed to do the programming for this class. As such, it is very condensed; if you find it too compressed then you might want to look elsewhere:

  • Robert Harper at Carnegie Mellon University has written a tutorial Programming in Standard ML (This is a rather long pdf file, so please don't send it to the college printers.) Chapter 1 jumps right into a relatively complex ML program; if this seems overwhelming you might go on to Chapter 2, which starts back at the beginning with a more introductory approach.
  • Andrew Cumming has written A Gentle Introduction to ML
  • There are several textbooks you can purchase on learning SML, including Jeffrey Ullman's Elements of ML Programming (ML97 Edition), Hansen and Rischel's Introduction to Programming Using SML, and Laurence Paulson's ML for the Working Programmer. Copies of all three books will be placed in the Terminal Room.

  Documentation for the Standard ML Basis (i.e., the standard library) is available on-line. Particularly useful are the modules Int, Real, String, and List, but there are many others as well.