Course information from your instructor

Quick picks: [ philosophy ] [ overview ] [ outline ]


Compilers and their construction are a core discipline in computer science, melding an exciting theory of language recognition and computability with a compelling practical application. Although the term compiler is most often applied to a computer program that converts a high-level programming language into machine instructions for a target platform, the term more generally denotes the transformation of one language (or its representation) into another.

This course aims to give you a solid foundation in the theory of compiler construction as well as the experience of building a compiler. Much of what you have learned about algorithms and data structures will come to bear as you study and implement the various components of a compiler. In a sense, compiler construction is a showcase for many other disciplines of computer science.


Class URL:
Class news group: news://
Lecture Lopata 101, 4-5:30 PM, Tuesday and Thursday

Attendance is not mandatory; however, you are responsible for all material presented in class, and I do not generally follow a script.

Instructor: Ron Cytron (
Office 525 Bryan
Phone 935-7527
Office Hours Tuesday and Thursday, 3-4 PM
walk-in, or by appointment
Assistant: Nicholas Calugar (
Office Graders' Office (Lopata 406)
Phone 5-5044
Office Hours TBD
Assistant: Cheryl Barkauskas (
Office Graders' Office (Lopata 406)
Phone 5-5044
Office Hours TBD
Assistant: Christopher Hill (
Office Graders' Office (Lopata 406)
Phone 5-5044
Office Hours TBD
Assistant: David Warner (
Office Graders' Office (Lopata 406)
Phone 5-5044
Office Hours TBD
Assistant: Nicholas Webb (
Office Graders' Office (Lopata 406)
Phone 5-5044
Office Hours TBD
Textbook, available in the campus bookstore: Fischer and LeBlanc: Crafting a Compiler with C, Benjamin/Cummings, 1991.
The library will have on reserve a copy of the notes from which I lecture (400 pages). I will also hand out chapters from Crafting a Compiler, Second Edition by Charles Fischer, Ron K. Cytron, and Richard LeBlanc, to be published by Addison Wesley Longman.
Supplementary notes (164 pages) are available online. Cytron: Compiler Construction PLDI Tutorial Notes, 1994.
Other references:

I will loan these out overnight until a week before an exam, when they will be placed in the library for two-hour checkout.

Information on UNIX programming tools, including JLex and JavaCUP will be available online.

  • Aho, Sethi, Ullman: Compilers: principles, techniques, and tools, Addison-Wesley, 1988 (affectionately called "The Dragon Book").
  • Waite and Goos: Compiler Construction, Springer-Verlag, 1984.
  • Bauer and Eickel: Compiler Construction: An Advanced Course, Springer-Verlag, 1976.
  • Waite and Carter: An Introduction to Compiler Construction, HarperCollins, 1993.
  • Wirth: Algorithms + Data Structures = Programs, Prentice-Hall, 1976.
  • Hopcroft and Ullman: Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
  • Aho and Ullman: The Theory of Parsing, Translation, and Compiling (two volumes), Prentice-Hall, 1973.

Any assignment turned in for this couse is subject to the students' statement of academic integrity. Honor and integrity rank prominently among the essential attributes of a scholar.
Anyone found cheating on any assignment will receive an "F" for this course; other actions may be taken.

On the date that an assignment is due, said assignment must be submitted by the beginning of class.

  • For paper products, turn in such assignments in class.
  • For software and other such products, turn these in by e-mailing them to cs431@cec, also by the beginning of class. Instructions for e-mailing software are given with each machine problem handout.

15-minute service guarantee: Should you run into trouble while working on a machine problem, I offer you the following guarantee. Within 15 minutes of my receiving a complete description of your problem, by e-mail or in person, I promise to have your problem solved, or you get a small (but nourishing) package of M&Ms.

Lateness policy: Assignments are due as advertised; late work is not accepted.

Exam 1 20% There will be two in-class exams. Although books and notes may be used, all work turned in must be done in-class. Extra-credit earned on the final project may be applied to any exam grade.
Exam 2 20%
Quizzes: 20% On the class prior to a quiz date, 6 questions will be published. On the quiz date, one of these questions will be given as a ten-minute, in-class, closed-book quiz, with the question chosen by throw of a die.

Ten such quizzes are planned for this semester. All quizzes count equally, and no quiz grade will be dropped.

Machine Problems: 20% Six machine problems will be assigned. Four of these contribute directly to the final project.
Final Project: 20% Our project involves the translation of a Java-like language into a high-level interpretable language. This project emphasizes syntactic and semantic analysis, symbol table management, and straightforward code generation.

The final project is graded on code quality, correctness of translation, and documentation. Your code is expected to be reasonably written, documented, and tested, in a manner that brings honor to CS431.

Stock solutions for the four machine problems contributing to the final project will be made available. Students who do not earn a "B" or better on the relevant machine problems are expected to make up this deficiency by extra credit on the final project.


  1. Introduction.
  2. A simple translation system
    • Grammars
    • Derivation trees
  3. Deterministic finite state automata
    • Right-linear grammars
    • YACC
  4. Finite state automata and Regular Expressions
    • Transforming a regular expression into NFA
    • Eliminating e-moves from NFA
    • Transformation into DFA
    • Table-based DFA simulation
    • Mininimizing DFA
    • Transforming FSA into a regular expression.
    • LEX
  5. Pumping lemma for regular languages.
  6. Context-free grammars and ambiguity
  7. Recognition by Recursive Descent
    • First and Follow sets
    • Error recover and repair
  8. LL(1) parsers.
  9. LR parsing
    • Shift-reduce parsing
    • Synthesized attributes
    • YACC revisited.
  10. Symbol Tables
  11. Operator precedence parsing
  12. LR(k) parsing
    • LR(0)
    • SLR(1)
  13. Abstract Syntax trees
  14. LR(k) parsing continued
    • LR(1)
    • LALR(1)
    • LR(1)
    • Incremental parsing
  15. Semantic processing
    • Type checking
    • Type conversion
    • Attribute grammars
    • Practical methods
  16. Run-time environments
    • Libraries
    • Activation records
  17. Code generation
  18. Storage management
    • Storage allocation
    • Accessing nonlocals
    • Garbage collection
  19. Program optimization

Last modified 09:59:23 CST 08 January 2002 by
Ron K. Cytron