CS606 - Compiler Construction
Course Page
Q & A
Course Category: Computer Science/Information Technology
Course Level: Imdregraduate
Credit Hours: 3
Pre-requisites: CS201 CS402

Course Synopsis

The course introduces the students to the operation of a modern compiler that translates code in a programming language into machine code. Special emphasis is placed on the actual construction of a compiler by working on a project that builds a compiler for a language that is a subset of C++. Modern compilers operate in three passes. These are front-end, middle end and back end. Given a program written in a programming language, the front end carries out syntax analysis of input program. The middle end performs code optimization so that the eventual executable program will require less memory and will be efficient at runtime. The back end generates actual assembly language code for the target machine. We will study mechanics of the three stages. However, due to the introductory nature of the course, we will spend majority of the time on syntax analysis and code generation. We will touch upon optimization briefly. The course provides a practical opportunity to see how concepts and techniques from various areas of Computer Science come together to build a useful tool.

Course Learning Outcomes

At the end of the course, you should be able to
  • Translate and interpret computer languages
  • The basic theory of compilers
  • Evaluate the issues involved in implementing a compiler
  • Better knowledge about how a compiler works
  • Design parsers and compilers for any language

Course Contents

Passes of a Compiler. Lexical Analysis, Specification of Tokens, Recognition of Tokens, Top-down Parsing, Predictive Parsing, Recursive Descent Parsing, LL Parsing, LL Pasing Table Construction, Left Factoring, Bottom-up Parsing, Shift-Reduce Parsing, LR(1) Parsing, LR(1) Canonical Collection of Items, LR(1) Parsing, Shift-Reduce Conflicts, LALR Parsing, Parser Generators – YACC, Sematic Analysis, Attribute Grammars, Ad-hoc scheme for attribute grammars, Intermediate Representation (IR), Intermediate Representation taxonomy, Syntax-directed translation: assignment statement, Code Generation, Code Optimization

Course Related Links

The Catalog of Compiler Construction Tools
"Real programmers can write assembly code in any language." - Larry Wall
Compiler construction From Wikibooks, the open-content textbooks collection
Compiler Construction Principles and Practice by Kenneth C. Louden
14th International Conference on Compiler Construction (CC)
Compiler Construction Course Concepts and Practical Application to .NET
COMP 512: Advanced Compiler Construction
Free Compiler Construction Tools
Let's Build a Compiler, by Jack Crenshaw
CS577 Compiler Construction (Modern Language Processors) Spring 2002
What's the difference between parse tree and AST?
Hopcroft's algorithm understanding in Lecture 9
Three Address Code Examples
Course Instructor

Dr. Sohail Aslam
Ph.D, University of Illinois,
at Urbana-Champaign

A Compact Guide to Lex & Yacc by Thomas Niemann

Compiler Construction using Flex & Bison by Anthony Aaby

Compilers & Compiler Generators by PD Terry

Compilers Principles, Techniques & Tools by Alfred V. Aho.

Operator-Precedence Parsing by Thomas Niemann

Programming Language Concepts by Carlo Ghezzi, Mehdi Jazayeri