CSE 504 Compiler Design

Fall 2020

Welcome to CSE 504! Public information regarding this course will be posted on this page, assignments/quizzes/exams will be administered on Blackboard, and discussions hosted on Piazza. Access code for joining this Piazza forum is posted on Blackboard.

Overview

Computer Science projects increasingly involve the analysis of unstructured textual data. Yet, only a small minority of CS grads are proficient in text-processing with regular expressions and grammars, or have used parsing/transformation tools such as sed, AWK, Lex and Yacc. Students can address this gap by taking this course. Moreover, by understanding the process of code translation and optimization, students can become better at writing efficient code.

Compilers is my favorite subject because it harnesses the beauty of theoretical computer science to solve very concrete software engineering problems. Time and again, it demonstrates how efficient software implementations can be automatically generated from compact, high-level specifications. Compilers also offers a perspective on how research results find their way into practice. Much of the course material originates from research papers written in the 70s and 80s that have since been put into practice.

Modern compilers are among the most complex pieces of software around. Through this course, students learn how to break down this complexity --- how to modularize their design, how to make the modules flexible and extensible, how to decouple design and implementation, and finally, how to build efficient implementations. This course will also provide significant experience in OO-programming with C++. Modern C++ is the language of choice for writing high-performance code. While retaining some of the key benefits of C-language such as the ability to write low-level code, it avoids most of C's drawbacks such as the lack of type-safety, standardized libraries for data structures, and modern features such as objects, templates (aka generics), type inference, closures, exceptions, and so on.

Course Topics

• Lexical analysis: Regular expressions, translation to finite-state automata (deterministic or non-deterministic), and regular expression tools.
• Parsing: Context-free grammars, push-down automata, parser generation from CFGs, and abstract syntax trees (ASTs).
• Runtime Environments: Memory allocation, memory management, garbage collection techniques, exceptions, and inheritance.
• Static Analysis and Optimization: Data flow analysis, abstraction interpretation, and optimizations based on them.
• Dynamic Analysis and Instrumentation: Applications to debugging, runtime error detection, automated testing and vulnerability analysis.

What is New/Different This Time

• The projects will focus more on the front-end of compilers, and less on the back-end. You will develop a non-trivial parser using the tools Flex and Bison. Through your project, you can also explore other tools such as sed and AWK.
• You get to write a compiler/interpreter from ground-up. You will gain significant experience with C++ programming, specifically, C++17 and STL, without having to master the complexities of an industrial-strength compiler such as LLVM.
• About a third of the course will focus on new topics that many compiler courses are unable to get to. These topics will cater to researchers (e.g., static analysis, dynamic analysis, instrumentation, and automated testing) as well as practitioners (e.g., regular expressions, garbage collection, debugging and testing, and optimizations used in modern compilers). To make room for these topics, we will reduce the time spent on topics such as parser and code generation techniques.

Schedule:

Lecture time/location: Tue/Thu at 11:30am to 12:50pm online from Blackboard.

Programming Assignments: (Tentative)

• Assignment 1: Sep 9
• Assignment 2: Sep 30
• Assignment 3: Oct 16
• Project: Dec 8

Important Dates:

Mid-term: Oct 27

Thanksgiving Break: Nov 23 to Nov 29

Last lecture: Dec 3, Thursday

Final Exam: Dec 16, Wednesday, 11:15am to 1:45pm

Lecture Slides and Recordings:

Topic #	Topics and Lecture Recordings	Slides	Notes
1	Introduction Organization of a Compiler: 24 mins	PDF
2	Lexical Analysis Regular expressions, Flex: 76 mins Flex, Finite State Automata: 84 mins Finite State Automata, Assignment 1: 86 mins	PDF
3	Syntax Analysis RE derivatives, Lex and state machines, Intro to CFGs: 73 mins Context-Free Grammars and Top-Down Parsing: 77 mins Bottom-up Parsing: 78 mins     76 mins LR(1) Parsing, Assignment 2: 80 mins	PDF
3	Syntax-Directed Translation Attributes and Attribute Grammars: 75 mins	PDF
4	Names, Binding and Symbol Table Names, Attributes, Binding and Symbol Table: 81 mins	PDF
5	Types and Type-Checking Types: 85 mins    86 mins A3 Discussion, OOP: 75 mins Types and OOP: 78 mins Type equivalence and Type-checking: 75 mins	PDF PDF PDF
6	Evaluation and Runtime Environment Expressions and statements: 88 mins Parameter passing: 73 mins Stacks and Procedure calls: 53 mins Exceptions, Heap management: 14 mins (starts at 64 mins) Garbage collection: 85 mins Implementation of OO Languages: 70 mins	PDF
7	Intermediate Code Generation Introduction: 13 mins starting at 64 mins Expressions, calls, statements: 76 mins Control-flow statements: 30 mins	PDF
8	Code Optimization Overview of optimizations: 47 mins (starts at 30 mins) Dataflow analysis: 84 mins   50 mins	PDF
9	Machine Code Generation Overview: 23 mins (starts at 54 mins) Register allocation and instruction selection: 63 mins	PDF

Instructor:

R. Sekar
Office: 364 New CS Building
Office Hours: Tue/Thu 1:30pm to 2:15pm on Zoom

Texts:

We will use the "Dragon book" --- Compilers: Principles, Techniques, and Tools, Second Edition by Aho, Sethi, Ullman, and Lam, or any older version; including the 1977 version, called "Principles of Compiler Design" and has a green dragon on it, as opposed to the purple dragon on the latest version. We will use the textbook for material that has not changed significantly since the green dragon book. Your reference for newer material will be the lecture slides and additional material made available from this page.

Grading

The weighting for programming assignments, midterm and final exams will be roughly as follows. Note that these weightings are preliminary, and are subject to some changes in the future.

• Assignments: 40%
  • Academic honesty assignment: 2%
  • Class participation: 3%
  • Assignment 1: 6%
  • Assignment 2: 7%
  • Assignment 3: 9%
  • Project: 13% plus bonus points of up to 8%
• Exams: 60%
  • Midterm: 23%
  • Final exam: 37%

You are advised to start working on the projects at the earliest possible time even if the deadlines are far away. The date the projects are due will be clearly specified. Projects are due by 11:59pm on the specified date. Late projects will be penalized at the rate of 5% for the first day, 15% the second day and 25% per day after that. So, there is no point submitting a project more than 4 days late! No further extensions will be allowed.

Each student gets one late pass that allows you to submit one assignment up to 4 days late. Use the late pass wisely. I will not accept more than one late submission for any reason, including emergencies.

Any form of copying in the course, and all forms of academic dishonesty, are considered serious offenses, and will be prosecuted to the maximum extent permitted by university policies. The minimum penalty for any form of copying, whether from your friends, the Internet or outside sources, or from previous offerings of the course, will be an F-grade. There will be no exceptions.

Note that we make use of automated software for catching copies, and this software is quite sophisticated and can see through typical evasion attempts. In addition, we manually check for unusual similarities among programs. These enhanced may not be performed on every submission, but if we do identify copying, then it is a situation of "one strike and you are out," i.e., you end up with an F-grade regardless of how well you have done in the course until then.

Special Needs

If you have special needs, concerns or a disability, please contact the staff at Student Accessibility Support Center (SASC). SASC staff will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation will remain confidential.