CS445 Compiler Construction
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%
- Aho, Sethi and Ullman. Compilers. Addison-Wesley Publishing
- Levine, Mason, and Brown. lex & yacc. O'Reilly and Associates,
- Kernighan and Ritchie. The C Programming Language. Second edition.
- Kelley and Pohl. A Book on C. Fourth edition. Addison-Wesley,
- Horspool. The Berkeley UNIX Environment. Second edition. Prentice-Hall,
- Paul. SPARC Architecture, Assembly Language Programming, & C.
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.
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
- Design a lex scanner and a yacc parser for the Pascal
grammar in Appendix A in the Dragon book.
Deadline: Middle of February.
- Modify the grammar so that nested local subroutines are allowed.
- 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
- There is a small complication with the last rule involving sign.
- If you need a good starting point, use the sample handout on the
- Design a symbol table and semantic checker module that
performs the necessary checks. It should catch violations involving:
You should have the symbol table manager implemented before Spring break.
- using variables before declaring them.
- type mismatches in expressions.
- scoping rules
- improper usage of procedures and functions
- others (list will be updated)
Here is a list of semantic checks. Also check the directory ~tino/public/cs445/testing
for some Pascal test files.
Deadline: End of March.
- Design a code generator that outputs assembly code for the
Sun SPARC assembly language.
Deadline: End of April.
- Assignment 1: C & UNIX warmup
- Assignment 2:
- Functional lex scanner for Pascal.
- Functional yacc parser for Pascal.
- Functional symbol table manager for Pascal written in C.
- Working semantic checker for Pascal. This has to pass all the
list of checks given in the public directory.
- Working code generator for Pascal and SPARC assembly language.