CS131: Programming Languages and Compilers. Fall 2018

LecturesTuesday and Thursday, 15:00--16:40, Room 1D 104 SIST Building
Instructors宋富 <songfu>
Office hoursRoom 1B-101 SIST Building
高鹏飞: Tuesday 19:30-20:30
秦琦: Friday 13:00-14:00
Q&APost all your questions on the forum.

Project assignments

Writing assignments

Optional Projects with Bonus

1.Compiler Testing

2.Compile real programs into floating-point programs with controllable round errors

3.Self-selected related projects

At most 3 students for each team. Each team has to submit: (1) A report that clearly describe the background, your design thoughts, the specific realization and the testing results, (2) Source code and a user guide, and (3) A final presentation to show what you have done

Submitting proposal of your optional project, due Oct. 31, 23:59

Week Date Topic Reading Notes
109-18 Introduction I CPUR 1 Slides
09-20 Introduction II & Lexical Analysis CPUR 1,3 Slides
209-25 Lexical Analysis CPUR 3 Slides
09-27 Slides
3 10-02 National Day
10-04 move to 09-29
4 10-09 Syntax Analysis CPUR 4 Slides1 Slides2
10-11 Slides
5 10-16 Slides
10-18 Slides
6 10-23 Slides
10-25 Slides
710-30 Intermediate Representation (IR) Slides1 Slides2
11-01 Midterm Review
811-06 Syntax-Directed Translation CPUR 5 Slides
11-08 Midterm
911-13 Syntax-Directed Translation Slides
11-15 Semantic Analysis and Type Checking CPUR 6.1-6.5, TypeSystems.pdf Slides
1011-20 Slides
11-22 Intermediate Code Generation CPUR 6.3-6.4, 6.6-6.9 Slides
1111-27 Operational Semantics COOL manual, SA 1-3,5-6 Slides
11-29 Run-time Environments CPUR 7.1-7.4 Slides
1212-04 Code Generation CPUR 8 Slides
12-06 Slides
1312-11 Slides
12-13 Garbage Collection CPUR 7.5-7.8 Slides
1412-18 Optimization Slides
12-20 Dataflow Analysis Slides
1512-25 Slides
12-27 Control Hijacking Attack Slides
1601-01 New Year's Day
01-03 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
Getting Started with LLVM Core Libraries


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.