600.328 / 600.428: Compilers and Interpreters
You’re in the right place if you want to find out how compilers and
interpreters, the tools you’ve been using for quite a while now to do
all your programming with, really work. You’ll also pick up some useful
software development techniques along the way.
Catalog Description: Introduction to compiler design, including
lexical analysis, parsing, syntax-directed translation, symbol tables,
run-time environments, and code generation and optimization. Students
are required to write a complete compiler as a course project.
Prerequisite(s): 600.120: Intermediate Programming, 600.226: Data
Structures. (Having taken 600.233: Computer System Fundamentals and
600.271: Automata and Computation Theory is very helpful too.)
The course includes significant programming projects; without prior
development experience you’ll probably get lost in a
maze of relatively complex code.
Please read the
general course policies
and take them to heart.
Additional policies specific to this course may be posted at a later date.
- Understand the theoretical foundations for compilers
- Practice object-oriented design and the application of
- Implement a full compiler for a high-level imperative language.
- Understand the hardware / software tradeoffs involved in
There is no required text.
However, it is strongly recommended that you get yourself a text book
The following are all excellent, but none covers exactly what we’ll do in
the course, and all cover things that we’ll never even mention.
Note that most editions will do, you don’t necessarily need the latest and
therefore most expensive one.
Compilers and Interpreters
Software Development and Design
- Assignments (about 10): 70%
- Midterm: 10%
- Final: 20%
Please check the individual assignments for due dates and the structure
your solutions should have. See our Piazza
site for detailed submission instructions.
If you have an opinion on these assignments, be it good or bad, please
know about it. We’re always trying to make these things more enjoyable
(if that’s an applicable term? :-).
This is not a schedule.
It’s a “log” of what we did, roughly, in each lecture.
Don’t expect it to turn into a schedule, it won’t.
- Jan 30: Welcome,
- Feb 1: A tiny interpreter / compiler for integer expressions
(demo, tokens, scanner, abstract syntax tree, parser)
- Feb 3: A tiny interpreter / compiler for integer expressions
(concrete syntax tree, parser, interpreter, code generator for MIPS/SPIM)
- Feb 6: Compiler architecture, phases, passes,
bootstrapping and porting (T-diagrams, self-compilation test,
- Feb 8: Formal languages review,
notations for grammars (EBNF in particular),
intro to lexical analysis
- Feb 10: Regular languages and grammars,
implementation (working from EBNF, token representation, etc.)
- Feb 13: Intro to syntactic analysis,
context-free languages and grammars,
left recursion elimination for top-down parsing
- Feb 15: Recursive descent parsing,
first and follow sets,
implementation (working from EBNF, matching terminals, etc.)
- Feb 17: Example SIMPLE parse,
visualizing the parse tree (without actually building it),
the observer pattern (aka publish-subscribe aka events)
- Feb 20: Handling syntax errors,
heuristics and (bad?) assumptions,
strong tokens/symbols to resynchronize the parser,
filtering excessive error messages,
- Feb 22: No class.
- Feb 24: Context established by declarations,
mapping names to meanings,
scope objects (outer scopes, hierarchical lookup),
entry objects (constants, types, variables),
long-ish symbol table example.
- Feb 27: Background on semantic analysis,
attribute grammars (synthesized and inherited attributes),
semantic analysis code in the parser,
block structure (nested scopes, shadowing),
Type parsing and representation,
another long-ish symbol table example.
- Mar 1: Detailed example of shadowing (lots of
symbol table traversal (recursive functions, visitor pattern).
- Mar 3: Introduction to abstract grammars,
abstract syntax trees (ASTs),
simple example (involving
WRITE, assignment, expression),
type information in the AST,
example of REPEAT loop (condition, nested instructions),
design of class hierarchy for AST.
- missing a few
- Mar 13: Introduction to direct interpreter,
next-guided post-order traversal of AST,
using a stack for intermediate values,
handling numbers, binary expressions,
enviroment to track current value of variables,
handling variables in expression contexts.
- Mar 15: No class,
Peter loses fight against snow and ice.
- Mar 17: More about environments for arrays and records,
examples for more complex designators,