CS 4240

Compilers, Interpreters and Program Analyzers

Fall 1999

Contact information Grading Assignments Readings and Lecture Schedule Examples

Recent Changes

The final exam I used in CS 4410 course last year now available (CS4410 final).  We have covered more material in a semester than I could in a quarter, so the things we have studied in the last few weeks are not included.  In particular, here are some suggested exercises from chapters 6 and 16 that will help you prepare for the final:

Chapter 6: exercises 4, 5, 6, 14, 19, 38 and as much of 39-42 as you find usefil/interesting.

Chapter 16: exercises 9, 12 and 20.

Contact Information

The course instructor is Richard LeBlanc (rich@cc).

The course TA is Brian McNamara (lorgon@cc). I have no official office hours; mail me to set up appointments to meet.

The course newsgroup is git.cc.class.cs4240.

Lecture meets T/Th at 3:00 in room 519 of the Mason (CE) building.
 
 

Course Description

 
As a 4000-level course, Compilers, Interpreters and Program Analyzers is offered primarily for seniors and graduate students. For undergraduates majoring in Computer Science, this course is part of the Computer Systems area of specialization. For graduate students without any preparation in the compiler area, it serves as a prerequisite to several advanced courses.
Compiler courses have long been part of computer science curricula. The area attracts a broad group of computer scientists. It is an area of great practical importance, since most of us use compilers or software products that depend on them every day. Building a compiler is a significant, yet tractable, challenge to programming skills, so it is a very good educational exercise. Finally, compilers provide one of the foremost examples of the application of theory to practice in computer science, since regular and context-free languages are commonly used to specify the syntax of programming languages and syntax analyzers based on finite state and push-down automata can be (and commonly are) automatically generated from these specifications. Other parts of a compiler make extensive use of lists, trees and graphs, thus providing students with an opportunity to display or develop their skills with data structures. Thus a compiler course frequently serves a "capstone" course role in a curriculum, demanding that a student exhibit knowledge and skills gained through many previous courses.
Compilers literally perform a translation task, typically converting a program in a programming language to an equivalent program in assembly or machine language. However, the techniques involved can generally be seen as useful for translating from any well-defined input language to a well-specified target language.

What's New This Term?

The basics of compiler technology have very broad applicability in the implementation of software systems. As the title suggests, the course will cover a broader set of topics that just compilers. Rather, we will look at how the same underlying technology provides the basis for a variety of programmming tools, including compilers, interpreters, and preprocessors, as well as for tools that might analyze the structure of or somehow transform a source program. A ten-week quarter barely provided time to look at the material in the course from a compiler perspective. The additional time available in a semester will allow us to look at a few compiler topics more thoroughly, as well as to expand our perspective to the whole range of tools discused above.

Teaching Approach

A fundamental goal of the course is for you to learn to use a large number of algorithms and general techniques drawn from the field of compiler construction. Since I have stated the goal in terms of your learning to use these algorithms and techniques rather than just learning about them, it should be clear that more is intended than just memorization. Thus a major component of the learning experience presented by this course will be a number of assignments involving the construction of components of a compiler, interpreter and/or program analysis tool. Through these assignments, you will learn about the relevant algorithms, techniques and tools by employing them in the implementation of working programs.
The assignments mentioned above may be done individually or in groups of two students. In either case, you are encouraged to interact with one another in the course of your project work. A number of the assignments will involve you doing extensions to some code that will be provided to you. I want you to feel free to work together on understanding the code provided to you and on developing strategies for extending it to implement the requirements of the assignments..

Teaching/Learning Goals for the Course

I expect you to have the following knowledge and skills as prerequisites to this course:
  1. exposure to regular expressions and finite automata;
  2. exposure to context-free languages, BNF, derivations, and parse trees;
  3. understanding of programming language concepts underlying languages from the Algol family (such as Pascal, C and Ada);
  4. ability to use data structures such as binary trees, hash tables and arbitrary graph structures;
  5. ability to understand a large Java or C++ program and to extend it.
