Compiler Design

CSCI 412, Section 01
Spring Semester 2007

Instructor

Course Description

This course explores the basic principles, algorithms, data structures, and tools involved in the design and construction of compilers. Topics include formal grammars, lexical analysis, parsing algorithms, semantic analysis, error recovery, code generation, and optimization. Each student will be required to complete a substantial programming project, the implementation of a compiler for a small programming language.

Prerequisite

Formal Prerequisite: CSCI 355

Informal Prerequisite: Strong background in data structures, algorithms, basic software engineering concepts, and both high-level and low-level programming languages. If you have mastered the concepts in both CSCI 305 (Computer Organization and Programming) and CSCI 223 (Data Structures and Algorithms), you should be able to perform well in this course.

Learning Outcomes

Upon successful completion of this course, a student will

• Understand the formalisms and techniques used in the specification of programming languages (regular expressions, context-free grammars, contextual constraints, etc.)
• Be able to analyze context-free grammars to compute first and follow sets
• Understand the basic structure of a compiler in terms of its functional components (lexical analysis, syntax analysis, semantic analysis, error handling/recovery, code generation, and optimization)
• Have completed a major programming project, the design, implementation, and testing of a compiler for a small programming language
• Have gained a deeper understanding of the basic principles of software design and object-oriented programming

Textbook

David A. Watt and Deryck F. Brown, Programming Language Processors in Java: Compilers and Interpreters, Prentice Hall, 2000.

Also:  Course Notes and Handouts

Compiler References

1. [Aho 2006] Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, And Tools (Second Edition – a.k.a. Purple Dragon), Addison Wesley, 2006.
    
2. [Appel 2002] Andrew W. Appel, Modern Compiler Implementation in Java (Second Edition), Cambridge University Press, 2002.
    
3. [Brinch Hansen 1985] Per Brinch Hansen, Brinch Hansen on Pascal Compilers, Prentice-Hall, 1985.
    
4. [Elder 1994] John Elder, Compiler Construction: A Recursive Descent Model, Prentice-Hall, 1994.
    
5. [Mak 1996] Ronald Mak, Writing Compilers and Interpreters: An Applied Approach Using C++ (Second Edition), John Wiley & Sons, 1996.
    
6. [Wirth 1996] Niklaus Wirth, Compiler Construction, Addison Wesley, 1996. (available online at http://www.oberon.ethz.ch/WirthPubl/CBEAll.pdf)

Programming Project

This course requires that each student complete a major programming project, the design and implementation of a small compiler. The project will be graded primarily on completeness and correctness, but other factors such as overall design and structure will also affect your project grade. The project must be demonstrated during the time period allocated for the final exam. More details on the grading criteria for the project will be discussed in class as the course progresses.

Class Schedule

MWF 9:00-9:50, Thompson Hall 216.

Grading

The final grade for the course is based on 5 grades as follows:

• Two assigned in-class tests. Each test counts as a separate grade.
• Daily quizzes and minor assignments – collectively count as 1 grade.
  (Lowest two quiz grades will be dropped.)
• Programming project – counts as 3 grades.
• Lowest grade from above 6 grades will be dropped. If the lowest grade is the programming project, only one of the three grades will be dropped.

Miscellaneous Grading Policies

1. Students are required to work individually or with approved team members on all work done outside of class. Assistance from anyone other than the instructor, a librarian, the writing center staff, or an approved team member is forbidden.
    
2. Daily quizzes will come directly from the material covered in the previous day's class.
    
3. Homework will be assigned but not collected; however, daily quizzes will often be based on homework assignments.
    
4. Class attendance and participation can influence borderline grades.
    
5. A total of nine absences will result in a course grade of F. With respect to this policy, three lates count as an absence. In addition, if you are late by 15 minutes or more, you will be considered absent.
    
6. Incomplete grades are given only in unusual circumstances. Consult the catalog for policy on incomplete work.

Office Hours

Other times by appointment

Important Dates

Expectations

1. Do not miss the assigned tests without a valid excuse! Missing an assigned test without a valid excuse will result in a grade of zero for that test. The instructor gets to determine whether or not an excuse is valid. In particular, guard duty is not an acceptable excuse for missing an assigned test. When possible, students should notify the instructor in advance if they will be unable to take an assigned test. All make-up tests will be given outside of normal class time. Once a test has been given in class, any subsequent make-up tests may differ significantly.
    
2. Show up for class on time and prepared. That means that you have read the appropriate sections from the book plus any handouts, and you have worked all assigned homework. If a test has been assigned, you should be prepared to take the test. If you were late to class or absent from the previous class meeting, you are responsible for getting class notes and assignments from another student in the class or from the instructor.
    
3. If you are late to class, it is possible that you have already been marked absent by the time you arrive. It is your responsibility to notify the instructor after class that you were late rather than absent.
    
4. Take care of any personal needs outside of class time. Except for emergencies, you should not need to go to the bathroom, get a drink of water, etc. If you need to leave the room at any time while class is in session, you should ask for permission.
    
5. There should be no personal conversations or moving around during class without explicit permission. These actions are disturbing to other students and to the instructor. Be courteous and respect the rights of others.
    
6. You should respect the property of your college. No eating, drinking (other than water), smoking, dipping, chewing tobacco, etc. in the classrooms. Also, no writing or carving on the desks, chairs, podium, etc. Any willful vandalism or destruction of Citadel property will be dealt with severely.

Daily Schedule