CMSC 430, Spring 2009

Theory of Language Translation

Schedule

Lectures & Discussions

Week of: Tuesday Lecture Thursday Lecture
Jan 26



Introduction
Feb 2 Scanners Parsing - Derivations, Ambiguity
Feb 9 Parsing - Backtracking, Left Recursion LL(1) Predictive Parsing
Feb 16 Bottom-up Parsers LR(1) Shift-Reduce Parsing
Feb 23 Parsing Wrapup
Quiz 1
Mar 2 Context Sensitive Analysis Type Checking
Mar 9
Quiz 2
Intermediate Representations
Code Generation
Mar 16
Spring Break

Mar 23 Code Generation 2 Run-time Environment
Mar 30
Midterm 1
Code Generation 3

Optimization Overview
Apr 6 Classical Optimizations Global Optimizations
Apr 13 Dataflow Analysis Dataflow Analysis 2
Apr 20 Dataflow Analysis Frameworks Instruction Scheduling (part1, part2)
Apr 27 Register Allocation Compiling For High Performance
May 4
Midterm 2
Compiler Optimization Research
May 11 No lecture, read Hall et al., CACM Feb 09
Compiler Research: The Next 50 Years

Projects

  • Project 1 - due Mon, Feb 23
    • DFA Minimizer in Java
    • Project description & downloads here

  • Project 2 - due Thu, Mar 12 (Extension to Mon, Mar 16)
    • C-- Scanner & Parser
    • Project description & downloads here

  • Project 3 - due Fri, Apr 3
    • C-- Type Checker
    • Project description & downloads here

  • Project 4 - due Mon, Apr 27
    • C-- Code Generator
    • Project description & downloads here

  • Project 5 - due Tue, May 12
    • C-- Global Optimizer
    • Project description & downloads here

Quizzes

  • Quiz 1 - Thu, Feb 26
    • Topics - regular expressions & finite automata, context free grammars & derivations, top-down LL(1) parsers
    • Practice problems and solutions
    • Solution

  • Quiz 2 - Tue, Mar 10

  • Quiz 3 - Cancelled
    • Topics - intermediate representations, code generation, run-time environment
    • Practice problems and solutions

Tests

  • Midterm 1 - Tue, Mar 31
  • Midterm 2 - Tue, May 5
    • Topics - intermediate representations, code generation, optimization, dataflow analysis
    • Practice problems and solutions
    • Solution

  • Final Exam - Wed, May 20 (10:30am-12:30pm, CSIC 3117)
    • Topics - everything (material since Midterm 2 emphasized)
    • Practice problems and solutions

Valid HTML 4.01!