The primary goals of this course are for you to develop the following abilities:
  1. to describe basic compiler, interpreter and program analysis architectures and their variants;
  2. to apply common syntax analysis algorithms;
  3. to demonstrate understanding of techniques for interpreting or compiling simple programming language features;
  4. to integrate these techniques in a working interpreter or compiler;
  5. to use concepts from basic analysis, interpretation and compilation techniques in new contexts;
  6. to comprehend and utilize a variety of program analysis tools.

Teaching Methods and Learning Activities

Course Design
Class meeting will be devoted mainly to lectures about the information content of the course, thus primarily supporting goals 1, 2, 3 and, to a limited extent, 5. Some class time will be used to provide an overview of code given to you as part of assignments. Time at the beginning of many class periods during the course will be used to answer project-related questions or to explain to the whole class answers to questions asked directly to me or to the TA outside of class (supporting goals 4 and 6).
The compiler project work itself is the most direct means by which you are intended to achieve goals 4 and 6 and to demonstrate the learning required by goals 2 and 3.
Structure of the Subject Matter
During the introductory lecture, idealized architectures for compilers, interpreters and program analyzers will be presented, identifying six major compiler components (scanner, parser, semantic processor, symbol table manager, optimizer, and code generator). Throughout this course, the subject matter is organized in relation to these components and their interactions. The lectures tend to focus on techniques that fit within a particular component, while the project work emphasizes the integration of techniques within and across components.
My Role as a Learning Facilitator
Because of the high information content of this course, most of the class time will be spent on lectures and answering questions. Lecture will include explanations of algorithms and techniques (reiterating material from the text) and demonstrations of their dynamic behavior. Question answering sessions will be intended to provide assistance with the assignments by addressing difficulties that arise as in the course of student implementation work. Project assistance will also be provided outside of class via office hours and electronic communication.
Evaluation/Assessment of Student Learning
Because of the large amount of material covered in the course, the course schedule will include two exams during the semester plus a final exam at the regularly scheduled period. These exams will be oriented toward assessment of your performance relative to goals 1, 2, 3, and 5.
The assignments require integration of many techniques that are presented all through the quarter, though the individual assignments will tend to focus on one particular component. The total experience is intended to support learning goals 2, 3, 4, and 6.
Final assessment of each your implementation work will include an interview at end of the term. In this interview, you will present the results of your work and answer questions about the assignments. The intent of these interviews is to assess your accomplishments relative to goals 4 and 5. 

Grading

Final grades will be based on the weighting given below, unless the average of your exam grades differs from your project grade by two or more letters. This exceptional case can happen for one of two reasons: (1) a student does reasonably well on exams but makes little or no effort toward completing the most challenging assignments (3 & 4) or (2) a student turns in terrific assignments but fails to show even a vaguely equivalent mastery of the material on the exams. In either of these situations, I reserve the right to assign a final grade that I judge to reflect your accomplishments relative to all of the learning objectives of the course.
Graduating seniors:
Graduating seniors will be required to submit a special assignment instead of taking a final exam.  The assignment is to make up what you consider to be a good final exam for the course and answer it.  The assignment will be graded on the quality of the questions rather than the correctness of your answers (since the correctness part should be simple!)  Rather than give you a letter grade on this assignment, I will assign a grade of plus, munis, or no change.  The actions described by this grade will be applied to the letter grade you earn for the rest of your work in the course.  The weighting of course work for this purpose will be:
 
 
Finally, incompletes will be given only in truly exceptional circumstances, not simply because you have not managed to get the work done.

Readings and Lecture Schedule

Text:    Crafting a Compiler, 2nd Edition (manuscript) Fischer, LeBlanc and Cytron (Benjamin/Cummings, 2000).
 
Other Readings:

Slides Used in Lectures

Assignments

Click here for information about online submissons.

Homework

Project Assignments

Examples

Last updated on Mon Nov 15 12:47:43 EST 1999 by Brian McNamara