CMSC 226/326: Compilers for Computer Languages

Spring Quarter, 2003 
Monday, Wednesdays and Fridays, 10:30 - 11:20 am
Ryerson 251


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


Instructor Contact Info

Name Role Office Office hours Phone Email
David MacQueen Professor Ryerson 256 by arrangement 2-4980
Kenneth Harris TA Ryerson ??? ??? ???
Chunyan Song TA Mac Lab Tue 2:00pm - 4:00pm or by appointment -

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

Course Mailing List

A mailing list has been created for the course. The address is The web page for the mailing list is at

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

Dave MacQueen
Last modified: Wed Jun 4 13:35:06 CDT 2003