CS131: Programming Languages and Compilers

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

Schedule
Week	Date	Topic	Reading	Notes
1	02-27	Introduction I	CPUR 1	Slides
1	03-01	Introduction II & Lexical Analysis	CPUR 1,3	Slides
2	03-06	Lexical Analysis	CPUR 3
2	03-08
3	03-13
3	03-15	Syntax Analysis	CPUR 4	Slides
4	03-20
4	03-22
5	03-27
5	03-29
6	04-03
6	04-05	Tomb Sweeping Day
7	04-10	Intermediate Representation (IR)		Slides
7	04-12	Syntax-Directed Translation	CPUR 5	Slides
8	04-17	Midterm
8	04-19	Syntax-Directed Translation
9	04-24	Semantic Analysis and Type Checking	CPUR 6.1-6.5, TypeSystems.pdf	Slides
9	04-26
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
11	05-08
	05-10	Run-time Environments	CPUR 7.1-7.4	Slides
	05-12	Frontend by Dinghong Li	LLVM 4
12	05-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
13	05-22
	05-24
	05-26	Backend by Zhiqiang Xie	LLVM 6
14	05-29	Garbage Collection	CPUR 7.5-7.8	Slides
	05-31	Optimization		Slides
	06-02	JIT by Yuyang Rong	LLVM 7
15	06-05	Dataflow Analysis		Slides
	06-07
	06-09	Static Analyzer by Jianxiong Cai	LLVM 9
16	06-12	Control Hijacking Attack		Slides
16	06-14	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
LLVM: Getting Started with LLVM Core Libraries

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):

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.