8.10

EECS 483: Compiler Construction

Syllabus --Fall 2023

Meeting places & times

Course staff & office hours

Instructor

  

Max New

  

maxsnew

  

Beyster 4628 & Zoom

  

Tue & Wed 3:30-5:00pm (hybrid),
and by appointment

GSI

  

Steven Schaefer

  

stschaef

  

Beyster 1637 & Zoom

  

Thu 9:00-11:00am

IA

  

Daniel Calco

  

dcalco

  

2nd Floor Duderstadt Library

  

Thu 2:00-3:00pm

Max New
Max New

Steven Schaefer
Steven Schaefer

Daniel Calco
Daniel Calco


General information

EECS 483 covers the implementation of efficient compilers for programming languages. The course focuses on the connections between language features and the impact they have on the design of a compilier, including any associated algorithms and pragmatic issues, and practical applications including those outside of programming languages proper. Participants build a working compiler including lexical analysis, parsing, register allocation and code generation. As a secondary emphasis, the course exposes students to run-time issues and optimization.

Exams

There will be no formal exams in this course. However, we will have one or two written assignments (as opposed to the programming assignments) that will serve a similar purpose. There is a final exam time scheduled for this course, but we may not use it.


External Links

This is the main website for this course. We will also use the following sites:


Materials

Software

Programming assignments will use several pieces of software:

Rust is supported by many editors you may use any editor you wish.

Compilers written in the class will be graded on Linux, and code is not cross-platform. I will provide pointers to how Mac users can easily make their code work on Linux, but Windows users are recommended to install a Linux distribution using WSL for testing. Instructions are provided here.

Books

There is no required textbook, but you may find these books useful.


Andrew Appel, Modern Compiler Implementation in ML, Cambridge University Press, 1998.

  


Keith D. Cooper and Linda Torczon, Engineering a Compiler, 2nd Ed., Morgan Kaufmann, 2004.

  


Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools, Pearson Education Inc, 2006.

Online resources

Rust Resources

X86 Resources

X64 Resources


Lectures

This table specifies the lecture schedule; topics are tentative.

Date

 

Topics (tentative and approximate)

 

Materials

8/28 M

 

Introduction to compilers, course overview

 

Reading: Rust book chapters 1-4 and notes

8/30 W

 

Rust practice, trees

 

Reading: Rust book chapters 6.2, 8.1,8.2, 9, 10.3, 11, Rust live code and slides

9/04 M

 

No class: Labor Day

 

9/06 W

 

(ONLINE ONLY) Our first compiler: grammar, abstract syntax, and x86

 

notes

9/11 M

 

Names, scope and (simple) stacks

 

notes, slides and code

9/13 W

 

Conditionals

 

notes

9/18 M

 

Sequential Form

 

notes

9/20 W

 

Multiple data types and tagging values

 

notes

9/25 M

 

Errors, Calling into Rust

 

notes

9/27 W

 

Functions Part I: Tail Calls

 

notes

10/02 M

 

Desugaring Mutable Variables and Loops

 

10/04 W

 

Functions Part II: Non-tail Calls

 

slides and notes

10/09 M

 

Lambda Lifting

 

In-class code/examples

10/11 W

 

Register Allocation Part 1: Liveness Analysis

 

slides

10/16 M

 

No class: Fall Study Break

 

10/18 W

 

Register Allocation 2: Graph Coloring

 

slides

10/23 M

 

Heap allocation

 

notes and notes

10/25 W

 

NO LECTURE: Class time used as extra office hours

 

10/30 M

 

Flattening Expressions, First-class functions

 

11/01 W

 

NO LECTURE due to illness

 

11/06 M

 

Closures

 

notes

11/08 W

 

Dataflow Analysis & Optimization

 

11/13 M

 

Frontend Overview, Regular Expressions

 

11/15 W

 

NFAs/DFAs, Lexing

 

slides

11/20 M

 

Context-free Grammars

 

slides

11/22 W

 

