CS445 Compiler Construction
Spring 2000


Instructor: Christino Tamon
Lectures: MWF 8am SC354
Office hours: MWF 9-11am SC373
Pre-requisites: CS344, CS345 or consent.
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 (2) 40%
Required Texts:
  1. Aho, Sethi and Ullman. Compilers. Addison-Wesley Publishing Company, 1986.
  2. Levine, Mason, and Brown. lex & yacc. O'Reilly and Associates, Inc., 1992.
Recommended references
  1. Kernighan and Ritchie. The C Programming Language. Second edition. Prentice-Hall, 1988.
  2. Kelley and Pohl. A Book on C. Fourth edition. Addison-Wesley, 1998.
  3. Horspool. The Berkeley UNIX Environment. Second edition. Prentice-Hall, 1992.
  4. Paul. SPARC Architecture, Assembly Language Programming, & C. Prentice-Hall, 1994.

Course project

For each component, perform extensive testing (beyond the normal and standard amount). You are allowed to work in a group of at most two persons.
  1. Design a lex scanner and a yacc parser for the Pascal grammar in Appendix A in the Dragon book.
    1. Modify the grammar so that nested local subroutines are allowed.
    2. Allow inputs coming from a file. Some Pascal test files are in ~tino/public/cs445/ suffixed by .p
      The good files are prefixed with tst and the bad ones by bad.
    3. There is a small complication with the last rule involving sign.
    4. If you need a good starting point, use the sample handout on the C grammar.
    Deadline: Middle of February.
  2. Design a symbol table and semantic checker module that performs the necessary checks. It should catch violations involving:
    1. using variables before declaring them.
    2. type mismatches in expressions.
    3. scoping rules
    4. improper usage of procedures and functions
    5. others (list will be updated)
    You should have the symbol table manager implemented before Spring break.
    Here is a list of semantic checks. Also check the directory ~tino/public/cs445/testing for some Pascal test files.
    Deadline: End of March.
  3. Design a code generator that outputs assembly code for the Sun SPARC assembly language.
    Deadline: End of April.
During the final week of classes, arrange a meeting time with me for a presentation of your project. An online testing of your compiler will be part of the presentation.

Assignments

  1. Assignment 1: C & UNIX warmup
    Text formatter.
  2. Assignment 2:
    Simple calculator

Links
Minimal requirements
  1. Functional lex scanner for Pascal.
  2. Functional yacc parser for Pascal.
  3. Functional symbol table manager for Pascal written in C.
Further requirements
  1. Working semantic checker for Pascal. This has to pass all the list of checks given in the public directory.
  2. Working code generator for Pascal and SPARC assembly language.