Philosophy

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.

Oveview

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