COM 3355: Compiler Design
Winter 2003

[Administrivia |Outline ]

Administrivia

Instructor: William Clinger
Directory: /course/com3355
Newsgroup: ccs.courses.com3355
Home page: http://www.ccs.neu.edu/course/com3355/index.html

Prerequisite: COM 3351 or 3352 (Principles of Programming Languages).

Textbook: Andrew W Appel, Modern Compiler Implementation in ML.

Required notes: Documentation and other notes will be available through the World-Wide Web and possibly through a copy center.

This course has two main purposes. One is to demystify compilers and to help you understand them well enough to become a better programmer. The course also serves as a review of programming languages, automata theory, computer architecture, and software design.

One midterm and one final examination will be given. The midterm will cover type checking and static semantics, SPARC and MacScheme machine architectures, and simple code generation. The final examination will also cover lexical analysis, parsing, and more complex code generation. Approximately 50 per cent of the final grade will be determined by the exams, and the other 50 per cent by the term project.

The course is built around a compiler construction project in which you will write a type checker and a simple code generator for a statically typed, block-structured programming language with automatic garbage collection. I will provide modules for scanning, parsing, assembly, and run-time storage management. The input to the type checker and code generator will be an abstract syntax tree.

The term project will be implemented in Scheme.

The term project is a substantial program. Be sure to allocate sufficient time and follow good programming practice.

Outline

• Semantic analysis
  • abstract syntax trees
  • simple type checking
  • scope of declarations
  • lexical addresses
• MacScheme machine architecture
  • run-time structures
    • expressed values
    • environments and closures
    • continuations
  • procedure calls
  • registers
  • invariants
  • Larceny
    • assembly
    • disassembly
    • primitive operations
• SPARC instruction set
• Code generation
  • values and extent
  • garbage collection
  • instruction selection
  • register allocation
  • major optimizations
• Construction of lexical analyzers
  • regular expressions
  • minimal deterministic finite automata
• Construction of efficient parsers
  • LL(1) grammars
  • deterministic top-down parsing
  • syntax-directed translation
  • construction of abstract syntax trees
  • error recovery

Last updated 2 January 2003.