CSC 453: Compilers & Systems Software

Syllabus

Lecture: Tuesdays and Thursdays 3:30pm to 4:45pm in Gould-Simpson Room 906
Required Discussion Session: Fridays 10 to 11am or 11 to noon in 228
We are covering material in the recitation that we will not be covering in lecture.

Description of Course

CS 453 teaches students how to implement programming languages with a compiler. Although most computer science professionals do not end up implementing a full compiler, alumni of this course are surprised by how often the skills they learn are used within industry and academic settings. The subject of compilers ties together many concepts in computer science: the theoretical concepts of regular expressions and context free grammars; the systems concept of layers including programming languages, compilers, system calls, assembly language, and architecture; the embedded systems concept of an architecture with restricted resources; and the software engineering concepts of revision control, debugging, and testing.

Course Prerequisites

CSC 345 and CSC 352 are require prerequisites. CSC 372 is recommended.

Instructor and Contact Information

Instructor: Michelle Strout, mstrout@cs.arizona.edu, please communicate through piazza
Office Hours: Wednesdays 2-3pm and Thursdays 5-6pm in Gould-Simpson 707, other times possible by request
Open Door Policy: If my office door is open, feel free to knock and ask questions. If my door is closed, send your question via piazza.
Teaching Assistant: Erman Gurses, egurses@email.arizona.edu, please communicate through piazza. Lab hours in G-S 228, Mon 8am-9:50.
Class Web Page (required reading): http://www.cs.arizona.edu/classes/cs453/fall16/
D2L (For grades and some homeworks): http://d2l.arizona.edu
Piazza: https://piazza.com/arizona/fall2016/csc453/home

Course Format and Teaching Methods

Students are responsible for reading the announcements posted on the course website. Students are also responsible for completing all of the posted reading assignments, homeworks, and programming assignments.

This compiler's course includes two lectures a week and one recitation section. The lectures will be interactive with students being put in groups and working on example problems in class. Answers to the problems will be shared with the whole class. The recitation session will be hands on exercises for learning the course concepts and any supporting technology.

In this course, you will spend most of your time building a compiler as a learning experience. Through the implementation of the compiler, students will learn how to apply the concepts being discussed in lecture. An iterative design and development process will be followed so that each of PA2 through PA5 will result in a compiler for an ever growing subset of the MeggyJava programming language. There is a homework or programming assignment due EVERY Monday (except for labor day where it is pushed to Tuesday). We estimate that students will spend one to two hours a day outside of class learning the concepts being taught in this class.

The semester-long project, which consists of 5 programming assignments (PA1 through PA5), and the homeworks (HW1 through HW9), which include online quizzes and/or smaller programming drills, are all collaborative learning opportunities. The programming assignments that build the compiler can be done in groups of any size from 1 to 5 students. ALL other outside of class work is to be done individually (homeworks and peer reviews). The majority of your time will be spent working on these learning opportunities. However, the majority of your grade will be due to the two midterms and the final. These will evaluate the concepts we expect you to learn while doing the homeworks and the programming assignments.

Any code your group submits must have been written by someone in your group. Your group for programming assignment PAx can build on another group's code for PA(x-1), but the README file for PAx must indicate which group's code is being built on. The instructor reserves the right to ask any group member to explain any aspect of the submitted code.

Participation is expected in the form of peer reviews of code, posting to piazza, and contributing during in-class activities.

Course Objectives and Expected Learning Outcomes

The focus of this class is to learn and practice problem solving programming in the context of designing and developing a full compiler. Important CS concepts such as regular expressions, context free grammars, lexing, parsing, semantic analysis, abstract syntax trees, and the object-oriented programming language run-time memory model will be covered in depth. Students will also be expected to learn the development of program evaluation criteria, constructive critique, and self evaluation. Students will have the opportunity to practice collaboration skills, verbal and written communication of technical concepts, unit and regression testing, and iterative design and development.

The learning outcomes for this course will be evaluated using the following criteria:

