This course will introduce the basic concepts of compiler design and implementation. Topics include lexical analysis, various types of parsers, intermediate and object code generation and code optimization. The material will be presented from an implementation point of view rather than a formal approach. The impact of language design on compilers will also be examined.
Course Requirements: PREQ: CS 0441 and ((CS or COE 0447) or (CS 0406 and 0456)); (MIN GRADE ‘C’ FOR ALL COURSES LISTED); PROG: Arts and Sciences or Sch Computing and Information; LVL: Junior or Senior
https://pitt.zoom.us/j/679594355
Vinicius Petrucci (vpetrucci AT pitt DOT edu)
6309 Sennot Square
TuTh 1:00 pm - 2:15 pm - Cathedral of Learning @ G8
Room SENSQ 6309
Chi Zhang
Contact: CHZ54
Office hours
By appointment @ SENSQ 5514
To be successful in the course, the student must understand how simple imperative programming languages equivalent to C can be compiled to machine code for RISC-like machines. In particular, the students must be able to:
structure a compiler as a sequence of distinct translation steps
use regular languages to describe the lexical elements of a programming language
implement lexical analysis using a finite automaton approach or tools like Flex
use context free languages to describe the syntactic structure of a programming language
apply the parsing methods top-down (recursive descent) or bottom-up (LR) using tools like Bison
use abstract syntax trees to represent the results of the syntactic analysis
break down statements and expressions to simpler designs, and translate syntax trees to code
describe how recursive procedure calls can be implemented by means of stacks, activation records, and machine registers
translate the simplified source language code of a program to machine-specific (RISC) instructions
Lexical analysis and Finite Automata (scanning)
Syntactical analysis (parsing) using Top-down and Bottom-up approaches
Program representation in Abstract Syntax Trees (AST)
Symbol tables and scope rules for C-like languages
Type-checking for C-like languages
Different forms of intermediate code (IR)
Local/Global code optimization
Call stacks and activation records
Code generation for RISC-like machines
Basic blocks, control-flow graphs, liveness analysis, register allocation
There will be two exams: one mid-term exam and one final exam. The tentative exam dates are listed on the schedule. Exams are closed book and an individual effort. You must take all exams in the lecture session for which you are registered.
Most weeks there will be a homework assignment covering material presented in lecture. These assignments are to be completed individually. The purpose of the assignments is to give you practice with the theoretical material of the course. Spending time on the written assignments pays off on the exams.
The course project consists of 4 parts. Taken together, those parts form a complete implementation of a subset of the C language. Completing the course project is a large, complex, and rewarding task, which is made much easier by giving adequate forethought to design. Start the programming assignments early!
Programming assignments should be done in teams of one or two. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.
Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the teaching assistants will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment.
Programming assignments are due at 11:59 p.m. on the date in the course schedule. Programming assignments will be turned in electronically. The exact method will be announced with the first assignment.
All lectures notes and assignments will be uploaded on the class website. See the Schedule page.
Written Assignments: 10%
Programming Assignments: 50%
I, II: 10% each
III, IV: 15% each
Midterm: 20%
Final: 20%
Each exam and lab assignment must be your own independent and original work. Students choosing to work with a partner are effectively considered as one entity, and are freely allowed to exchange, help, design, and code with one other. Assignments will be checked by automatic plagiarism detectors, and students may be asked to explain any suspicious similarities. All incidences of cheating will be reported to the Dean’s office. The default penalty for cheating is to be removed from the course with a failing grade.
Pay attention to the following examples of cheating, which include:
Sharing code: either by copying, retyping, looking at, or supplying a copy of a file from this or a previous semester.
Describing code: Verbal description of code from one person to another.
Coaching: Helping your friend to write a lab, line by line.
Copying: Copying code from the Web or another student. You are only allowed to use code that we provide you.
Searching: Searching the Web for solutions or for any advice on the lab.
Cheating is also looking at other students’ code or allowing others to look at yours. This includes one person looking at code and describing it to another. Be sure to store your work in protected directories, and log off when you leave a remove server, to prevent others from copying your work without your explicit assistance.
You may find it useful to know what is not cheating:
Clarifying ambiguities or vague points in class handouts, lectures, or textbooks.
Helping others use the computer systems, networks, compilers, debuggers, profilers, or other system facilities.
Helping others with high-level design issues only, but algorithm/coding and other such details are not ”high-level design issues”.
Helping others with high-level (not code-based) debugging.
Using code from the skeleton/package provided in class is always OK.
Students need to submit assessed assignments by the published deadline. The penalty for late assignments is 15% per day. However, each student will receive 5 late days for the course. These late days are provided to allow you to cope with most emergencies that prevent completing a lab on time, including computer problems, a cold, getting stuck at the airport, etc. The following rules will be applied for late days:
Late days are used automatically until you run out.
No more than 2 late days can be used on any one assignment.
If your last submission is one day late, and you have at least one remaining late day, then you will receive full credit for the lab and automatically spend one late day. For example, if an assignment is due at 11:59pm on Thursday and your last submission is noon on Friday, then you will receive full credit and spend one late day.
Once you have used all your late days, or exhausted the limit for the assignment in question, then you will receive a penalty of 15% for each subsequent late day. For example, suppose you have only one late day left. If an assignment is due at 11:59pm on Thursday and your last submission is noon on Saturday, then you will spend your one remaining late day and be penalized 15%. If your last submission is noon on Sunday, then you will spend one late day and be penalized 30%.
Late submissions will not be accepted after three days after the due date.
It is worth noting that those late days to help you manage your time in the face of personal issues and to help smooth out burstiness in assignment due dates across classes. They are for when you are sick, when a short term emergency situation arises, when you have too many deadlines all at once, etc. It is strongly recommended that you conserve your late days, saving them for the more difficult assignments at the end of the term.
You are expected to plan your time well and including contingency time. For example, if you expect a piece of work to take two days, you should begin it more than two days before its deadline. Please DO NOT ask the course lecturer for an extension. Except for serious persistent personal issues, you should not anticipate additional deadline leniency. If you have a serious persistent personal issue, such as being hospitalized for an extended period or needing to leave the country for a family matter, please talk to your academic advisor as soon as possible. You should always inform your academic advisor of any circumstance that seriously affects your work.
There is no required textbook, but you are encouraged to do some reading from the relevant material using any of those popular textbooks:
Compilers: Principles, Techniques, and Tools (CPTT, aka "The Dragon Book")
2nd edition
Aho, Lam, Sethi, and Ullman
Engineering a Compiler (EC)
2nd edition
Cooper and Torczon
Modern Compiler Implementation (MCI)
Appel, with Palsberg
Note: there are versions of this book tailored to C and Java, as well as ML.
CPTT: Sections 3.1, 3.3, 3.4, 3.6, 3.7, 3.8
EC: Chapter 2 through Section 2.5.1 except for 2.4.4
MCI: Chapter 2
CPTT: Sections 4.1-4.6, 4.8.1, 4.8.2
EC: Sections 3.1-3.5
MCI: Chapter 3
CPTT: Sections 5.1-5.3 6.3, 6.5
EC: Sections 4.1-4.4
MCI: Chapters 4 and 5
CPTT: Sections 6.2, 7.1-7.4, 8.1-8.3, 8.6
EC: Chapter 5, Sections 7.1-7.2
MCI: Chapters 6, 7, and 14
CPTT: Sections 8.5, 8.7, 9.1-9.4
EC: Sections 8.1-8.4, 8.6, 9.1-9.3
MCI: Chapter 10
CPTT: Sections 7.5-7.6, Section 8.8
EC: Sections 13.1-13.2, 13.4,
MCI: Chapters 11 and 13
Cheating/plagiarism will not be tolerated. You may discuss assignments with classmates, but the work you turn in must be your own. If in doubt, refer to the university's policies or ask the instructor.
Students suspected of violating the University of Pittsburgh Policy on Academic Integrity, from the February 1974 Senate Committee on Tenure and Academic Freedom reported to the Senate Council, will be required to participate in the outlined procedural process as initiated by the instructor. View the complete policy at http://www.cfo.pitt.edu/policies/policy/02/02-03-02.html.
All exams must be taken in class on the date they are given. There will be no exceptions unless you have a very good reason and have received permission in advance.
Unless otherwise stated, the due time of homework and projects is the beginning of the class time. Late submissions may incur a penalty per day.
You may ask to have an exam, project or lab regraded. However, the entire exam, project or lab will be regraded. This may or may not result in a grade change, either up or down. To have an assignment regraded, you must hand in the item with a typewritten paragraph explaining what was not graded correctly. You must ask for the regrading by the next class period after the project, lab, or exam was returned.
If you have a disability for which you are or may be requesting an accommodation, you are encouraged to contact both your instructor and Disability Resources and Services, 216 WilliamPitt Union, (412) 648-7890/(412)383-7355 (TTY), as early as possible in the term. DRS will verify your disability and determine reasonable accommodations for this course.