Class Description

An introduction to compiler design and construction. This is a hands-on compiler construction course in which each student will work independently to construct a compiler that actually compiles a rather complex C like language including recursive functions and arrays. The student will be carefully guided toward a successful completion by working on incremental development and testing of the compiler. On line testing tools will be available for constructing your compiler.

Goals:

  1. Understand the basic theory of languages and techniques for simple language translation.
  2. Understand the features of compilers and interpreters.
  3. Understand why compilers behave as they do and why languages may be designed the way they are in response to compiler constraints.
  4. Understand the basic components and layered design of a compiler and the rational for their use.
  5. Each student will be responsible for independently building a simple compiler for a virtual machine and augment it with new features. The compiler will handle typing, procedure invocation, arrays, recursion, optimization, global and local scope, etc. The instructor will help the student to achieve this goal over a series of assignments, but it is up to the student to keep up with the assignments and complete each on time.

It is highly recommended that students be proficient in C or C++ and have good data structures skills. The students will be expected to write a program that has from 2000 to 5000 lines of code depending on how they solve the problems presented. A tiny sample compiler will be provided and some example pieces of code and support libraries provided. Since this is a phased development, completing each assignment in sequence and having good time management skills is critical. You must successfully complete each phase in order. These are skills that employers are looking for. In fact our industrial advisory board particularly likes the compiler course as a test of the skills of applicants.

A partial list of necessary skills to be successful at compilers

Time: 8:30-9:30 TWThF (ouch)
Location: EP204 and video to remote locations
Tests: There will be two tests
Final: None

Required Textbook: Compiler Construction: Principles and Practice by
Kenneth Louden, ISBN: 0534939724, Cengage Learning
I intentionally use this book a lot so you can use it for support.

Estimated Syllabus

This syllabus is an estimate of what we might cover this semester. The class varies from semester to semester to reflect new and interesting topics.

Wk#

Monday
of that
Week

Topics/Links Assignments Comments
1 Jan 13 Introduction to the class, what we plan on doing, how the class works, where to find stuff. How is a compiler organized. assignment  
2 Jan 20 Scanners and how they are defined, grammars, intro to flex and bison. Read Chapter 1, assignment 1 Monday is Martin Luther King Day
3 Feb 3 more on scanners, UNIX tools for homework submission, syntactic analysis Read Chapter 2  
4 Feb 10 Context Free Grammar review, Study: A Tutorial on Grammars, calculator demo code from this week Read Chapter 3 GRAMMAR TEST WEDNESDAY
5 Feb 17 First and Follow sets, formal LL(1) development Read Chapter 4, assignment 2 Monday is President's Day
6 Feb 24 various LR parsings and getting bison to build your syntax tree Read Chapter 5  
7 Mar 2 Symbol tables, type checking, and discuss what you need to know to do assignment 3 Read chapter 6 Assignment 3
8 Mar 9 more attribute grammar stuff and answer questions on assignment 3    
9 Mar 16   SPRING BREAK NO CLASS THIS WEEK!
10 Mar 23 Attribute grammars and how to finish out our syntax tree assignment  
11 Mar 30 Using the error token in Bison, start looking at the Tiny Virtual Machine Assignment 4 PARSER TEST THURSDAY
12 Apr 6 Discuss assignment 4. Study the Tiny machine and memory allocation Assignment 5  
13 Apr 13 More on the virtual machine and assignment 4 Assignment 6  
14 Apr 20 Memory allocation and code generation, extensions to C- that are common in many languages but that we won't actually include. Read Chapter 7  
15 Apr 27 Examples of code generation assignment Assignment 7  
16 May 4 Some on record types, object oriented languages, Optimizations in general, local optimizations, code selection, register allocation    
17 May 11   FINALS WEEK Final: None

References and Resources

Code

Services

Policies and Processes

Cool Links

These links are provided to entertaining and informative. You don't need to study them unless it is suggested that you do so. These links are not guaranteed to accurate, contain information that is safe to download, or not offend your morals, good sense or good taste, or to give sound financial advice. Some small parts may pose a choking hazard for children...
  • Jflex a java version of flex. It has links to Java based parser generators.
  • Cygwin in case you want that comfortable UNIX feel on your Windows box. This will give you a command shell and numerous UNIX tools for Windows.
  • LCC a retargetable free C compiler with lots of goodies.
  • A list of over 2500 computer languages
  • Zebu A parser generator for generating Common Lisp code
  • ANTLR A popular LL parser generator
  • A Python lex and yacc