Overview

This course is intended to explore the principal ideas and techniques of compiler construction. Topics include lexical analysis, syntax analysis including LL and LR parsers, type checking, run-time environments, symbol tables, code generation, and compiler-construction tools.

This course aims to give you a solid foundation in the theory of compiler construction as well as the experience of building a compiler. Much of what you have learned about algorithms and data structures will come to bear as you study and implement the various components of a compiler. In a sense, compiler construction is a showcase for many other disciplines of computer science.

Goals

To learn structure of compilers.
To learn basic techniques used in compiler construction such as lexical analysis, top-down and bottom-up parsing, context-sensitive analysis, and intermediate code generation.
To learn basic data structures used in compiler construction such as abstract syntax trees, symbol tables, three-address code, and stack machines.
To learn software tools used in compiler construction such as lexical analyzer generators (Lex), and parser generators (Yacc).
To construct a compiler for a small language using the above techniques and tools.

Meeting places & times

Class time: 3CD5G (Wed. 10:10-12:00 and Fri. 15:30-16:20)
Class location: EC015

Grading policy (total of 100%)

Grades will be assigned based on

midterm exam (25%)
final exam (25%)
course projects (45%)
class participation (5%)

The penalty for late homework is 15% per day (weekends count as 1 day). Late homework will not be accepted after the solutions have been posted.

These weights are subject to minor variation.

Statements on plagiarism

Homework assignments must be individual work. While you are allowed (and encouraged) to work together in understanding the concepts of the course, sharing of algorithms or code is NOT ALLOWED.

Textbook

Compilers: Principles, Techniques, and Tools (2nd edition) (a.k.a. Dragon Book), by Aho, Lam, Sethi, and Ullman, Addison Wesley, 2007.
Errata sheet: the first errata sheet, the latest errata sheet

Reference books

Lex & Yacc, by Doug Brown, John Levine, and Tony Mason, O'Reilly Media, 1995.
The JavaTM Virtual Machine Specification, 2nd edition, by Tim Lindholm and Frank Yellin, Addison-Wesley 1999.

Prerequisites

Programming Languages, Data Structures, and Assembly Language and System Programming