CS 444 | SCS

To provide a thorough understanding of the basic structure of compilers for Algol-like languages. A major part of the course consists of the implementation of a compiler for a simplified Algol-like language. To acquaint students with software tools and techniques which are applicable both to compilers and the implementation of system utility routines, command interpreters, etc.

Intended Audience

CS 444 is a course for CS major students, and is normally taken in a student's fourth year. It should appeal to anyone who is interested in the design and implementation of programming languages. Anyone who does a substantial amount of programming should find the material valuable.

Related Courses

References

Modern Compiler Implementation in Java, 2nd ed., by A. Appel, Cambridge University Press, 2002.

Crafting a Compiler Implementation by Fischer, LeBlanc, Cytron, Addison-Wesley

Schedule

Notes

Outline

Introduction (1 hr)

An overview of language translation. Compiler-compilers and translator writing systems. The notions of lexical analysis, parsing, and one-pass vs. multi-pass compilation.

Course Project (1 hr)

Discussion of a general-purpose procedural, algorithmic programming language (derivative of Ada) for which students taking the course write a compiler. 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)

The 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. An introduction to code improvement and control-flow analysis. Table-driven code generation.

Code Optimization (3 hours)