COM 1355: Compiler Design 1
Winter 2003

[Administrivia |Outline ]

Administrivia

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

Prerequisite: COM 1201, 1350 (Data structures, Automata).

Textbook: Andrew W Appel, Modern Compiler Implementation in Java, Second Edition.

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 simple code generator for a statically typed, block-structured programming language with automatic garbage collection. I will provide modules for scanning, parsing, type checking, assembly, and run-time storage management. The input to the code generator will be an abstract syntax tree.

In theory, you may write your code generator in any programming language you like. In practice, you will write your code generator in Java. Otherwise you would have to translate some of the modules that I am providing into your preferred implementation language.

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 6 January 2003.