CS 4980: Compiler Construction

CS 4980: Compiler Construction, Winter 2022-23

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. In addition to understanding how programming languages are implemented and optimized, this course will give tools for embedding programming concepts into other languages.
Prereq: CS 2040/SE 2040 or CS 3210

Note this course can be taken in addition to CS 3040, Programming Languages and Interpreters. While both courses overlap, the tools and approaches taken in this course are very different so the overlap is relatively small.

This course includes a number of topics that are relevant to software engineers: Breaking a complex problem into manageable subsystems, a concrete understanding of how high level programming languages relate to optimized machine code, and using design patterns to build a maintainable compiler.

Format: 3 lecture hours, no lab, 3 credits

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

Apply regular expressions to construct programming language tokenizers
Understand the relationship between regular expressions and finite automata
Construct a context-free grammar
Build a table-driven 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:	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/cs4980-cc/ or in Canvas. For instance, quizzes will be in Canvas and links to notes will be on the website. 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.

My office hours are listed as "drop-in" times to emphasize that you do not have to have an appointment to come see me. You can come other times as well! I am always glad to help students with challenges, both technical and non-technical. I do expect you to have spent a few minutes checking for answers on the class website and Teams before requesting help, but absolutely would rather you ask for help than spend hours trying to find solutions on your own.

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 by Saturday before finals. 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 such as BitBucket, GitHub, or GitLab. Backups are critical, but do be sure any such repositories are 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!

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.

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