Revised July 13, 2015

CS 444: Compiler Construction

Watch a video introduction to this course on YouTube.

General description

This course covers the basic structure of compilers for Algol-like languages. A major part of the course involves implementing a compiler for a simplified Algol-like language. Students discover software tools and techniques that are applicable to both compilers and the implementation of system utility routines, command interpreters, etc.

Logistics

Audience

• Fourth year CS majors interested in the design and implementation of programming languages. Students who do a substantial amount of programming should find the material valuable.

Normally available

• Winter

Related courses

• Pre-requisites: CS 350 or SE 350; Computer Science students only.

For official details, see the UW calendar.

Software/hardware used

• Students can use any programming language and development tools to complete the course project.

Typical reference(s)

• Fischer, Cytron, and LeBlanc, Crafting a Compiler, Addison Wesley

Required preparation

At the start of the course, students should be able to

• Write, debug, and test moderately-sized programs
• Read and write technical documents

Learning objectives

At the end of the course, students should be able to

• Read, interpret, and implement the specification of a mainstream programming language
• Write, debug, and test a compiler that translates from a mainstream programming language to assembly language
• Document the technical decisions and tradeoffs in the design and implementation of their compiler
• Implement algorithms for parsing and parser generation
• Explain the role of types and of type soundness in the design of a programming language

Much of the course mark is based on a project that is done in teams of 3 or 4 students.

Typical syllabus

Introduction (1 hour)

• Overview of language translation
• Compiler-compilers and translator writing systems
• Notions of lexical analysis, parsing, and one-pass vs. multi-pass compilation

Course project (1 hour)

• Discussion of a general-purpose procedural, algorithmic programming language (derivative of Ada) that students taking the course write a compiler for
• Organizing group projects
• Documentation
• Programming style

Parsing and lexical analysis (3 hours)

• Introduction to automatic tools for lexical and syntactic analysis
• Discussion of underlying theory

Scope rules, block structure and symbol table organization (6 hours)

• Organization of a symbol table to reflect scoping rules provided by various language constructs
• Discussion of time/space trade-offs

Semantic processing (6 hours)

• Semantic analysis - checking that the program makes "sense"
• Declarations
• Type checking
• Overload resolution

Storage and organization (8 hours)

• Runtime stack
• Displays
• Static and dynamic links
• Parameter passing
• Procedure call and return
• Data templates
• Strings
• Heap storage management

Code generation (8 hours)

• Intermediate code
• Trees and quadruples
• Arithmetic expressions
• Boolean expressions
• Code templates for various constructs
• Introduction to code improvement and control-flow analysis
• Table-driven code generation

Code optimization (3 hours)

• Overview of techniques for producing "better" code