CS131: Programming Languages and Compilers. Spring 2017

LecturesTuesday and Thursday, 8:15--9:55, Room 1D 106 SIST Building
DiscussionsThursday 19:00-20:30, Room 1A 104 SIST Building
Instructors宋富 <songfu>
Office hours 1A-108, SIST Building
张俊: Friday 13:30-15:30.
梅志明: Tuesday 15:00-17:00.
DiscussionsPost all your questions on the forum.

Project assignments

PA1: Description, Source-code

PA2: Description, Source-code

PA3: Description, Source-code

PA4: Description, Source-code

Writing assignments

WA1: Assignment, Latex templete

WA2: Assignment, Latex templete

WA3: Assignment, Latex templete

WA4: Assignment, Latex templete

Optional Projects

Compiler Testing: Description

Week Date Topic Reading Notes
102-14 Introduction I CPUR 1 Slides
02-16 Introduction II & Lexical Analysis CPUR 1,3 Slides
202-21 Lexical Analysis CPUR 3 Slides
403-07 Syntax Analysis CPUR 4 Slides
03-23 (08:15-09:55, 19:30-21:10)
03-30 Syntax Analysis & Intermediate Representation (IR) Slides
804-04 Tomb-sweeping Day
04-06 Midterm Review Slides
904-11 Midterm Solution
04-13 Syntax-Directed Translation CPUR 5 Slides
04-20 Semantic Analysis and Type Checking CPUR 6.1-6.5 Slides
1104-25 COOL Type Checking Type System
1205-02 Intermediate-Code Generation CPUR6.3-6.4, 6.6-6.9 Slides
1305-09 Run-time Environments CPUR 7 Slides
05-11 Operational Semantics COOL manual, SA 1-3,5-6 Slides
1405-16 Code Generation CPUR 8 Slides
05-25 Garbage Collection Slides
1605-30 Dragon Boat Festival
06-01 Review

Note: schedule is subject to change.


This course covers the fundamentals of compiler design, including lexical analysis, parsing, semantic analysis, compile-time memory organization, run-time memory organization, code generation, and compiler portability issues.


Compilers: Principles, Techniques and Tools (2Ed.), by Aho, Lam, Sethi, and Ullman (ISBN-10: 0321486811)
Compiler Construction Principles and Practice, by Kenneth C. Louden
Semantics with Applications: An Appetizer, by Hanne Riis Nielson and Flemming Nielson


Read the chapters before every class. We will not read the textbook to you but I will help you better understand certain materials in the textbook.

Reading material

Formal Language and automata
Chomsky hierarchy wikipedia. A high level view of formal languages
Handbook of Formal Languages: more details on formal languages, and related logics and automata 1 2 3. Chapters for Reading: Volume 1, Chapters 1-3; Volume 2, Chapter 9; Volume 3,Chapter 6-7. Other chapters are optional.
Symbolic automata: An extension of finite state automata, providing a way to compactly representing regular languages over infinite alphabet.
Symbolic automata materials Papers for Reading: Applications of Symbolic Finite Automata by M. Veanes CIAA13 and Symbolic Finite State Transducers: Algorithms and Applications by N, Bjorner, P. Hooimeijer, B. Livshits, D. Molnar, M. Veanes, POPL12. Other papers are optional.
Visibly Pushdown Languages/Automata: A formal language lie in regular language and context-free language, the model visibly pushdown automata lie in finite state automata and pushdown automata. But, visibly pushdown automata/languages have better closure properties than pushdown automata, i.e., closed under Boolean operations.
Visibly pushdown languages/automata materials Paper for Reading: Adding Nesting Structure to Words by Alur and Madhusudan, Journal of the ACM, 2009. Other papers are optional.

Project material

COOLAid: The Cool Reference Manual
COOL examples
A Tour of the Cool Support Code
Cool Support Source Code
Reference binaries
SPIM Manual


Projects 30%+ Homework 20%+ Midterm 20% + Final 30% + Bonus 10%


Academic integrity

We enforce academic integrity strictly. If you participate in any form of cheating, you will fail this course immediately. Examples of cheating on homework include (but are not limited to):

Late homework

We never accept late homework submission in any circumstances. Since we hand out homework several weeks before its deadline, you should allocate sufficient time and allow for contigencies.


You may not post anonymously. If you do, we will delete your post without notice and will deduct from your class participation score.


We always welcome any feedback on what we could do better. You are also welcome to send us feedback anonymously if you like.