Objectives and Expectations

The goal of this course is to become proficient with compiler theory and its practical applications. By the end of the course, you should be able to do the following:

  • Describe and compare classes of formal languages, including regular and context-free languages. Use regular expressions and Backus-Naur grammars to describe languages. Apply common grammar transformations such as left factoring and the elimination of ambiguity and left recursion.
  • Describe and build examples of formal automata, including deterministic and non-deterministic finite automata as well as pushdown automata.
  • Compare and implement various parsing approaches, including LL(1), LR(0), LR(1), and LALR.
  • Use practical compiler-generation tools such as lex/flex and yacc/bison.
  • Distinguish between front-end and back-end compiler components and justify the use of various intermediate code structures.
  • Describe the role of abstract syntax trees and syntax-directed compilation. Give examples of useful intermediate tree tranformations. Build and analyze basic blocks and control/data flow graphs.
  • Describe type systems and how they help with automated program translation, including the concept of type polymorphism. Explain the challenges of implementing an object-oriented language.
  • Discuss practical issues of language runtime implementation, including memory allocation and garbage collection.
  • Describe common code optimizations, including redundancy reduction, instruction-level parallelism, scheduling, and locality optimization.
  • Explain the issues involved in generating helpful compiler error messages.

Course Textbook

Compilers: Principles, Techniques, and Tools (2nd Edition)
Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman
Errata (latest) and Errata (pre-2008)

This book is without a doubt the single most famous textbook on compilers. Originally published in the mid 1980's by Aho, Sethi, and Ullman, we will be using the 2006 revision, created with the assistance of Monica Lam. The book includes extensive coverage of nearly all of the topics we will will be discussing this semester: lexical analysis, parsing, syntax-directed compilation, code generation, optimization, and parallelism.

We will also be reading papers and other supplemental materials as appropriate for topics not fully covered by the textbook, such as type systems, security issues, and other recent compiler research topics.

Textbook Cover

Grading Criteria

You are responsible for all material discussed in lecture and discussion section and posted on the class web page, including announcements, deadlines, policies, etc.

Your final course grade will be determined according to the following percentages:

Discussions 10%
Programming Projects 45%
Midterm Exams 30%
Final Exam 15%

Because the class size is small, this course will be seminar-style. I will lead discussions, not give lectures. This should optimize the utility of class time by allowing us to focus on the areas of knowledge that need the most attention for the individuals in the class. You are expected to come to class prepared to discuss the material scheduled for that day. You do not need to have mastered the material, but you should have a solid grasp of the basics and be ready to ask questions about the parts you do not fully understand. A portion of your final grade will be based on my observation of your diligence in preparing for class discussions.

If you believe I have made an error while grading your work or calculating your final score on an assignment, please bring it to my attention after class or during office hours. If I determine that there has been a simple mistake, I will fix it immediately and no formal request is necessary.

If you believe an exam question or assignment has been graded unfairly, you must submit a verbal or written formal request for a regrade. Such requests must be submitted within one week of when the assignment in question is returned to you. Any coursework submitted for reconsideration may be regraded in its entirety, which could result in a lower score if warranted.

Completing the programming assignments is an essential part of the course. Therefore, I reserve the right to fail any student who does not make a good-faith attempt on all course projects, regardless of the student's performance or scores on the other coursework.

Final course letter grades may be curved if necessary at the end of the semester, based on each student's overall performance for all coursework.

Instructor Contact Info

My email is lam2mo at the standard domain. My office is in ISAT 227, and my office hours are posted on the main course page. I am also frequently available by appointment outside posted hours; please email me to confirm my availability.

Course Policies

Important announcements will be made in class and/or on the class website. Please make it a habit to check the web page daily.

Although every effort has been made to be complete and accurate, unforeseen circumstances arising during the semester could require the adjustment of any material given here. Consequently, given due notice to students, I reserve the right to change any information on this syllabus or in other course materials.

You are permitted to use course materials for your own personal use only. Course materials may not be distributed publicly or provided to others (excepting other students in the course), in any way or format unless explicitly allowed.

Attendance and Participation

Attendance is not mandatory, and I will not give grades purely based on attendance. I view my students' time as valuable, and my goal as a teacher is to make class attendance and participation well worth the time investment for you. I strongly encourage you to attend every class session and participate fully in order to derive the maximum benefit of this course. If you believe that there is something I could change about the way I am handling the course in order to improve its effectiveness for you, please let me know via email or office hours.

You should also be aware that I do occasionally give graded quizzes or graded group work assignments during class periods. In some cases, I will notify you in advance about these quizzes or assignments, but I do reserve the right to administer them unannounced at my discretion.

Please silence your cell phone while class is in session. If you have a laptop or tablet, you are encouraged to bring it to class and use it to work along with programming examples and exercises. Mute the volume to avoid unintended interruptions, and do not use any electronic devices for activities that may distract other students. Repeated violations of this policy may result in disciplinary action or a grade penalty in the course.