Collaboration skills: improvements in communicating the purpose and usage of programs, ability to constructively critique other programmers and perform substantive self evaluation;
Regular expressions: be able to explain regular expression terminology, ability to specify example regular languages with regular expressions, converting regular expressions to NFAs, and NFAs to DFAs;
Lexing: ability to write a scanner for tokens that appear in programming languages;
Context Free Grammars: be able to explain CFG terminology and the relationship between CFGs and regular expressions, ability to write a CFG to recognize a particular language, ability to modify CFGs to remove left recursion and handle expression precedence and associativity, ability to draw a parse tree for example grammars and inputs;
Parsing: ability to define parsing terminology covered in class or in the assigned readings; ability to design and implement a parser using recursive descent or a general-purpose parsing algorithm;
Abstract Syntax Trees (AST): ability to convert a program into an AST and design an AST data structure for a language specified with a CFG;
Semantic Analysis: ability to locate type errors in ASTs, ability to implement type checking while parsing or while traversing an AST;
Error handling: ability to explain and implement various approaches to error handling in the scanner, parser, and semantic analyzer;
Run-time stack: ability to draw the run-time stack and heap for OOP programs at any point during execution;
Code Generation: ability to write AVR assembly code that implements various programming language features and ability to generate code as parsing or while traversing an AST;
Haskell: ability to understand and implement Haskell programs using function recursion, pattern matching, user-defined data structures, and list manipulation;
Interpretation: explain difference between compilation and interpretation and be able to implement interpretation for expression evaluation; and
Testing: ability to write a set of test cases that cover all programming language features and many of the possible combinations of those features.

Absence and Class Participation Policy

The UA’s policy concerning Class Attendance, Participation, and Administrative Drops is available at http://catalog.arizona.edu/policy/class-attendance-participation-and-administrative-drop.

The UA policy regarding absences for any sincerely held religious belief, observance or practice will be accommodated where reasonable: http://policy.arizona.edu/human-resources/religious-accommodation-policy.

Absences preapproved by the UA Dean of Students (or dean’s designee) will be honored. See https://deanofstudents.arizona.edu/absences .

Participating in the course and attending lectures and other course events are vital to the learning process. As such, attendance is strongly recommended at all lectures and discussion section meetings. Students who miss class due to illness or emergency are required to bring documentation from their health-care provider or other relevant, professional third parties. Failure to submit third-party documentation will result in unexcused absences. Unexcused absences means that only very specific questions about concepts covered in the missed class will be answered during office hours.

Makeup Policy for Students Who Register Late

Since there is a homework or programming assignment due each week and a peer review due after each programming assignment, it is critical that students who do a late add catch up quickly. A student who registers late will have 3 days to complete each deadline they have missed until they have caught up with the normal schedule.

Class Communication

We will be using Piazza https://piazza.com/arizona/fall2016/csc453/home. Sign up at https://piazza.com/arizona/fall2016/csc453/. Please post all questions on piazza and share interesting things you have learned about compilers, Meggy Jrs, Haskell, or anything related to the course.

Required Texts or Readings

For the text book, we will be using "Compiler Construction" by Niklaus Wirth, which is available online at http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf.

All reading assignments from the book and other provided notes will be posted on the class schedule.

Required or Special Materials

The Meggy Jr devices will be required to demonstrate test programs. These devices will be provided by the department via a semester loan. If you are interested in purchasing and assembling your own Meggy Jr, you can order one from http://shop.evilmadscientist.com/tinykitlist/100-meggyjr for $75. The department has soldering irons and the other tools needed to assemble the kit. You can set up a time to use these tools and obtain some assistance with the instructor.

For each programming assignment, each group will be creating a 30 second demo video using a phone camera. If your group does not have access to a phone camera, let the instructor know when declaring who is in your group.

Final Examination

Monday December 12, 2016 3:30 pm - 5:30 pm in room 906.

University Final Exam Regulations and Final Exam Schedule.

Grading Scale and Policies

Grades will be posted on D2L. Working with a group on the compiler project programming assignments (PA1 through PA5) is optional. Each group can include up to 5 students. Groups are self selected and can be modified throughout the semester. All other graded work will be submitted individually.

The course grade consists of the following:

Homeworks (HW1-HW9), 15%
Programming Assignments (PA1-PA5), 15%
Peer Reviews for PA1 through PA4, 10%
Midterm 1, 15%
Midterm 2, 20%
Final, 25%

Due Dates and submission: Programming assignments (PA1-PA5) and homeworks (HW1-HW9) will be due Monday nights at 11:59pm. Starting August 29th there will be something due EVERY Monday night except for Labor Day on September 5th where the deadline has been pushed one day later to Tuesday night at 11:59pm and the Monday after Thanksgiving, where nothing will be due. Programming assignments (PA1-PA5) will be submitted using the turnin script on lectura. Homeworks (HW1-HW9) will be submitted using D2L quizzes. You should figure out the answers to homework questions yourself, but you can read the book, the class web page, and other resources to help.

Due Dates and Submission: Peer reviews will be due three days after each programming assignment (PA1 through PA5). All of the programming assignments are due on a Monday at 11:59pm therefore, the peer reviews for PAx will be due the Thursday 11:59pm following the PAx Monday deadline. Peer reviews will be a google form that each student fills out and submits. See peer-reviews.html for more information.

Grading Promptness: Grades for the programming assignments, homeworks, and peer reviews will be provided within 5 days of the deadline. Any exceptions to this will be announced on Piazza and in class.

