50.054 Compiler Design and Program Analysis

Home / Education / Undergraduate / Courses / 50.054 Compiler Design and Program Analysis

Course Description

This course aims to introduce a new programming paradigm to the learners, Functional programming and the suite of advanced language features and design patterns for software design and development. By building on top of these techniques, the course curates the process of designing a modern compiler, through syntax analysis, intermediate representation construction, semantic analysis and code generation. More specifically the course focuses on the application of program analysis in areas of software verification, program optimization and software security analysis.

Pre-requisite

50.004 Algorithms

Learning Objectives

  • Implement software solutions using functional programming language and applying design patterns
  • Define the essential components in a program compilation pipeline
  • Design a compiler for an imperative programming language
  • Optimise the generated machine codes by applying program analysis techniques
  • Detect bugs and security flaws in software by applying program analysis techniques

Measurable Outcomes

  • Develop a parser for an imperative programming language with assignment, if-else and loop (AKA the source language) using Functional Programming
  • Implement a type checker for the source language
  • Develop a static analyser to eliminate dead codes
  • Implement the register allocation algorithm in the target code generation module
  • Develop a static analyser to identify potential security flaws in the source language

Topics Covered

  • Functional Programming Basics: expression, conditional, function and recursion
  • Functional Programming: list, algebraic data types and pattern matching
  • Functional Programming Advanced: generics, GADT, type classes
  • Functional Programming Design patterns: Functor
  • Functional Programming Design patterns: Applicative and Monad
  • Syntax Analysis: lexing, top-down parsing
  • Syntax Analysis: bottom-up parsing, parser combinator
  • Intermediate Representation: pseudo assembly
  • Intermediate Representation: static single assignment
  • Semantic Analysis: dynamic semantics
  • Semantic Analysis: static semantics, type checking, type inference
  • Semantic Analysis: lattice, sign analysis
  • Semantic Analysis: liveness analysis, information flow analysis
  • Code Generation: instruction selection, register allocation
  • Memory management
  • Activation Record

Recommended Texts and Readings

  • Compilers: Principles, Techniques, and Tools is a computer science textbook by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman
  • Modern Compiler Implementation in ML by Andrew W. Appel
  • Static Program Analysis by Anders Møller and Michael I. Schwartzbach

Course Instructors

Prof Kenny Lu

Image Credit