Syllabus and general information for MCS-388: Compiler Design (Spring 2014)

Overview

MCS-388 draws together the theory and practice of compiler construction. Much of the material will have a strong theoretical foundation. However, with the exception of the last couple topics (due to time constraints), this material will also serve as the basis for compiler-writing projects. Topics include lexical and syntactic analysis, code generation, data-flow analysis, and optimization.

Office hours

I welcome visitors to my office (OHS 306) on a drop-in basis as well as by appointment. You may send me electronic mail at max@gustavus.edu.

World Wide Web

All course materials will be available through my World Wide Web page. The URL for this course is https://gustavus.edu/+max/courses/S2014/MCS-388/. After this syllabus I will give hardcopy handouts only to those students who ask for them.

Prerequisites

MCS-388 draws heavily on MCS-265, MCS-287, and MCS-284. Some notions from MCS-375 and MCS-236 also crop up. You're expected to be able to program. Since the compiler-building tools and pre-existing code modules I supply will be centered around the Java programming language, the path of least resistance will be to use that language. On the other hand, there are comparable compiler-building tools centered around other languages, so if you would rather use another language, that's fine too; you'll just have less of a support network. I'll gladly accept labs written in any programming language.

Text and readings

Our primary text will be the "dragon book," i.e., Compilers: Principles Techniques and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, 2nd ed., 2007. When appropriate, I will also distribute supplemental reading.

Labs

Some days, shown in the schedule, we will will work on lab projects using laptop computers in our normal classroom. I expect each of you to bring a computer. Let me know if you need to sign out one from the department. Each lab assignment will generally require you to spend additional time out of class.

Honor

You are expected to be familiar with the college academic honesty honor code policy, and to comply with that policy. If you have any questions about it, please ask.

In doing an assignment, you may discuss the problems and their solutions with fellow students, but you should make an effort to solve each problem on your own. Give credit to the people and/or reading sources that help you find the solutions, be they fellow students, textbooks, journals, or internet postings. Be explicit and acknowledge clearly what sort of help you received. Failure to do so will be considered cheating.

Late assignments

All lab assignments are due at the beginning of class on the day indicated. Late lab assignments will be penalized by one "grade notch" (such as A to A- or A- to B+) for each weekday late or fraction thereof.

If you are too sick to complete an assignment on time, you will not be penalized. Simply label your assignment as late due to illness. Other circumstances will be evaluated on a case-by-case basis.

Please see the separate homework policy linked to the web version of this syllabus.

Grade changes

Please point out any arithmetic or clerical error I make in grading, and I will gladly fix it. You may also request reconsideration if I have been especially unjust.

Grading

I will provide you with a grade on each homework assignment and lab assignment, in addition to the mid-term and final grades, so that you may keep track of your performance. The homeworks will contribute half of your final grade with the labs contributing the other half. However, I reserve the right to subjectively adjust your final grade. Please see me if you have any question how you stand. Class participation is not graded; however, it allows you to find and repair the gaps in your understanding before doing the assignments and thus can dramatically improve your grade. You are responsible for all course material, whether or not you are present when it was covered or distributed.

Please see the separate homework policy linked to the web version of this syllabus.

Style guidelines

All assignments should be readily readable and should not presuppose that I already know what you are trying to say. Use full English sentences and clear diagrams, programs, etc. Remember that your goal is to communicate clearly and that the appearance of these technical items plays a role in this communication process. I encourage email submission but will accept hardcopy assignments that are stapled together and have your name on them.

Accessibility

Gustavus Adolphus College is committed to ensuring the full participation of all students in its programs. If you have a documented disability (or you think you may have a disability of any nature) and, as a result, need reasonable academic accommodation to participate in class, take tests or benefit from the College’s services, then you should speak with the Disability Services staff for a confidential discussion of your needs and appropriate plans. Course requirements cannot be waived, but reasonable accommodations may be provided based on disability documentation and course outcomes. Accommodations cannot be made retroactively; therefore, to maximize your academic success at Gustavus, please contact Disability Services as early as possible. Disability Services is located in the Academic Support Center

Support for English Learners and Multilingual students is available through the Academic Support Center and the English Learning Specialist, Laura Lindell (llindell@gustavus.edu or x7197). If you fall into one of these categories, she can meet individually with you for tutoring in writing, consulting about academic tasks, and helping you connect with the College’s support systems. In addition, you can seek help from peer tutors in the Writing Center. Please let me know if there is any accommodation in the course that would enable you to more fully show your abilities.

Schedule

In the reading column, section 0 means the material at the beginning of a chapter before the first section. Similarly, subsection 0 means the material at the beginning of a section before the first subsection.

This is my best guess as to the rate at which we will cover material. However, don't be shocked if I have to revise the schedule.

DateReadingTopicDue
2/101Introduction
2/122.2Syntax definition
2/132.3-2.4Syntax-directed translation
2/14Lab 1: Generating Code from ASTs

2/173.0-3.1, 3.3, 3.5Lexical analysis
2/194.0-4.2Context-free grammarsHW 1
2/20Lab 1 (continued)
2/21(Weather-related cancellation)

2/244.3Writing a grammar
2/264.4.0-4.4.3Top-down parsingHW 1 rewrite
2/274.4.4-4.4.5More on predictive parsing
2/284.5Bottom-up parsing

3/34.6SLR parser generationHW 2
3/54.7.0-4.7.4Canonical LR and LALR parser generationLab 1
3/64.8-4.9Using ambiguous grammars; parser generators
3/75.0-5.4.3Syntax-directed definitions

3/10Lab 2: Scanning and Parsing
3/12Lab 2 (continued)HW 2 rewrite, HW 3
3/13Lab 2 (continued)
3/146.0-6.2Intermediate code

3/176.4, 6.5.2Array access; type conversionsLab 2
3/19No class (Amcom trip)
3/206.6Control flowHW 3 rewrite
3/21Lab 3: Adding VariablesHW 4

3/24Lab 3 (continued)
3/26Lab 3 (continued)
3/27Lab 3 (continued)
3/288.0-8.3Code generation

4/78.4Basic blocks and flow graphsLab 3, HW 4 rewrite
4/9Preview of lab 4
4/10Lab 4: Control Flow and Scoping
4/119.0-9.1Optimization

4/14Lab 4 (continued)
4/16Lab 4 (continued)HW 5
4/17Lab 4 (continued)

4/239.2Data-flow analysisLab 4
4/24Data-flow analysis, continued
4/25Lab 5: Procedures – The Basics

4/289.5, notesPartial redundancy elimination
4/30Lab 5 (continued)
5/1Lab 5 (continued)HW 5 rewrite
5/29.3, notesFoundations of data-flow analysisHW 6

5/5Hack 1-2Interference graphsLab 5
5/7Hack 4.1-4.4Register allocation
5/8Lab 6: Procedures – Further Features
5/9Lab 6 (continued)

5/12No classHW 6 rewrite
5/14Lab 7: Wildcard LabLab 6
5/15Lab 7 (continued)
5/16Lab 7 (continued)

5/19Lab 7 (continued)
5/21Synthesis and evaluationLab 7


Course web site: https://gustavus.edu/+max/courses/S2014/MCS-388/
Instructor: Max Hailperin <max@gustavus.edu>