CS G262: Compilers
Fall 2004

[Administrivia | Outline ]

Administrivia

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

Prerequisite: CS G111 (Principles of Programming Languages) or CS G711 (Intensive Principles of Programming Languages)

Catalog Description:
Each student will write a small compiler. Topics include parser generation, abstract syntax trees, symbol tables, type checking, generation of intermediate code, simple code improvement, register allocation, run-time structures, and code generation.

Textbook: Andrew W Appel, Modern Compiler Implementation in ML, Second Edition. (Students may use the Java or C version instead of the ML version.)

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

This course has three main purposes

1. To demystify compilers and to help you understand them well enough to become a better programmer.
2. To review programming languages, automata theory, computer architecture, and software design.
3. To provide some of the background knowledge and experience that are expected of someone who is doing research in the area of programming languages.

One midterm and one final examination will be given. The midterm will cover type checking and static semantics, simple intermediate languages, machine architectures, and simple code generation. The final examination will also cover lexical analysis, parsing, and more sophisticated 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 compiler for a statically typed, block-structured, higher-order programming language with automatic garbage collection. I will define interfaces between the modules of your compiler, provide semiformal specifications of those modules, and supply you with at least one assembler and a run-time system that includes a generational garbage collector.

You will write most of your compiler in Scheme, because your compiler will be required to work with instructor-supplied modules that are written in Scheme. Scheme is also the only programming language that is implied by the CSG 111/711 prerequisite, and is likely to be the only programming language that is familiar to every student who takes the course.

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

Outline

• Formal specifications
  • regular expressions
  • context-free grammars
  • attribute grammars
  • algebraic specifications
  • Gentzen-style deduction systems
  • conditional constraint systems
• Semantic analysis
  • abstract syntax trees
  • simple type checking
  • scope of declarations
  • lexical addresses
  • tail calls
• Machine architecture
  • run-time structures
    • expressed values
    • environments and closures
    • continuations
  • procedure calls
  • registers
  • invariants
  • Larceny
    • the MacScheme machine
    • assembly
    • disassembly
    • primitive operations
  • SPARC instruction set
• Code generation
  • values and extent
  • garbage collection
  • proper tail recursion
  • instruction selection
  • peephole optimization
  • instruction scheduling
  • register allocation
• Major optimizations
  • Kleene fixed-point theorem
  • closure analysis, lambda lifting, and closure conversion
  • interprocedural constant propagation, folding, and inlining
  • interprocedural representation and subrange inference
  • interprocedural aliasing and liveness analysis
  • A-normal and SSA forms
  • copy propagation, commoning, and dead code elimination
• Construction of lexical analyzers
  • nondeterministic finite automata
  • 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 September 2004.