CS 4980: Compiler Construction

CS 4980: Compiler Construction, Winter 2021-22

Instructor: Rob Hasker (414-277-7326)

Drop-in times (office hours): See my home page: https://faculty-web.msoe.edu/hasker/

Textbook: Modern Compiler Implementation in Java, 2nd Edition, Andrew Appel, Cambridge University Press, 2002, ISBN 0-521-82060-X

Course Description:

We will look at the design and implementation of a compiler, including lexical analysis, parsing, grammars, semantic analysis, code generation, and optimization.
Prereq: CS 2040 or CS 3210 (or SE 2040)

Format: 3 lecture hours, no lab, 3 credits

Course Outcomes: On successful completion of this course, the student will be able to

Understand the relationship between regular expressions and finite automata
Apply regular expressions to construct programming language tokenizers
Construct a context-free grammar
Use tools to build an LR parser
Apply syntax-directed translation and semantic analysis to code generation
Explain basic optimization techniques including liveness analysis, register allocation, dataflow analysis, and loop optimization

Grading:

		Percentage
	Assignments	40%
	Quizzes/exercises/participation:	20%
	1 Midterm exam:	20%
	Final Exam:	20%
	Total:	100%

The MSOE grading scale will be used, though I reserve the right to award higher grades to individual students if it increases fairness.

Communication

Most materials will be available on my class web site, https://faculty-web.msoe.edu/hasker/cs4980cc/ or in Canvas. For instance, quizzes will be in Canvas and links to notes will be on both the website and Canvas. I will also communicate to the class on Teams; it is critical you enable notifications for the Teams entries for this class. Many announcements will be made that way and no other. I may also use email at times. I expect you to check for electronic communications at least once a day.

Assignments and Quizzes

Unless otherwise announced, late solutions will be penalized 2% per day for the first week. Solutions submitted more than one week late will be worth zero points unless there is advance arrangement due to extenuating circumstances. Unless you have written permission, all assignments must be submitted before Monday of finals week. Note that quizzes and exams have a due date and you will not be able to submit after that due date.

Programs in assignments will be graded for both correctness (does it work right?) and presentation (does it look good on the printed page?). I will not be handing out an extensive style sheet for this course, but at a minimum you must do the following:

Use only standard libraries (ones that come with standard installations).
Give meaningful names to identifiers and scope them correctly.
Format your programs consistently and nicely, including judicious use of spaces and blank lines. Keep line lengths to about 80 characters.
Ensure your files contain no hard tabs (unless they are required by the language).
Include your name (prominently) in source files.
Providing enough documentation that another person can understand the modules in your solution, without providing documentation that is blatantly obvious from examining the code. For example, the first documentation is useful but the others are not:

  const int MAX_SIZE = 30; // max # of dates
  const int LIMIT = 50;    // limit of 50 – USELESS
  if ( x > 0 )             // check x is positive – USELESS

Follow standard design principles including small subroutines, minimal repeated code, and tightly scoped identifiers.
Fix your code so it builds without compilation warnings.

Assignments, quizzes, and exams are individual unless explicitly stated otherwise. You are responsible for honestly completing and representing your work, for appropriately citing sources, and for respecting the academic endeavors of others. Electronic tools may be used to identify plagiarism. You will be penalized for violating these standards.

Missed quizzes cannot be made up, but at least one of the lowest quiz or exercise scores will be dropped. All assignments must be submitted by the Saturday after week 10. Assignments will not be accepted after that unless there is advance, written approval.

All code should be checked into a Git repository. Backups are critical. Some of the assignments will require you to use Git repositories on specific servers, but you can use BitBucket, GitHub, or other servers for the other code. Just keep any such repositories private.

Attendance

Do not skip class! If you do happen to miss, be sure to check for new materials and get the notes you missed from a friend before the next class period. If you need to be excused from class for MSOE activities or religious observances, be sure to me know in advance. If you're sick, stay home! This includes days on which there are exams; just be sure to contact me as soon as you can get to a phone or computer.

Using phones and laptops during class to check social media, write papers, etc. is a form of missing class!

An important part of attending class is the opportunity to work through in-class problems in small groups. This also gives you a chance to come up with better answers for questions that can be shared with the class. There are lots of questions in this class that have multiple answers, and I do not always have the best one!

Strongly consider taking hand-written notes for this class. The slides omit many details on purpose. Do not try to type your notes; research shows hand-written notes are the most effective way to capture key material. Note the campus printers will easily scan documents so you can organize your notes electronically. You might consider working with others and rotating who takes notes.

If an exam is missed, I will determine whether to give you a make-up exam or increase the weight of the other exams. All students must take the final exam to receive a passing grade unless the student has been excused in advance.

Please do not record video or audio of lectures without my permission.

All students are expected to follow the procedures specified in the Raider Return Plan. This includes wearing masks in the classroom at all times.

For students with documented disabilities, chronic medication conditions and mental health concerns: MSOE provides services to make reasonable accommodations available. If you are a student who requires or anticipates the need for accommodations, please contact Student Accessibility Services Office at 414-277-7281, by email at moureau@msoe.edu, or in person at K250 to discuss appropriate accommodations and eligibility requirements.

Projected Outline

Topic	Chapters

Lexical analysis Regular expressions Finite automata Lexical analyzer generators	1, 2

Parsing Context-free grammars Predictive parsing LR Parsing Parser generators Parser error recovery	3

Code generation Semantic actions Syntax-directed translation Abstract parse trees Type checking Storage allocation and stack frames Basic blocks Liveness analysis and register allocation	portions of 5-9

Issues for modern programming languages Garbage collection Object-oriented languages Functional programming languages Polymorphic Types	portions of 13-16

Optimization Dataflow analysis Loop optimization Function inlining and partial evaluation	17, 18

The Project

Each student will implement a full compiler for the programming language Tiger. The project will be broken into the following phases:

Lexical analysis
Syntactic analysis
Semantic analysis
Code generation