Boston University College of Arts and Sciences Computer Science Department

111 Cummington Street Boston, MA 02215 Phone: (617)-353-8919 / Fax: 353-6457 Web: www.cs.bu.edu

Prerequisites

This course has a prerequisite of CS 320 (or equivalent). CS 210 or some experience with assembly language is strongly recommended, and strong programming skills in C/C++ are a must.

Course Description

This course develops the mathematical basis for syntax specification and translation and shows how this basis can be used to design and implement compilers for imperative languages. It builds on CS 210 and CS 320, and leads to further study in programming language theory (CS 520). Topics include: regular languages and finite-state automata, lexical analysis, context-free grammars, and push-down automata, parsing using LR and LALR acceptors, syntax-directed translation using attribute grammars, symbol table maintenance, run-time environments, type systems and type-checking, intermediate code generation, code optimization, target code generation, register allocation, and data-flow analysis. If time allows (hope springs eternal!) I will cover advanced topics such as garbage collection, memory hierarchy optimizations, and compilation for pipelined and superscalar architectures. Students will write a complete compiler from a subset of C to MIPS assembly language, using the Unix compiler tools lex and yacc.

Books and Resources

Basics of Compiler Design, by Toben Mogensen

The project will make use of the following handy reference:

Lex & Yacc, Levine, Mason, and Brown (O'Reilly).

The first is a free text which is provided on the course website in pdf form; the second is available in the bookstore.

All materials other than the textbooks will be posted on the class web site: www.cs.bu.edu/fac/snyder/cs525/Home.html.

Course Policies

Lectures

• You are responsible for all the material covered in lecture and in the readings. I will clarify what material is most important before tests, however, it is important that you do all the readings and review your class notes periodically.
• Class attendence is very important. I will take attendence at random intervals to check on your attendance and to learn your names. If your class attendence has been a problem, I will not automatically lower your grade, but I will be less available to answer your questions outside of office hours (questions that probably pertain to material you missed from class), and less willing to help you later in the semester if there is a problem (as there usually is in such cases).
• Class participation is also very important. Although the class is large, I encourage questions, and will usually start class with a review of the last class, and a request for questions on that material. Please don’t be afraid to ask a question during the lecture, as often this means that many people may have a similar question, and it is worth stopping me to get clarification. If we are running out of time, I may defer your question for after class or email. I welcome questions by email, but can not guarantee a timely answer on your schedule.

Homework Assignments

• Homeworks are extremely important, as you can not learn these concepts (and especially you can not learn the programming techniques) by simply reading a description of them---you MUST get your hands dirty and learn by manipulating the concepts.
• There will be about 10 "pencil and paper" homework assignments, normally one every week. Please see the Topics link on the web page for the ongoing schedule of assignments. I will clarify the method for submission and my late policy on the first assignment.
• The programming project (integrated into the homeworks) will be the implementation of a compiler from a subset of C down to MIPS assembly language, which you will work on individually. You will get this project in 4-5 parts. You may implement this project on your own system, but we can provide support only for our own Unix system.
• There are no labs in this course, but the TF may need to hold some tutorial sessions on the project at various times. We will find appropriate times and places when this is necessary. In any case, you will have plenty of access to someone qualified to help you with the project. Basic programming problems can be answered by the TAs in the CS computer lab.

Tests

• The midterm exam will occur in Week 5 of the course (probably around June 20th); I will firm this up several weeks before the exam.
• The final exam is scheduled for the last day of class (July 11th) and the project will be due by the end of the last week (July 13th--Friday the 13th!) ; please make your travel plans accordingly. I can not give the exam early to anyone for any reason.

Grades

• 20% Midterm Exam
• 30% Final Exam (cummulative)
• 50% Homeworks and Project

These percentages are tentative and may be changed at my discretion at any time.

Miscellaneous

• There will be no incompletes in this class except for reasons of dire illness near the end of a semester in which all previous work has been completed satisfactorily.
• You can not redo any assignment, or do extra work after the semester is over to improve your grade, as this arrangement would then by fairness have to be extended to the rest of the class (an impossible situation).
• Please see me immediately after class or during office hours if you have a concern about the grading or indeed about any aspect of the course.

Homework Policies

• Submission Instructions: Please hand in a hard copy of your solutions to all problems, with a suitable cover page with your name, the date, the course, and the number of the assignment. Do each problem on a separate sheet clearly labelled at the top (e.g., "Problem 3"), and staple all pages together in the upper-left-hand corner (do NOT submit solutions separately or update your solutions after handing in your assignment). For any problem statement that asks multiple questions, answer each in a separate paragraph, labelled (a), (b), etc. Submit "pencil and paper" problems into the CS 525 mail slot (not the shelf) in the CS homework station; submit code or files produced by software using Gsubmit as specified on the course home page. A small penalty will be taken for any homework that does not follow these guidelines.
• Late Policy: Both parts of the homework (pencil and paper, and electronic submission) are due at 5 pm on wednesday; late homeworks will be penalized at the rate of 25% for each weekday late (each day ending at 5pm, weekends not included).

Policy on Academic Misconduct

Whenever you submit a piece of academic work and sign your name to it, you are verifying that this work is the result of your own intellectual efforts; it is Plagiarism to submit work solely under your own name in which:

• You collaborated with another student in solving the homework problems;
• You copied the solution from a book, web site, or the work of another student; or
• You got significant help in solving the problem, but do not acknowledge this in your solution.

In this course, I will not allow you to submit any joint work, although in other courses and in other contexts you may be permitted to do this. In general, you must always provide proper attribution of authorship by naming all persons, books, or resources that provided intellectual content towards the final result. In some cases, you will need to describe the extend of the contribution, particularly when literally copying the words or artistic artifacts of another. To fail to provide proper attribution is plagiarism. Plagiarism demeans the seriousness of what we do in class, and does not allow you as a student to obtain a fair grade for the results you worked hard for.

I will discuss the issue of plagiarism with the grader, and use, when appropriate, automated tools to check submitted programs and files for copying. I don't like to be involved in this, but it is necessary in order to provide a fair environment for your work. In cases of suspected plagiarism, I will discuss the matter with the student(s) involved and, when warrented, submit the case to the Academic Conduct Committee (of which I was chairman for three years). Unfortunately, students in my classes violate these policies several times a year on average; it is my hope that by being completely clear and straight-forward about my policy that I can reduce this number. Please take this issue serious and talk to me if you have any concerns or questions.