CS 444 | SCS | UW

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