No class: Thanksgiving

 

11/27 M

 

Predictive Parsing and LL(1)

 

slides and code

11/29 W

 

LR(1) and LALRPOP

 

slides and code

12/04 M

 

Type Systems

 

12/06 W

 

Compiler Correctness/Course Wrap Up

 

slides


Testing

Testing your code is sufficiently important that we’ve devoted an entire page to it. Please read these notes, for each and every assignment you work on.


Homework schedule

Homework will usually be due at 5:00 PM on Fridays, but may vary on each individual assignment, so be sure to check the page every time. General homework policies are here.

Link

  

Assigned

  

Due

Assignment 0: Rust warmup and ASTs

  

Wed 08/30

  

Fri 09/08

Assignment 1: Adder: A starter language

  

Sun 09/10

  

Fri 09/22

Assignment 2: Boa: Adding new operators

  

Fri 09/23

  

Fri 09/29

Assignment 3: Cobra: Multiple types of values

  

Fri 09/30

  

Fri 10/13

Assignment 4: Diamondback: Defining functions

  

Fri 10/13

  

Sun 10/29

Assignment 5: Hundred-pacer: Register Allocation

  

Mon 10/30

  

Sun 11/05

Assignment 6: Egg-eater: Heap Allocation

  

Mon 11/06

  

Sun 11/19

Assignment 7: Garter: Design Your Own Language Extension

  

Mon 11/20

  

Part 1 Fri 12/01 Part 2 Wed 12/13


Course policies

Collaboration and academic integrity

Programming assignments may be completed with a partner or solo. To make grading/presentation time manageable, the written assignment and the final project must be completed with a partner. Discuss with the professor if you have a very strong reason it is not possible to work with a partner (personal preference is not a strong reason).

You must collaborate with your assigned partner or team, as specified, on homework assignments. You may request help from any staff member on homework. (When you are working with a partner, we strongly recommend that you request help with your partner, rather than solo.) You may use the Piazza bulletin board to ask questions regarding assignments, so long as your questions (and answers) do not reveal information regarding solutions. You may not get any help from anyone else on a homework assignment; all material submitted must be your own. If in doubt, ask a member of the course staff.

Providing illicit help to another student is also cheating, and will be punished the same as receiving illicit help. It is your responsibility to safeguard your own work.

Students who cheat will be reported to the university’s office on academic integrity and penalized by the course staff, at our discretion, up to and including failing the course.

If you are unclear on any of these policies, please ask a member of the course staff.

Homework

We will be using the following gradescope page for homework submissions.

Late days & late work

Homework will (typically) be due Friday at 5pm. Late work will be accepted for the next two days: a 10% deduction if by Saturday 11:59pm and a 20% deduction if by Sunday 11:59pm. After that, late submissions will not be accepted. This policy generally holds unless otherwise specified in the assignment.

Grades

Your grade will be based on your performance on the programming assignments and written assignments. Each assignment will be given an equal weight to the final grade, except for the final project will count for twice as much as a typical assignment. This works out to each assignment being worth 11% of your total grade, with the two portions of the final project being worth 11% each.

The grades will computed on an absolute basis: there will be no overall curving. The instructor may choose to curve an individual assignment, but please do not bank on such a chance.

The estimated mapping of raw point totals to letter grades is given below. Please note that these grade boundaries may move slightly in either direction at the discretion of the instructor: if a particular breakpoint falls in the middle of a tight cluster of numeric grades, we will attempt to move the breakpoint to give that whole cluster the same letter grade. If, near the end of the semester, you are concerned that your grade is hovering near a breakpoint, see me to discuss your concerns.

Cutoff

  

100%

  

93%

  

90%

  

86%

  

83%

  

80%

  

76%

  

73%

  

70%

  

66%

  

63%

  

60%

  

else

Letter grade

  

A+

  

A

  

A-

  

B+

  

B

  

B-

  

C+

  

C

  

C-

  

D+

  

D

  

D-

  

F