Compilers

Overview

This course focuses on the design and implementation of compilers. Topics covered include the structure of one-pass and multiple-pass compilers; symbol table management; lexical analysis; traditional and automated parsing techniques; syntax-directed translation and semantic analysis; run-time storage management; intermediate code generation; introduction to optimization; and code generation. This course requires a substantial, semester-long programming project implementing a functional compiler that includes lexical and syntactic analyzers, a type checker, and a code generator.

Details

Textbooks

We rely on one textbook:

• Compilers: Principles, Techniques, and Tools, 2nd edition, by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. (Called the Dragon Book.)

Additionally, a reference on Antlr may be useful, such as the following:

• The The Definitive ANTLR 4 Reference, by Terence Parr.

Moodle

Please send class-related questions to the Discussions Forum on Moodle (unless, of course, they concern private rather than technical or organizational issues).

Grading Policy

• There will be a homework assignment roughly every week.
• There will be a project milestone every 2-3 weeks. These will require a substantial amount of programming.
• There will two exams: a midterm and a final.

The final grades will be computed as 10% from homeworks, 30% from the project, 20% from the midterm exam, and 40% from the final exam.

• If you submit at least 1 minute late, but at most 3 hours late, you receive 50% of the points for that assignment.
• Otherwise, late homeworks or project milestones are only acceptable if the lateness is caused by circumstances beyond your control, such as illness or a missed flight.
• In this case, you only get the points for the homework if you provide official documentation, such as a doctor's certificate, for the reason why your homework is late.

Academic Integrity

I encourage you to collaborate on homework assignments. But you must write up and turn in your own answers. Also, you must clearly indicate who you collaborated with. If I detect any incidents of cheating, I will report them immediately to the department, and the assignment will be given a grade of 0.

Readings

Students must write a review for each assigned paper (to make sure everyone keeps up with the readings). Each review should be about a paragraph long and discuss in the student's own words (1) the main idea(s) of each paper, (2) the student's main criticisms (regarding soundness, methodology, presentation, etc.), and (3) relevance to current systems or future research directions. David Wetherall at the University of Washington has written a great guide to reviewing papers.

Reviews are submitted by emailing them to the professor and the TA in plain-text format (with hard line breaks after each line). Paper reviews are due at 8am on the day of the corresponding class!

Syllabus

Please be sure to regularly check this page for updates.

Sep 16

Introduction

• Read: Aho et al. 1.1-1.2
• Homework 1 out
• Lecture notes
• Homework 1 out

Sep 18

Simple Translator

• Read: Aho et al. 2.1-2.5
• Lecture notes

Sep 23

Lexical analysis

• Read: Aho et al. 3.1-3.6
• Lecture notes
• Homework 2 out
• Project 1 out

Sep 25

Introduction to Antlr and work on project

Sep 30

Top-down syntax analysis

• Read: Aho et al. 4.1-4.4
• Lecture notes
• Homework 2 due
• Homework 3 out

Oct 2

Work on project

• Yanok travelling

Oct 7

Bottom-up syntax analysis

• Yanok travelling
• Lecture notes
• Additional handout
• Read: Aho et al. 4.5-4.8
• Project 1 due
• Homework 3 due
• Homework 4 out
• Project 2 out

Oct 9

Work on project

• Yanok travelling

Oct 14

Syntax-directed translation

• Soulé travelling
• Lecture notes
• Read: Aho et al. 5.1-5.3
• Homework 4 due
• Homework 5 out

Oct 16

Work on project

• Soulé travelling

Oct 21

Review

Project 2 due

Homework 5 due

Oct 23

Midterm

Oct 28

Name and type analysis

• Lecture notes
• Read: Aho et al. 1.6,2.7,6.5
• Homework 6 out
• Project 3 out

Oct 30

Nov 4

Intermediate-code generation

• Lecture notes
• Read: Aho et al. 6.2-6.4, 6.6
• Homework 6 due
• Homework 7 out

Nov 6

Nov 11

Run-time environments

• Lecture notes
• Read: Aho et al. 7.1-7.4
• Project 3 due
• Project 4 out

Nov 13

Nov 18

Code generation

• Lecture notes
• Read: Aho et al. 8.1-8.4, 8.6
• Homework 7 due

Nov 20

Nov 25

Register allocation

• Lecture notes
• Read: Aho et al. 8.8
• Project 4 due
• Project 5 out

Nov 27

Simone D'Avico and Lorenzo Ferretti lecture

• Read: [Gazzillo+]
• Read: [Hirzel+]
• Paper summaries due.

Dec 2

Optimization

• Read: Aho et al. 8.5-8.7
• Lecture notes
• Homework 8 out

Dec 4

Boyan Beronov and Florian Jung lecture

• Read: [Mainland+]
• Read: [Leroy]
• Paper summaries due.

Dec 9

Garbage collection

• Read: Aho et al. 7.5-7.6
• Lecture notes
• Project 5 due
• Homework 8 due

Dec 11

Zaikun Xu and Dhananjay Tomar lecture

• Read: [McAfee+]
• Read: [Ansel+]
• Paper summaries due.

Dec 16

Nate Nystrom Guest Lecture

• Partial Evaluation tutorial
• Partial Evaluation tutorial
• Hybrid partial evaluator for Java

Dec 18

Arun Verma and Oleh Zhymolokhov lecture

• Read: [Kawachiya+]
• Read: [Gvero+]
• Paper summaries due.

Jan 18

Exam at 13:30, Room SI-006

References

• Tack language specification
• Tack IR specification
• Introduction to Antlr
• Introduction to x64 Assembly
• Antlr grammar for infix-to-postfix translator
• Java driver for infix-to-postfix translator
• Example AST generator

Acknowledgements