CS131: Programming Languages and Compilers. Spring 2018

LecturesTuesday and Thursday, 8:15--9:55, Room 1D 106 SIST Building
DiscussionsSaturday, 15:00-16:30, Room 1D 106 SIST Building
Instructors宋富 <songfu>
Office hours 1B-101, SIST Building
高鹏飞: Wednesday, 20:00-21:30
秦琦: Friday, 14:00-15:30.
Q&APost all your questions on the forum.

Project assignments

PA1: Due March 20, 2018 at 11:59pm Handin: https://q71998.cn Description, Source-code

PA2: Due April 10, 2018 at 11:59pm Handin: https://q71998.cn Description, Source-code

PA3: Due May 8, 2018 at 11:59pm Handin: https://q71998.cnDescription, Source-code

PA4: Due June 14, 2018 at 11:59pm Handin: https://q71998.cnDescription, Source-code

Writing assignments

WA1: Assignment, Latex templete

WA2: Assignment, Latex templete

WA3: Assignment, Latex templete

WA4: Assignment, Latex templete

Optional Projects with Bonus

1.Compiler Testing

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

3.Self-selected related projects

You have 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 04-24, 23:59

Week Date Topic Reading Notes
102-27 Introduction I CPUR 1 Slides
03-01 Introduction II & Lexical Analysis CPUR 1,3 Slides
203-06 Lexical Analysis CPUR 3
03-15 Syntax Analysis CPUR 4 Slides
04-05 Tomb Sweeping Day
704-10 Intermediate Representation (IR) Slides
04-12 Syntax-Directed Translation CPUR 5 Slides
804-17 Midterm
04-19 Syntax-Directed Translation
904-24 Semantic Analysis and Type Checking CPUR 6.1-6.5, TypeSystems.pdf Slides
10 05-01 Labor Day
05-03 Intermediate Code Generation CPUR 6.3-6.4, 6.6-6.9 Slides
05-05 Tools and Design by Youmi Ma LLVM 3
05-10 Run-time Environments CPUR 7.1-7.4 Slides
05-12 Frontend by Dinghong Li LLVM 4
1205-15 Operational Semantics COOL manual,SA> 1-3,5-6 Slides
05-17 Code Generation CPUR 8 Slides
05-19 IR by Haocong Luo LLVM 5
05-26 Backend by Zhiqiang Xie LLVM 6
1405-29 Garbage Collection CPUR 7.5-7.8 Slides
05-31 Optimization Slides
06-02 JIT by Yuyang Rong LLVM 7
1506-05 Dataflow Analysis Slides
06-09 Static Analyzer by Jianxiong Cai LLVM 9
1606-12 Control Hijacking Attack Slides
06-14 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.