Late policy: Programming assignments, homeworks, and peer reviews submitted within 24 hours of the due date and time will be reduced by 20% unless we indicate otherwise. For example, an assignment due Monday at 11:59pm that is submitted at Tuesday 12:00am (midnight and 1 minute late) will receive a grade of [X - X*(.20)], where X is the raw grade out of 100 on the assignment.

Curve Policy on Exams: If an exam average is less than 75% for those who took exam, I will use the following curving policy. Let X be the top score in the range 91 to 95 inclusive or 91 if there are no score in that range then let X=91. All the exams scores for that particular exam will be increased by (100-X).

Extra credit: Students can earn extra credit by submitting potential midterm or final exam questions. For each question used in one of the midterms or final, the student will obtain 1 extra credit point for that exam. The instructor decides which questions to include on the midterms and the final. Additionally students can obtain extra credit by posting a substantive message "Anonymously to Classmates" on Piazza. The instructor will indicate in piazza which posts are substantially useful and the student will earn an extra credit point on the next midterm or final. A maximum of 5 points can be earned this way for any one midterm or final, and only one post per student can earn an extra credit point per week. Last but not least, the first student to find a bug in a programming assignment or class web page AND report it will earn half a point of extra credit for the next midterm or final. Items marked FIXME have already been detected by someone. A maximum of 2 points can be earned this way for any one midterm or final.

Requests for incomplete (I) or withdrawal (W) must be made in accordance with University policies, which are available at http://catalog.arizona.edu/policy/grades-and-grading-system#incomplete and http://catalog.arizona.edu/policy/grades-and-grading-system#Withdrawal, respectively.

Dispute of Grade Policy: Any requests for grading corrections must be done within 10 school days of the assignment being due. Requests for grading corrections must be made in a private message on piazza to the instructor.

University policy regarding grades and grading systems is available at http://catalog.arizona.edu/policy/grades-and-grading-system .

Honors Credit

Students wishing to contract this course for Honors Credit should e-mail me to set up an appointment to discuss the terms of the contact and to sign the Honors Course Contract Request Form. The form is available at http://www.honors.arizona.edu/faculty-and-advisors/contracts .

Scheduled Topics/Activities

See the class schedule online for more details.

Date	Topic	Due Dates
Week 1, Aug 22-26	Introduction to compilers, Meggy Jrs, and MeggyJava
Week 2, Aug 29-Sept 2	Haskell and AVR assembly	DUE Mon Aug 29th: HW1 - Syllabus, compiler intro, and MeggyJava
Week 3, Sept 5-9	Regular languages and lexing	DUE Tues Sept 6th: HW2 - Haskell Exercises (Sept 5th is labor day)
Week 4, Sept 12-16	Context free grammars and parsing	DUE Mon Sept 12th: PA1 - MeggyJava and AVR, DUE Thursday Sept 15: PA1 Peer Reviews
Week 5, Sept 19-23	1st Midterm and code generation intro	DUE Sun Sept 18th: HW3 - Online exercises to help study for midterm
Week 6, Sept 26-30	ASTs, semantic analysis, and error handling	DUE Mon Sept 26th: PA2 - setPixel, DUE Thursday Sept 29: PA2 Peer Reviews
Week 7, Oct 3-7	Code generation for PA3 and more lexical analysis	DUE Mon Oct 3rd: HW4 - programming exercise for ASTs
Week 8, Oct 10-14	Expression parsing	DUE Mon Oct 10: HW5 - online exercises
Week 9, Oct 17-21	Other approaches to parsing	DUE Mon Oct 17: PA3 - checkButton, DUE Monday Oct 24th: PA3 Peer Reviews
Week 10, Oct 24-28	Symbol tables and 2nd Midterm	DUE Mon 24th: HW6 - Online exercises to help study for midterm
Week 11, Oct 31-Nov 4	More Haskell	DUE Mon Oct 31: HW7 - programming exercise for symbol tables (canceled)
Week 12, Nov 7-11	Run-time stack	DUE Mon Nov 7: HW8 - symbol table design
Week 13, Nov 14-18	Code generation for OOP	DUE Mon Nov 14: PA4 - methods, <, tones, DUE Satruday Nov 19: PA4 Peer Reviews
Week 14, Nov 21-22	Compilation for objects and arrays including memory model	DUE Mon Nov 21: HW9 - Memory models exercise
Week 15, Nov 28-Dec 2	Haskell Monads
Week 16, Dec 5-6	Compilation for advanced language features	DUE Mon Dec 5th: PA5 - Objects and Arrays, No PA5 Peer Review
Monday December 12 (3:30-5:30pm)	Final Exam

Department of Computer Science Code of Conduct

