TDT4205 Compiler Construction (Spring 2021)


Grading

-- tba --


Discussions

We have enabled a forum on piazza to enable anonymous discussions and feedback. Interesting questions will be discussed in the upcoming Q&A sessions.

Timetable

Lectures will be running online until further notice, due to NTNU-wide Corona virus precautions.

Until the situation changes, we will run the course in flipped classroom style with lecture videos on youtube and two live sessions - an online exercise session on Fridays (14:15-16:00) to discuss the theoretical and practical exercises and an online Q&A session in the Monday lecture slot (17:15-18:00) on Zoom. Flipped classroom means that you are not bound to fixed lecture times but can watch the lecture videos whenever it fits best.

Weekday Time Location Type
Mon 17:15-18:00 Online Q&A session
Fri 14:15-16:00 Online Exercise discussion session


Lecture videos and additional material

youtube TDT4205 channel

MIT's "The Missing Semester of Your CS Education" with an introduction to the Unix shell, version control, makefiles etc.


Semester plan, slides and videos

Lecture slides and videos will be published twice a week (on Monday and Tuesday). Assignments for theoretical (TE) and practical (PE) exercises will be handed out weekly on Friays, alternating between theoretical and practical exercises. You have two weeks to hand in the solutions (Deadline is Friday 14:00).

The C crash course serves as an introduction to C for students who have only programmed in Java (or other languages) before. It is also useful as a refresher of your knowledge. This part is identical for the operating systems (TDT4186) and compilers (TDT4205) course.

