Course Information

Course information from your instructor

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

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

Class URL:	`http://www.cs.wustl.edu/~cytron/cse431/`
Lecture	McMillan G052, 4-5:30 PM, Monday and Wednesday I do not take attendance, but you are responsible for all material presented in class, and I do not generally follow a script or textbook.
Instructor:	Ron Cytron (cytron@wustl.edu)
	Office	304 Jolley
	Phone	935-7527
	Office Hours	Monday and Wednesday, 3-4 PM walk-in, or by appointment
Assistant:	Tyler Reeves (tyler418@gmail.com)
	Office	Urbauer 222
	Contact	Use piazza
	Office Hours	TBA
Textbook, available in the campus bookstore:	Fischer, Cytron, and LeBlanc, Crafting a Compiler, 2010
Alternate textbook	Aho, Lam, Sethi, Ullman: Compilers: principles, techniques, and tools, Second Edition, Addison-Wesley, 2007 (affectionately called "The Dragon Book")
The library will have on reserve a copy of the notes from which I lecture (400 pages).	Other material may be distributed as needed.
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 programming tools, including JFlex and JavaCUP will be available online.	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.
Collaboration details for this course can be found here. 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 committing and pushing them, per instructions given on the assignment.

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 committed and pushed in your repository, 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%

Machine Problems: 45% Six machine problems will be assigned. Four of these contribute directly to the final project.

Final Project: 10% 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 CSE431.

Course Participation: 5% If we do the studio style meetings this semester, then this part of your grade will be determined from your consistent participation in studio. Otherwise, it will be based on participation in class.

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.

Outline

Introduction.
A simple translation system
- Grammars
- Derivation trees
Deterministic finite state automata
- Right-linear grammars
- CUP/YACC
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.
- JFlex/LEX
Pumping lemma for regular languages.
Context-free grammars and ambiguity
Recognition by Recursive Descent
- First and Follow sets
- Error recover and repair
LL(1) parsers.
LR parsing
- Shift-reduce parsing
- Synthesized attributes
- YACC revisited.
Symbol Tables
Operator precedence parsing
LR(k) parsing
- LR(0)
- SLR(1)
Abstract Syntax trees
LR(k) parsing continued
- LR(1)
- LALR(1)
- LR(1)
- Incremental parsing
Semantic processing
- Type checking
- Type conversion
- Attribute grammars
- Practical methods
Run-time environments
- Libraries
- Activation records
Code generation
Storage management
- Storage allocation
- Accessing nonlocals
- Garbage collection
Program optimization

Last modified 08:48:02 CST 18 January 2017 by Ron K. Cytron

Any assignment turned in for this couse is subject to the students' statement of academic integrity. Collaboration details for this course can be found here. 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 committing and pushing them, per instructions given on the assignment. 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 committed and pushed in your repository, 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%
Machine Problems:	45%	Six machine problems will be assigned. Four of these contribute directly to the final project.
Final Project:	10%	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 CSE431.
Course Participation:	5%	If we do the studio style meetings this semester, then this part of your grade will be determined from your consistent participation in studio. Otherwise, it will be based on participation in class.
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.

CSE 431S (Spring 2017)