Compiler Design

CSCI 412, Section 01
Spring Semester 2016

 

Instructor

John I. Moore, Jr. Phone:  843-953-7883
Office:  Thompson Hall 311       E-mail:  john.moore@citadel.edu

 

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: CSCI 223 and CSCI 305

 

Learning Outcomes

Upon successful completion of this course, a student will be able to

 

Compiler References and Websites

  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, ISBN 978-0321486813.
     
  2. The Compiler Generator Coco/R, http://www.ssw.uni-linz.ac.at/Coco/.
     
  3. The LLVM Compiler Infrastructure, http://llvm.org/.
     
  4. [Parr 2010] Terence Parr, Language Implementation Patterns, Pragmatic Bookshelf, 2010, ISBN 978-1934356456.
     
  5. [Parr 2013] Terence Parr, The Definitive ANTLR 4 Reference (Second Edition), Pragmatic Bookshelf, 2013, ISBN 978-1934356999. (See also http://www.antlr.org/.)
     
  6. [Watt 2000] David A. Watt and Deryck F. Brown, Programming Language Processors in Java: Compilers and Interpreters, Prentice Hall, 2000, ISBN 978-0130257864.
     
  7. [Wirth 1996] Niklaus Wirth, Compiler Construction, Addison Wesley, 1996, ISBN 978-0201403534. (Available online at http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf.)

Also:  Course Notes and Handouts

 

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

Monday-Wednesday-Friday, 9:00-9:50 a.m., Thompson Hall 316.
 

Grading

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

 

Miscellaneous Grading Policies

  1. With the exception of the course project, students are required to work individually on all work done outside of class that will be turned in for a grade. For the course project, you may work in teams of two. Assistance from anyone other than the instructor or your team partner (on the course project only) is forbidden.
     
  2. The course project is divided into several progamming assignments, and each programming assignment is due one week after it is assigned unless noted otherwise by the instructor. A late program, for whatever reason, will have its grade lowered by one letter, and programs more than one week late will not be accepted, resulting in a grade of zero for that program. The final course project must be demonstrated during the final exam period. No project will be accepted after the final exam period unless explicitly approved by the instructor.
     
  3. Daily quizzes are usually based directly on the material covered in the previous day’s class.
     
  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 college catalog for policy on incomplete work.

 

Office Hours

Monday 1:00-3:30 p.m.
Wednesday  1:00-3:30 p.m.

Other times by appointment

 

Important Dates

Jan. 18 Martin Luther King, Jr. Holiday (no classes)
Feb. 24 Test #1
Mar. 16 Last day to withdraw with a grade of “W”
Apr. 6 Test #2 (Cumulative)
Mar. 28-Apr. 1 Spring Break (Work on project during break!)
Apr. 28 (Thursday) Final Exam/Project Demonstrations 1:00-4:00 p.m.

 

Expectations

  1. Do not miss an assigned test 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. Cell phones must be kept in book bags and programmed in a silent or vibrate setting during class.
     
  7. 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 handled appropriately.

 

Daily Schedule

Dates Topics Covered
Jan. 13 Overview of Compilers and Language Translation
Jan. 15 Overview of Compilers and Language Translation
 
Jan. 18 Martin Luther King, Jr. Holiday (no classes)
Jan. 20 Structure of Compilers
Jan. 22 Context-Free Grammars
 
Jan. 25 Context-Free Grammars
Jan. 27 Definition of the Programming Language CPRL
Jan. 29 Lexical Analysis (Scanning)
 
Feb. 1 Lexical Analysis (Scanning)
Feb. 3 Lexical Analysis (Scanning)
Feb. 5 Syntax Analysis (Recursive Descent Parsing)
 
Feb. 8 Syntax Analysis (Recursive Descent Parsing)
Feb. 10 Syntax Analysis (Recursive Descent Parsing)
Feb. 12 Syntax Analysis (Recursive Descent Parsing)
 
Feb. 15 Error Handling/Recovery
Feb. 17 Error Handling/Recovery
Feb. 19 Project Discussions/Review
 
Feb. 22 Project Discussions/Review
Feb. 24 Test #1
Feb. 26 Abstract Syntax Trees
 
Feb. 29 Abstract Syntax Trees
Mar. 2 Abstract Syntax Trees
Mar. 4 Abstract Syntax Trees
 
Mar. 7 Constraint Analysis
Mar. 9 Constraint Analysis
Mar. 11 Constraint Analysis
 
Mar. 14 The CPRL Virtual Machine
Mar. 16 Code Generation
Mar. 18 Code Generation
 
Mar. 21 Code Generation
Mar. 23 Code Generation
Mar. 25 Optimization
 
Mar. 28-Apr. 1 Spring Break (Work on project during break!)
 
Apr. 4 Project Discussions/Review
Apr. 6 Test #2 (Cumulative)
Apr. 8 Implementing Procedures and Functions
 
Apr. 11 Implementing Procedures and Functions
Apr. 13 Implementing Procedures and Functions
Apr. 15 Implementing Procedures and Functions
 
Apr. 18 Implementing Arrays
Apr. 20 Implementing Arrays
Apr. 22 Project Discussions
 
Apr. 25 Project Discussions/Course Evaluations
 
Apr. 28 (Thursday) Final Exam/Project Demonstrations 1:00-4:00 p.m.