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 Jan 27 more on scanners, UNIX tools for homework submission, syntactic analysis Read Chapter 2, calculator demo code from this week  
4 Feb 3 Context Free Grammar review, Study: A Tutorial on Grammars, Read Chapter 3  
5 Feb 10 First and Follow sets, formal LL(1) development Read Chapter 4, assignment 2 Monday is President's Day
6 Feb 17 various LR parsings and getting bison to build your syntax tree Read Chapter 5  
7 Feb 27 Symbol tables, type checking, and discuss what you need to know to do assignment 3 Read chapter 6 Assignment 3
8 Mar 2 more attribute grammar stuff and answer questions on assignment 3    
9 Mar 9 Attribute grammars and how to finish out our syntax tree Assignment 4  
10 Mar 16   SPRING BREAK NO CLASS THIS WEEK!
11 Mar 23 Using the error token in Bison, start looking at the Tiny Virtual Machine   PARSER TEST WEDNESDAY
12 Mar 30 Discuss assignment 4. Study the Tiny machine and memory allocation Assignment 5  
13 Apr 6 More on the virtual machine and assignment 4 Assignment 6  
14 Apr 13 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 20 Examples of code generation assignment Assignment 7  
16 Apr 27 Some on record types, object oriented languages, Optimizations in general, local optimizations, code selection, register allocation    
17 May 4      
18 May 11   FINALS WEEK Final: None

References and Resources

Code

Services

  • Homework submission page. This our homework submission page. This is not to be confused with any other submission tools used in the CS department.
  • Submitting homework without a browser
  • Computer Science IT FAQ including information on logging onto class machines.
  • The CS445 student machine is called cs-475.cs.uidaho.edu. That is not a typo. We are just reusing the machine from CS475. If you are off campus you can access this machine only by first "coming on campus" with VPN. For details see CS IT FAQ The compile command I run on that machine is:
    scl enable devtoolset-7 "make"
    
    to get the same compiler and options.

    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
  •