CS131: Programming Languages and Compilers. Spring 2017
| Lectures | Tuesday and Thursday, 8:15--9:55, Room 1D 106 SIST Building |
| Discussions | Thursday 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. |
| Discussions | Post 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
Schedule
| Week |
Date |
Topic |
Reading |
Notes |
|---|
| 1 | 02-14 |
Introduction I |
CPUR 1 |
Slides |
| 02-16 |
Introduction II & Lexical Analysis |
CPUR 1,3 |
Slides |
| 2 | 02-21 |
Lexical Analysis |
CPUR 3 |
Slides |
| 02-23 |
| 3 | 02-28 |
| 03-02 |
| 4 | 03-07 |
Syntax Analysis |
CPUR 4 |
Slides |
| 03-09 |
| 5 | 03-14 |
| 03-16 |
| 6 | 03-21 |
| 03-23 (08:15-09:55, 19:30-21:10) |
| 7 | 03-28 |
| 03-30 |
Syntax Analysis & Intermediate Representation (IR) |
|
Slides |
| 8 | 04-04 |
Tomb-sweeping Day |
|
|
| 04-06 |
Midterm Review |
|
Slides |
| 9 | 04-11 |
Midterm |
|
Solution |
| 04-13 |
Syntax-Directed Translation |
CPUR 5 |
Slides |
| 10 | 04-18 |
| 04-20 |
Semantic Analysis and Type Checking |
CPUR 6.1-6.5 |
Slides |
| 11 | 04-25 |
COOL Type Checking |
Type System |
|
| 04-27 |
| 12 | 05-02 |
Intermediate-Code Generation |
CPUR6.3-6.4, 6.6-6.9 |
Slides |
| 05-04 |
| 13 | 05-09 |
Run-time Environments |
CPUR 7 |
Slides |
| 05-11 |
Operational Semantics |
COOL manual, SA 1-3,5-6 |
Slides |
| 14 | 05-16 |
Code Generation |
CPUR 8 |
Slides |
| 05-18 |
| 15 | 05-23 |
| 05-25 |
Garbage Collection |
|
Slides |
| 16 | 05-30 |
Dragon Boat Festival |
|
|
| 06-01 |
Review |
|
|
Note: schedule is subject to change.
Description
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.
References
- CPUR
- Compilers: Principles, Techniques and Tools (2Ed.), by Aho, Lam, Sethi, and Ullman (ISBN-10: 0321486811)
- CCPP
- Compiler Construction Principles and Practice, by Kenneth C. Louden
- SA
- Semantics with Applications: An Appetizer, by Hanne Riis Nielson and Flemming Nielson
Requirements
- Reading
- 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
- COOL
- COOLAid: The Cool Reference Manual
- COOL examples
- A Tour of the Cool Support Code
- Cool Support Source Code
- Reference binaries
- Flex
- Bison
- SPIM Manual
Grading
Projects 30%+ Homework 20%+ Midterm 20% + Final 30% + Bonus 10%
Policies
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):
- Read or possess solution code written by other people.
- Submit to the gradebot code written by other people or derived from the code written by other people.
- Allow other people to read or possess your solution code either actively or passively, e.g., by posting your code on a web site or leaving the computer containing your code unattended and unlocked. You are responsible for exercising due diligence in safeguarding your code.
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.
Forum
You may not post anonymously. If you do, we will delete your post without notice and will deduct from your class participation score.
Feedback
We always welcome any feedback on what we could do better.
You are also welcome to send us feedback anonymously if you like.