CPSC 421/521 Compilers and Interpreters

Spring 2021
Class: Monday and Wednesday, 1:00pm-2:15pm, Zoom (See Canvas)
Instructor: Robert Soulé
TAs: Yixuan Chen and Yu Zhang
Soulé office hours: By appointment
Chen office hours: Tuesdays at 3:00pm EST
Zhang office hours: Thursdays at 9:00am EST


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.



We rely on one textbook:

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


Please join the cpsc421-spring2021 mailing list to post questions.

Please join the Piazza site to post questions.


The final grades will be computed as follows 100% from the programming assignments.

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 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 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.


Please be sure to regularly check this page for updates.

Feb 1
Introduction; ML Language
  • Read: Appel 1
  • Reccomended: Ullman 1-3
  • Optional: Aho et al. 1.1-1.2
Feb 35
More about ML; Regular Expressions
  • Read: Appel 2.1-2.4
  • Optional: Aho et al. 2.1-2.5
Feb 8
SML/NJ and ML; Finite Automata
  • Read: Appel 2.3-2.4
  • Reccomended: Ullman 4-9
  • Optional: Aho et al. 3.1-3.6
Jan 15
More about ML; Lex and ML-Lex
Feb 17
Context-Free Grammars; Parsing
Feb 22
Feb 24
Parsing & Yacc; Abstract Syntax
  • Read: Appel 3.2-3.4
  • Read: ML-Yacc Manual
  • Optional: Aho et al. 4.5-4.8
  • Read: Appel 4, Appendix
  • Optional: Aho et al. 5.1-5.3
Mar 1
Type Inference
Mar 3
Type Inference 2; Symbol Tables; Type Checking
  • Read: Appel 5.1-5.3
  • Optional: Aho et al. 1.6,2.7,6.5
Mar 8
Mar 10
More on Type Checking
  • Read: Appel 5.3-5.4
Mar 15
Stack Frames
Mar 17
More on Stack Frames
  • Read: Appel 6
Mar 22
Intermediate Trees; Expressions to Trees
  • Read: Appel 7.1-7.3
  • Optional: Aho et al. 6.2-6.4, 6.6
Mar 24
Mar 29
Declarations to Trees; Canonical Trees
  • Read: Appel 7.3, 8.1-8.2
Mar 31
Instruction Selection; Assembly Code
  • Read: Appel 9-10
  • Optional: Aho et al. 8.8
Apr 5
Liveness; Register Allocation
Apr 7
Apr 12
Garbage Collection
  • Read: Appel 13
  • Optional: Aho et al. 7.5-7.6
Apr 14
Linking, Functional Languages
Apr 16
Apr 19
Object-Oriented Languages
  • Read: Appel 14
Apr 21
  • Read: Appel 15
Apr 26
Apr 28
May 3
No class
May 12
No class

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.



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