CS445/CS545 Compiler Construction
Spring 2001

Instructor: Christino Tamon
Lectures: MWF 8-9am Science Center 354
Laboratory meets: F 8am Rowley 142
Office hours: Science Center 373 MW 9-10am, 11-noon F 9-10am
Pre-requisites: CS344, CS345.
Syllabus: A study of compiler design. Overview of the compilation process. Formal definition of syntax, lexical scanning, parsing including LL and LR grammars, run-time structures, intermediate code generation, and storage allocation. Students are expected to develop a compiler for a substantial subset of a high-level language using compiler tools such as lex and yacc.

Course grading: Project 60%, Exams 30%, Miscellaneous 10%

Texts: [main][recommended]

Tentative Outline

  1. Language translation. Compilation. Overview.
  2. Lexical Analysis. Regular expressions.
  3. Syntax Analysis. Theory of Parsing: top-down LL(1); bottom-up SLR(1), LR(1) (and LALR(1)).
  4. Semantic Analysis. Parse trees. Syntax-directed translation. Type checking.
  5. Code generation. Runtime environments.

Readings and notes

Course project

The goal of the project is to build a compiler for a large chunk of a Pascal-like programming language. The output of the compiler is an executable SPARC assembly program. If the compiler is called yapc (Yet Another Pascal-like Compiler), then a typical happy ending scenario is as follows:
% yapc -o boo main.p 
% boo
The first line should never result in a segmentation fault (i.e. the compiler should never crash) and the second line will execute whatever is meant to be done in the Pascal source code main.p. Since we are generating SPARC assembly code, some local machines that would be able to run these are crux and atlantis.

Assignments (mini projects)

  1. C & UNIX
  2. Calculator
  3. Scanner (deadline: 02/02/01)
  4. Symbol table (deadline: 02/15/01)
  5. Parser (deadline: 02/28/01)
  6. Semantic analyzer; type checker (deadline: 03/30/01)
  7. Code generator (deadline: 04/25/01)