CPSC 421/521 Compilers and Interpreters

Spring 2020
Class: Monday and Wednesday, 1:00pm-2:15pm, WTS A60
Instructor: Robert Soulé
TAs: Wolf Honoré and Yixuan Chen
Soulé office hours: Monday 2:30pm-3:30pm or by appointment, AKW 206
Honoré office hours: Tuesday 3-4pm and Thursday 10-11am, AKW 312
Chen office hours: Monday 11:30am-12:30pm and Wednesday 4:00pm-5:00pm, AKW 310

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:

Additionally, a reference on ML will be useful, such as the following:

Discussion

Please join the Piazza site to post questions.

Grading

The final grades will be computed as follows 70% from the programming assignment and 30% from the final exam and problem sets.

Late Policy

Each student is given 100 discretionary late hours for programming assignments, but any one assignment may only be up to 72 hours late (this is because we will post the sample solution after then). These are calendar hours, not business hours. As the homework assignments are submitted electronically, the "write date" on the student's homework file will be considered the completion date for late assignments.

After you use up all of your discretionary late hours, assignments turned in late will be graded according to the following formula: S = R * (1 - t / c), where S is the grade given, R is the grade the work would have gotten if turned in on time, t is the amount of time by which the work was late, and c is equal to four days. Thus, the value of a late assignment decays daily, with a half-life of just over two days. Examples: work turned in five minutes late gets 99.9% credit, one hour late gets 99.0% credit, six hours late gets 93.8% credit, one day late gets 75.0% credit, two days late gets 50.0%, and three days late gets 25.0%. Assignments submitted more than 72 hours late will not be accepted.

There will be no extensions due to scheduling conflicts, computer downtime, or other such factors, except under truly extraordinary circumstances. Extensions will be granted only for university-sanctioned excuses such as illness, and then only with the proper documentation. You are responsible for planning ahead and managing your time so that you can complete the assignments on time. You must either finish on time or accept the consequences of doing otherwise.

Attendance

Attendance at lectures is expected but will not be recorded. Students are, however, fully responsible for all material presented in lectures, even if some of it does not appear in the "official" lecture notes. Class attendance is recommended strongly.

Assignments

Assignments are due at 11:59 PM on the date specified in the schedule.

Please check your project group to see which assignment you should implement for the compiler back-end.

Schedule

Please be sure to regularly check this page for updates.

Jan 13
Introduction; ML Language
  • Read: Appel 1
  • Reccomended: Ullman 1-3
Jan 15
More about ML; Regular Expressions
  • Read: Appel 2.1-2.4
Jan 17
SML/NJ and ML; Finite Automata
  • Read: Appel 2.3-2.4
  • Reccomended: Ullman 4-9
Jan 20
Martin Luther King Jr. Day; classes do not meet.
Jan 22
More about ML; Lex and ML-Lex
Jan 27
Context-Free Grammars; Parsing
Jan 29
Parsing & Yacc
Feb 3
Parser Generation
Feb 5
Tiger Language; Abstract Syntax
  • Read: Appel 4, Appendix
Feb 10
Symbol Tables; Type Checking
Feb 12
More on Type Checking
  • Read: Appel 5.3-5.4
Feb 17
Stack Frames
Feb 19
More on Stack Frames
  • Read: Appel 6
Feb 24
Intermediate Trees; Expressions to Trees
  • Read: Appel 7.1-7.3
Feb 26
Declarations to Trees; Canonical Trees
  • Read: Appel 7.3, 8.1-8.2
Mar 2
Instruction Selection; Assembly Code
  • Read: Appel 9-10
Mar 4
Liveness; Register Allocation; Linking
Mar 8
Spring recess
Mar 11
Spring recess
Mar 16
Spring recess
Mar 18
Spring recess
Mar 23
Garbage Collection
  • Read: Appel 13
Mar 25
Program Analysis; Optimizations
Mar 30
No class.
Apr 1
Object-Oriented Languages
Apr 6
No class.
Apr 8
No class.
Apr 10
No class.
Apr 13
No class.
Apr 15
Functional Languages
  • Read: Appel 15
Apr 20
No class.
Apr 22
LLVM and SSA

Submission Guidelines

For each programming assignment, you must turn in two things: your programs; a README file for the writeup, the writeup is an important part of your work and will contribute significantly to your assignment grade.

To submit your solutions to the programming assignments electronically, first change to the directory where your solutions are, and then use the following command.

     /c/cs421/bin/submit number files
number is the assignment number and files is the list of files for that assignment. For example,
     /c/cs421/bin/submit 3 README sources.cm tiger.lex
submits the files README, sources.cm, and tiger.lex for a fictitious assignment 3.

The submit command copies your files to the directory /c/cs421/SUBMIT/number/login and lists all the files that you have submitted for assignment number. Here, login is your user account name.

There is also unsubmit, which allows you to retract one or more files. For example,

     /c/cs421/bin/unsubmit 3 tiger.lex
would remove your tiger.lex from the submission directory.

You can also check what files you have submitted by using the check command. For example,

     /c/cs421/bin/check 3
would list all the files your have submitted so far for assignment 3.

Usually, you can omit the /c/cs421/bin/ prefix if /c/cs421/bin/ is already added to your PATH variable.

References

Acknowledgements

The course website is based on the design by Robert Grimm. The course content is based on a previous course by Zhong Shao.