IndexAnnouncements
Instructor Contact Info
Course Description
Course Textbooks
Lab Sessions
Course Policies
Course Mailing List
Course Schedule
Course Homework Exercises
Additional Useful Links
Programming in SML
Course FAQ
SML FAQ
Announcements/Updates
- The first class will be on March 31, 2003 at 10:30am in Ry 251.
Instructor Contact Info
Name Role Office Office hours Phone David MacQueen Professor Ryerson 256 by arrangement 2-4980 macqueen@cs.uchicago.edu Kenneth Harris TA Ryerson ??? ??? ??? kaharris@cs.uchicago.edu Chunyan Song TA Mac Lab Tue 2:00pm - 4:00pm or by appointment - cysong@cs.uchicago.edu Course Description
This course covers principles of modern compiler design and implementation. Topics include lexical analysis, parsing, type systems, code generation, and optimization. This is a project oriented course in which students will construct a fully working compiler, using Standard ML as the implementation language.Students should be familar with topics from algorithms, programming languages, computer achitecture, and programming in Unix. Knowledge of CS280 will also be useful, but is not strictly required.
Course Textbooks
The main textbook for the course is: Modern Compiler Implementation in ML by Andrew Appel. Another classic text on compilers is Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman (commonly known as the Dragon Book). Two copies of this text are on 24 hour reserve in the Eckhart library. The Dragon book has extensive coverage of lexers and parsers (about 300 pages) for those who want to dig deeper into these topics.The course programming language is Standard ML, which is covered in the supplementary textbook ML for the Working Programmer by Lawrence C. Paulson.
Lab Sessions
Supervised lab sessions will be held each Monday from 5pm to 8pm in the Mac Lab in the basement of Regenstein library. These will provide opportunities for individual consultation and short tutorials relating to the programming projects and the tools used in the course (SML/NJ, CM, ML-Lex, ML-Yacc).Course Policies
- Grading will be based on the following:
- Programming projects: 60%
- Written exercises and final exam: 40%
- Assigments: Assignments are due at the beginning of class the following Wednesday.
- Collaboration: As in most courses, we encourage students to discuss course material among themselves. Discussions of assignment problems is also permitted to an extent, but submitted assignments should be your own work, and collaborative discussions should be acknowledged.
- Final Examination Date: 6/11/2003, 10:30-12:30
Course Mailing List
A mailing list has been created for the course. The address is cs22600-1@cs.uchicago.edu. The web page for the mailing list is at http://mailman.cs.uchicago.edu/mailman/listinfo/cs22600-1.Course Schedule
Here is a tenative schedule of the lectures. This is subject to midcourse adjustment, of course.
Lecture Date Topic Reading Slides Code 1 3/31 Introduction, overview, administration, SML tutorial Appel, Chpt 1; Paulson, Chpts 1,2 lecture1.pdf chap1.tgz 2 4/2 Regular Expressions; SML and SML/NJ Appel 2.1-2.2; Paulson 3,4 lecture2.pdf 3 4/4 Finite Automata Appel 2.3-2.4; Paulson 5,7 chap2.tgz 4 4/7 NFAs and DFAs Appel 2.3-4; Paulson 7,8 Lab 1 4/7 Lab session 1: SML and SML/NJ; CVS Paulson 1,2,3,4 5 4/9 ML Lex; SML Tutorial continued Appel 2.5; Paulson 7; ML-Lex Manual SML2.pdf 6 4/11 Parsing; Context Free Grammars Appel 3.1; Paulson 8 lecture3.pdf 7 4/14 Recursive Descent Parsing Appel 3.2-3.3 Lab 2 4/14 ML-Lex; ML-Yacc; SML; CM Paulson 5,7,8 8 4/16 Bottom up parsing, LR0 grammars; Yacc Appel 3.3; ML-Yacc Manual lecture4.pdf chap3.tgz 9 4/18 LR0 grammars; Yacc Appel 3.4-5 10 4/21 Tiger Language; Abstract Syntax Appel 4; Appendix chap4.tgz Lab 3 4/21 ML-Yacc; Tiger grammar ML-Yacc Manual 11 4/23 Abstract Syntax; Symbol Tables Appel 5.1-5.3 12 4/25 Type Checking Appel 5.4 lecture5.pdf chap5.tgz 13 4/28 Stack Frames Appel 6 Lab 4 4/28 Type checking 14 4/30 Type checking 15 5/2 Frames and Escaping Variables Appel 6 lecture6.pdf chap6.tgz 16 5/5 Frames and Escaping Variables Appel 6 Lab 5 5/5 Frames and Escaping Variables Appel 6 17 5/7 Intermediate Trees Appel 7.1 lecture7.pdf chap7.tgz 18 5/9 Translation to IR Trees Appel 7.2-3 19 5/12 Translation to IR Trees Appel 10 Lab 6 5/12 Trees; Instr. selection 20 5/14 Basic Blocks and Traces Appel 8 lecture8.pdf 21 5/16 Instruction Selection Appel 9 lecture9.pdf 22 5/19 Instruction Selection Appel 9 Lab 7 5/19 Instruction Sel., Liveness 23 5/21 Liveness Appel 10 lecture10.pdf 24 5/23 Register Allocation Appel 11.1 lecture11.pdf 25 5/26 Register Allocation Appel 11.2-3 Lab 8 5/26 Register Allocation, Integration 26 5/28 Register Allocation Appel 11.4-5 27 5/30 Compiler Integration Appel 12 28 6/2 Compiler Integration Appel 12 Lab 9 6/2 Integration and testing 29 6/4 Summary and Review lecture12.pdf
Additional Useful Links
- Documentation and software for Standard ML of New Jersey (SML/NJ) are available at http://www.smlnj.org/.
- The Standard ML Basis Library Manual
- A Compact Guide to Lex and Yacc.
- Tiger compiler modules for the programming exercises (we will provide revised versions of these throughout the course).
- Appel's collection of test cases.
- The spim MIPS emulator.
- Some usefule Class Notes on the MIPS architecture.
- Appendix A from Hennessy and Patterson's Computer Organization and Design: The Hardware/Software Interface, which covers the MIPS architecture and the SPIM simulator.
- The SPIM Reference Manual, including a description of the MIPS assembly language.
- A MIPS Instruction Summary.