Topics
Readings and problem sets to prepare in advance of meetings on the listed date.
Regular Expressions and Finite Automata
- Assignment
- Outline
- Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …), Russ Cox.
Lexers, Grammars, Top-Down Parsing
← Monday, 8 February - Friday, 12 February
- Assignment
- Refer again as needed to last week’s readings, including Russ Cox’s article.
- Fun: We built a simplified URL regex. How about one for email addresses?
Bottom-Up Parsing
- Assignment
- Refer again as needed to last week’s readings, especially on FIRST and FOLLOW.
Abstract Syntax Trees and Symbol Tables
- Assignment
- Code for exercise 1: cs301-tiny3.tar.gz
- Refer back to our Tiny compiler front end and back end as needed.
Scope and Types
- Assignment
- Type Systems, Luca Cardelli.
- Lambda calculus reference:
- Lambda calculus on Wikipedia
- A short introduction to the Lambda Calculus, Achim Jung.
Objects, Subtyping, Information Flow
- Assignment
- Type Systems, Luca Cardelli.
- Lambda calculus reference:
- Lambda calculus on Wikipedia
- A short introduction to the Lambda Calculus, Achim Jung.
- Language-Based Information-Flow Security, Andrei Sabelfeld and Andrew C. Myers.
- EnerJ: Approximate Data Types for Safe and General Low-Power Computing (technical paper) and EnerJ, the Language of Good-Enough Computing (article for more general audience), Adrian Sampson, et al..
Intermediate Code and Object Representation
- Assignment
- TAC specification
- Available outside my door:
- Appel, Modern Compiler Implementation in Java (14-14.3, 14.6-14.7)
- Bruce, Foundations of Objected Oriented Languages for OO reference
- Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis
- Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches
Code Generation
This week, we will discuss code generation and x86-64 assembly in class. These slides, exercises, and reading accompany the class activities. See also the resources on the project page.
Optimization and Data-Flow Analysis
← Friday, 1 April - Monday, 4 April
This set of reading and exercises is a little larger than usual, since we did not have meetings this week. Please try the reading up through about local optimizations and exercises 1, 2, and (optionally) 3 for class on Friday. You do not need to write solutions. We will discuss some of these examples together in class on Friday and (if time) lay some groundwork for your exploration of data-flow analysis in preparation for tutorial meetings.
Data-Flow Framework
We will get a head start a bit in class on Friday. No prep required by then.
More Optimization
- Assignment
- See also (coming soon): IC Optimizer