Week Day Date Mode Topic PDF Video
2Mon11.01.2021 videoC "crash course" part 1 c-course.pdf video
Tue12.01.2021 videoC "crash course" part 2 video
Fri15.01.2021 Handout TE1 - C theory Compilers_TE1.pdf
3Mon18.01.2021 videoLecture 1: Motivation and History compilers01.pdf video 1
Mon18.01.2021 Welcome and Q&A session (17:15-18:00) qa01.pdf
Tue19.01.2021 videoLecture 2: Compiler structure, automata and scanning compilers02.pdf video 2.1 (structure)
video 2.2 (scanning)
How difficult is it to write a compiler? (additional material: blog) link
Fri22.01.2021 Handout PE1 - C practice Compilers_PE1.pdf (now with points!)
Fri22.01.2021 Moved to next week! Overview over the practical exercises
4Mon25.01.2021 Lecture 3: Scanner Generators compilers03.pdf video 3
Mon25.01.2021 Q&A session (17:15-18:00) qa02.pdf video
Tue26.01.2021 Lecture 4: Lexical analysis in the real world compilers04.pdf video 4.1 (DFA minimization)
video 4.2 (lex)
Fri29.01.2021 Deadline Handin TE1 (14:00)
Fri29.01.2021 Discussion session for TE1 (14:15-16:00) solution sheet
solution slides
Fri29.01.2021 Handout TE2 Compilers_TE2.pdf
5Mon01.02.2021 Lecture 5: Introduction to parsing compilers05.pdf video 5
Which parsing approach? (additional material: blog) link
Mon01.02.2021 Q&A session (17:15-18:00)
Tue02.02.2021 Lecture 6: Top-down parsing and LL(1) parser construction compilers06.pdf video 6.1 (parsing)
video 6.2 (recursive descent)
video 6.3 (LL(1) and table-driven parsing
Fri05.02.2021 Deadline Handin PE1 (14:00)
Fri05.02.2021 Discussion session for PE1 (14:15-16:00) pdf video
Fri05.02.2021 Handout PE2 - Hands-on with scanner generators Compilers_PE2.pdf
Compilers_PE2_skeleton.tar.gz
Compilers_PE2_testcases.tar.gz
6Mon08.02.2021 Lecture 7: Bottom-up parsing compilers07.pdf video 7
Mon08.02.2021 m Q&A session (17:15-18:00)
Tue09.02.2021 Lecture 8: LR(k) parsers compilers08.pdf video 8.1: LR1() DFA
video 8.2: LR(1) parsing
Fri12.02.2021 Deadline Handin TE2 (14:00)
Fri12.02.2021 Discussion session for TE2 (14:15-16:00) solution sheet PDF
slides PDF
video
Fri12.02.2021 Handout TE3 (Update: clarification of 3.1!) Compilers_TE3_v2.pdf
7Mon15.02.2021 Lecture 9: Practical parsing issues and yacc introduction compilers09.pdf video 9.1
video 9.2
Compiling is like skiing: the art of compiler architecture (video by Paul Kelly, Imperial College) video
Mon15.02.2021 Q&A session (17:15-18:00)
Tue16.02.2021 Lecture 10: Context-sensitive analysis compilers10.pdf video 10.1
video 10.2
Fri19.02.2021 Deadline Handin PE2 (14:00)
Fri19.02.2021 Discussion session for PE2 (14:15-16:00) pdf video
Fri19.02.2021 Handout PE3 - Parsing and VSL specification: grammar error and example programs fixed! Compilers_PE3_v3.pdf
PE3_skeleton_v2.zip
8Mon22.02.2021 Lecture 11: Type analysis and attribute grammars compilers11.pdf video 11
Mon22.02.2021 Q&A session (17:15-18:00)
Tue23.02.2021 Lecture 12: Intermediate representations and three-address code compilers12.pdf video 12
Fri26.02.2021 Deadline Handin TE3 (14:00)
Fri26.02.2021 ---- Discussion session for TE3 (14:15-16:00) moved to next week! moved!
Fri26.02.2021 Handout TE4 Compilers_TE4.pdf
9Mon01.03.2021 Lecture 13: Intermediate representations and Static Single Assignment compilers13.pdf video 13
Mon01.03.2021 zoom Q&A session (17:15-18:00) zoom
Tue02.03.2021 Lecture 14: The procedure abstraction compilers14.pdf video 14
Fri05.03.2021 Deadline Handin PE3 (14:00)
Fri05.03.2021 Discussion session for PE3 (14:15-16:00) TE3
PE3
video
Fri05.03.2021 Handout PE4 - Syntax tree simplification Compilers_PE4.pdf
PE4_skeleton.zip
10Mon08.03.2021 Lecture 15: Assembler and real world procedures compilers15.pdf video 15
Mon08.03.2021 Q&A session (17:15-18:00)
Tue09.03.2021 Lecture 16: Introduction to optimizations compilers16.pdf video 16
Fri12.03.2021 Deadline Handin TE4 (14:00)
Fri12.03.2021 Discussion session for TE4 (14:15-16:00) Next week!
Fri12.03.2021 Handout TE5 Compilers_TE5.pdf
11Mon15.03.2021 Lecture 17: Optimizations in detail: control-flow graphs compilers17.pdf video 17.1
video 17.2
Mon15.03.2021 Q&A session (17:15-18:00)
Tue16.03.2021 Lecture 18: Data-flow analysis framework compilers18.pdf video 18
Fri19.03.2021 Deadline Handin PE4 (14:00)
Fri19.03.2021 Discussion session for TE4 & PE4 pdf video
Fri19.03.2021 Handout PE5 - Symbol table construction Compilers_PE5.pdf
PE5: guidelines PDF
PE5: new skeleton files
PE5: sources and output files
PE5 new VSL examples
12Mon22.03.2021 Lecture 19: Data-flow and liveness analyses compilers19-1.pdf
compilers19-2.pdf
video 19.1
video 19.2
Mon22.03.2021 Q&A session: Guidelines for PE5 slides video
Tue23.03.2021 Lecture 20: Reaching definitions compilers20.pdf video 20
Fri26.03.2021 Deadline Handin TE5 (14:00)
Fri26.03.2021 Discussion session for TE5 (14:15-16:00) pdf video
Fri26.03.2021 Handout TE6 Compilers_TE6.pdf
13 🐰 Easter break – påskeferie 🐣
14Mon05.04.2021 🐰 Easter break – påskeferie 🐣
Tue06.04.2021 🐰 Easter break – påskeferie 🐣
Fri09.04.2021 Additional Q&A session for PE5 pdf video
15Mon12.04.2021 Lecture 21: Available expressions and very busy expressions analysis compilers21-1.pdf
compilers21-2.pdf
video 21.1
video 21.2
Mon12.04.2021 Q&A session No session today - new PE + guideline video on the 13.!
Mon12.04.2021 Deadline Handin PE5 (23:59)
Tue13.04.2021 Lecture 22: Code generation compilers22.pdf video 22
Tue13.04.2021 Handout PE6 - Code generation Compilers_PE6.pdf
PE6: guidelines PDF
PE6: new skeleton files
guidelines video
Fri16.04.2021 Deadline Handin TE6 (14:00)
Fri16.04.2021 Discussion session for TE6 (14:15-16:00)
Fri16.04.2021 Handout Example exam example exam 2020
solutions example exam 2020 (updated)
exam 2020
solutions exam 2020
16Mon19.04.2021 Lecture 23: Register allocation compilers23.pdf video 23
Mon19.04.2021 Q&A session (17:15-18:00)
Tue20.04.2021 Lecture 24: SSA generation and optimization compilers24.pdf
Fri23.04.2021 Discussion session for the exam preparation
17Mon26.04.2021 Semester summary compilers25.pdf zoom
Mon26.04.2021 Deadline Handin PE6 (23:59)

Practical exercises and code templates

Week Publication date Handin date Topic PDF Code
3 22.01.2021 05.02.2021 Practical C exercises
5 05.02.2021 19.02.2021 Hands-on with scanner generators
7 19.02.2021 05.03.2021 Parsing and VSL specification
9 05.03.2021 19.03.2021 Syntax tree simplification
11 19.03.2021 09.04.2021 Symbol table construction
14 09.04.2021 23.04.2021 Code generation


Literature

AuthorsKeith Cooper and Linda Torczon
TitleEngineering a Compiler, Second Edition
ISBN9780120884780 (hardcover) / 9780080916613 (ebook)