I strongly encourage you to check the main website regularly for important announcements (usually regarding programming projects). You may also use the Canvas forum to ask general questions of interest to the class as a whole (e.g., administrative issues or project clarification questions) as well as to offer each other general advice on class assignments. However, do not post any information that would violate the university academic integrity policy. If you are unsure about this, please email me for approval before you post.

Programming Projects

Projects must be submitted electronically following the instructions given in class and on the website. Projects may not be submitted by any other means (e.g., do not email your projects to me unless I request that). It is your responsibility to test your program and verify that it works properly before submitting it.

All projects are due at 23:59 (11:59pm) on the day indicated on the project assignment unless noted otherwise.

Projects may be submitted up to 72 hours late for a 10% penalty per 24-hour period. For example, a submission that would have earned 90 points in an on-time submission will earn 90 x 0.90 = 81 points if submitted up to 24 hours late, or 90 x 0.80 = 72 points if submitted up to 48 hours late. If you make multiple submissions, I will typically grade the latest submission. If you wish me to grade a different submission, you must indicate this before the 72-hour late period is over.

Regardless of the above policy, I reserve the right to refuse to grade any projects submitted after the beginning of the second class period following the project deadline, because I may discuss the solution in class.

Project extensions will not necessarily be granted due to server congestion, system problems, network problems, power outages, etc., so do not wait to submit a project until the night it is due. No consideration in grading will be made for errors made in transferring files or submitting the wrong version of your project. Having a working, non-submitted version will not count; only submitted code will be be counted.

You will be responsible for developing your own techniques for testing your projects before submitting it. I will grade your projects based on test cases not provided to you in advance. Because grading may be done automatically, you must follow the project specification exactly.

Your code will be graded on a combination of correctness, completeness, documentation, and code style.

Any "hard coding" in a project assignment will result in a score of zero for that project, and is considered a bad-faith effort. Hard coding refers to attempting to make a program appear as if it works correctly, when in fact it does not. One example of hard coding would be printing the desired output instead of computing it. If you have any questions as to what constitutes hard coding for a particular assignment, be sure to ask ahead of time.

Adding and Dropping the Course

Students are responsible for adding and dropping courses. Please consult the appropriate academic calendar for the exact deadlines. I will not give "WP" or "WF" grades to students requesting a drop after the deadline except in extraordinary circumstances.

Academic Honesty

You are expected to comply with the JMU Honor Code as stated in the Student Handbook and available from the Honor Council website on all assignments, projects, and exams.

Consulting with other students about problems and solutions is not necessarily a violation of the honor code, depending on the particular assignment. All final work turned in for an assignment must be your own unless it is a group project. In particular, you may not share source or binary code on programming assignments unless the project specification explicitly allows it. If you are in doubt about whether something is an honor code violation, please contact me immediately.

If I find evidence of a violation of the honor code, I will bring the matter to the attention of the involved individuals via email and request a face-to-face meeting. As per section IV of the honor code, first time student offenders may agree that a violation has occurred and accept an appropriate penalty by submitting an "Informal Resolution Agreement Form" to the honor council. If the student is not a first-time offender or if there is disagreement about the violation or penalty, the matter will be refered to the honor council under section V of the honor code.

Disability Accommodations

If you need an accommodation based on the impact of a disability, you must contact the Office of Disability Services if you have not previously done so. Disability Services will provide you with an Access Plan letter that will verify your need for services and make recommendations for accommodations to be used in the classroom. Once you have shown me this letter, we will sit down and review the course requirements, your disability characteristics, and your requested accommodations to develop an individualized plan appropriate for this course. I will not make any accommodations without the appropriate documentation, as I am not qualified to diagnose disabilities.

Excused Absences

Besides the policies in this syllabus, the University's policies apply during the semester. Various policies that may be relevant appear in the Undergraduate Catalog.

Excused absences will be granted at my discretion and only with appropriate documentation. Please contact me as soon as possible if you wish to request an excused absence.

Missing an exam for reasons such as illness, religious observance, participation in required university activities, or family or personal emergency (such as a serious automobile accident or the funeral of a close relative) all are circumstances that may qualify as an excused absence. However, you must provide documentation that the absence qualifies as excused. I will arrange a makeup exam or substitute assignment at my discretion.

The policies for excused absences do not apply to in-class activities (which cannot be made up) or project assignments. Projects will be assigned with sufficient time to be completed by students who have a reasonable understanding of the necessary material and begin promptly. In cases of extremely serious documented illness of lengthy duration or other protracted, severe emergency situations, I may consider extensions on project assignments depending upon the specific circumstances. Please contact me as early as possible if you believe you will need such an extension.

Inclement Weather

This class will operate in accord with JMU's official cancellation policy.

Catalog Description

This course teaches an introduction to the theory of grammars and the mathematical foundations of compilers along with the practical considerations for developing them. The course covers practical aspects of all phases of the compilation process including lexical analysis, parsing, code generation, and code optimization. Students develop a compiler for a small grammar using the appropriate techniques.

Prerequisites: None

Sections: 0001
Instructor: Dr. Mike Lam
Credits: 3