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: 2:30-3:30 MTWTh(F)
Location: Live at the time above via Zoom. See BBLearn for class for Zoom id.
Tests: There will be two tests.
Final: None! Just the big compiler project.
Coding: *Lots* of C++, plus UNIX skills.

Covid-19 Adjustments
  • This class will be taught entirely on Zoom. ZOOM ID in bblearn for class.
  • A recitation class will be taught, experimentally, on the Friday of the week in the class time slot. I will re-cap the week's lectures and ask for more questions. This class is optional but will be recorded as if a real class. This is in response to almost no one showing up for office hours the previous semester.
  • All zoom lectures will be recorded and appear in the videos section in the class BBLearn page.
  • Except for videos and grades all else will appear here on the class web page.
  • All email from students should have the subject: CS445.
  • Since almost no one showed up for office hours last semester I will try office hours BY APPOINTMENT ONLY. Please send email. Appointments will be in 20 minute slots. Multiple people can arrange to see me at the same time if you wish. We will see how this works out.
  • Since we can't have in class exams, all exams will be take home. I will assume I am working with adults in extraordinary times and that students will not share hints or answers.
Recommended 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 (WARNING: THIS HAS NOT BEEN UPDATED)

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 Aug 24 Introduction to the class, what we plan on doing, how the class works, where to find stuff. How is a compiler organized. assignment  
2 Aug 31 Scanners and how they are defined, grammars, intro to flex and bison. Read Chapter 1, assignment 1 Monday is Martin Luther King Day
3 Sep 7 more on scanners, UNIX tools for homework submission, syntactic analysis Read Chapter 2, calculator demo code from this week NO CLASS ON MONDAY - LABOR DAY
4 Sep 14 Context Free Grammar review, Study: A Tutorial on Grammars, Read Chapter 3  
5 Sep 21 First and Follow sets, formal LL(1) development Read Chapter 4, assignment 2 Monday is President's Day
6 Sep 28 various LR parsings and getting bison to build your syntax tree Read Chapter 5  
7 Oct 5 Symbol tables, type checking, and discuss what you need to know to do assignment 3 Read chapter 6 Assignment 3
8 Oct 12 more attribute grammar stuff and answer questions on assignment 3    
9 Oct 19 Attribute grammars and how to finish out our syntax tree Assignment 4  
10 Oct 26 Using the error token in Bison, start looking at the Tiny Virtual Machine   PARSER TEST WEDNESDAY
11 Nov 2 Discuss assignment 4. Study the Tiny machine and memory allocation Assignment 5  
12 Nov 9 More on the virtual machine and assignment 4 Assignment 6  
13 Nov 16 Memory allocation and code generation, extensions to C- that are common in many languages but that we won't actually include. Read Chapter 7  
14 Nov 23   THANKSGIVING BREAK! NO CLASS THIS WEEK!
15 Nov 30 Examples of code generation assignment Assignment 7  
16 Dec 7 Some on record types, object oriented languages, Optimizations in general, local optimizations, code selection, register allocation    
17 Dec 14   FINALS WEEK (NO FINAL FOR US) 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. This is How Testing Works
  • Submitting homework without a browser
  • Computer Science IT FAQ including information on logging onto class machines.
  • The CS445 student machine is called cs-445.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
  •