The Department of Computer Science is committed to providing and maintaining a supportive educational environment for all. We strive to be welcoming and inclusive, respect privacy and confidentiality, behave respectfully and courteously, and practice intellectual honesty. Disruptive behaviors (such as physical or emotional harassment, dismissive attitudes, and abuse of department resources) will not be tolerated. The complete Code of Conduct is available on our department web site. We expect that you will adhere to this code, as well as the UA Student Code of Conduct, while you are a member of this class.

Classroom Behavior Policy

To foster a positive learning environment, students and instructors have a shared responsibility. We want a safe, welcoming, and inclusive environment where all of us feel comfortable with each other and where we can challenge ourselves to succeed. To that end, our focus is on the tasks at hand and not on extraneous activities (e.g., texting, chatting, reading a newspaper, making phone calls, web surfing, etc.).

Students are asked to refrain from disruptive conversations with people sitting around them during lecture. Students observed engaging in disruptive activity will be asked to cease this behavior. Those who continue to disrupt the class will be asked to leave lecture or discussion and may be reported to the Dean of Students.

Some learning styles are best served by using personal electronics, such as laptops and iPads. These devices can be distracting to other learners. Therefore, students who prefer to use electronic devices for note-taking during lecture should use one side of the classroom.

Threatening Behavior Policy

The UA Threatening Behavior by Students Policy prohibits threats of physical harm to any member of the University community, including to oneself. See http://policy.arizona.edu/education-and-student-affairs/threatening-behavior-students.

Accessibility and Accommodations

Our goal in this classroom is that learning experiences be as accessible as possible. If you anticipate or experience physical or academic barriers based on disability, please let me know immediately so that we can discuss options. You are also welcome to contact the Disability Resource Center (520-621-3268) to establish reasonable accommodations. For additional information on the Disability Resource Center and reasonable accommodations, please visit http://drc.arizona.edu.

If you have reasonable accommodations, please plan to meet with me by appointment or during office hours to discuss accommodations and how my course requirements and activities may impact your ability to fully participate. Please be aware that the accessible table and chairs in this room should remain available for students who find that standard classroom seating is not usable.

Code of Academic Integrity

Students are encouraged to share intellectual views and discuss freely the principles and applications of course materials. However, graded work/exercises must be the product of independent effort unless otherwise instructed. Students are expected to adhere to the UA Code of Academic Integrity as described in the UA General Catalog. See http://deanofstudents.arizona.edu/academic-integrity/students/academic-integrity.

The University Libraries have some excellent tips for avoiding plagiarism, available at http://www.library.arizona.edu/help/tutorials/plagiarism/index.html/

Selling class notes and/or other course materials to other students or to a third party for resale is not permitted without the instructor’s express written consent. Violations to this and other course rules are subject to the Code of Academic Integrity and may result in course sanctions. Additionally, students who use D2L or UA e-mail to sell or buy these copyrighted materials are subject to Code of Conduct Violations for misuse of student e-mail addresses. This conduct may also constitute copyright infringement.

UA Nondiscrimination and Anti-harassment Policy

The University is committed to creating and maintaining an environment free of discrimination; see http://policy.arizona.edu/human-resources/nondiscrimination-and-anti-harassment-policy

Our classroom is a place where everyone is encouraged to express well-formed opinions and their reasons for those opinions. We also want to create a tolerant and open environment where such opinions can be expressed without resorting to bullying or discrimination of others.

Additional Resources for Students

UA Academic policies and procedures are available at http://catalog.arizona.edu/policies. Student Assistance and Advocacy information is available at http://deanofstudents.arizona.edu/student-assistance/students/student-assistance.

Confidentiality of Student Records http://www.registrar.arizona.edu/personal-information/family-educational-rights-and-privacy-act-1974-ferpa?topic=ferpa

Subject to Change Statement

Information contained in the course syllabus, other than the grade and absence policy, may be subject to change with advance notice, as deemed appropriate by the instructor.

Last Updated

mstrout@cs.arizona.edu updated October 26, 2016: Canceled HW7.
mstrout@cs.arizona.edu updated October 13, 2016: PA3 peer review deadline pushed from October 20th to October 24th due to GHC.
mstrout@cs.arizona.edu updated September 13, 2016: Assignments can have late period revoked.
mstrout@cs.arizona.edu updated August 30, 2016: Removed PA5 peer review.
mstrout@cs.arizona.edu updated August 25, 2016: Added curve policy for exams and clarification about what can be used for HWs, which are implemented as D2L quizzes.
mstrout@cs.arizona.edu updated August 24, 2016: Added Erman office hours.
mstrout@cs.arizona.edu updated August 23, 2016: Various typos and maximums on extra credit.