CompSci 654/754: Compilers

John Boyland

compsci-654@uwm.edu

Spring 2012

	John Boyland	Chao Sun
Office	EMS 925	EMS E280
Office Hours	T 2:00-3:00pm, R 10:00am-12:00pm, F 8:30-9:30am	M 4:00-6:00pm
Phone Number	229-6986, 964-3227 (home)

A compiler is a program that translates another program from one language to another. The first language is usually a high-level language such as C++, Java or Common Lisp. The second language is often a low-level language such as MIPS assembly language or Java byte code. As part of the course, students will construct a working compiler for an object-oriented language, and then use it to execute real programs in the language.

Desired Outcomes

Students will

• know the basic structure and functionality of compilers
• be able to apply formal language theory to construct compiler front-ends
• understand symbol tables
• know how high-level features such as objects and method calls are implemented
• be familar with basic optimizations, including redundancy elimination, copy propagation, and dead-code elimination
• be familiar with issues of register allocation and assignment
• be able to construct a working simple compiler for a simple object-oriented language to a simple but realistic machine language using syntax-directed translation

Requirements

Junior standing, CompSci 417, and CompSci 431 are prerequisites.

Students must be

1. able to write, compile and execute programs in a UNIX environment
2. able to use makefiles
3. able to define classes with information hiding (abstract data types ADTs)
4. able to use and implement standard data structures (dynamic arrays, linked lists, binary search trees and hash tables)
5. able to use inheritance and virtual member functions to implement designs using dynamic-dispatch for polymorphism
6. able to understand and modify programs with tens of classes
7. able to write black-box unit tests of simple ADTs
8. able to understand and write regular expressions and context-free grammars
9. familar with functional programming

Texts

The required textbook for the course is

Michael Scott. Programming Language Pragmatics. Morgan Kaufmann, San Francisco. 3rd edition. 2009. (Earlier editions are also acceptable, but the chapters and page numbers come from the third edition.)

Assigned readings are given at the end of this syllabus.

I also recommend that one read the classic compilers textbook:

Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools. Addison-Wesley, Reading, Massachussetts.

This book has come out in a third edition.

Discussion Section

The discussion section will be used to present specific information about the tools we are using (for example, coollex, coolyacc and spim) as well as on the structure of the many files that form the infrastructure of the Cool compiler. There will also be time for concrete questions on the programming assignments.

Grading

The grade for the course will be computed from the following parts:

30%

Examinations
There will be three examinations spaced throughout the course; each examination contributes 10% to the course grade. Any single examination may be made-up during the final examination time.

42%

Programming Assignments
There will be eight programming assignments, each worth 6% of the course grade. The lowest assignment grade will be dropped.

18%

Homework
There will be a written homework every second week (7 in all). Each homework is worth 3% of the grade. The lowest grade will be dropped.

10%

Reading
Over the course of the semester, there will be 12 quizzes on the required reading. Each counts 1% of the course grade and the lowest two will be dropped.

Late assignments will not be accepted.

Exceptions to these rules can be made only in extraordinary circumstances. Advance notice of a need for an exception should be given if possible. All graded assignments must be your own work (your own words), but you may work with other people as long as you list their names prominently on the first page of the turned in assignment or homework. Unless specific permission is given (for example, in group assignments), no electronic or xerographic copying of assignments is permitted. Whether or not you have permission of the other, submitting someone else's work as your own is plagiarism, a serious instance of academic misconduct. Everyone is responsible for learning the material themselves. Some of the assignments (programming or homework) may be graded orally.

The numeric grade will be converted into a letter grade according to the following scale

Minimum Score	92	90	87	82	80	77	72	70	67	62	60	0
Grade	A	A$-$	B$+$	B	B$-$	C$+$	C	C$-$	D$+$	D	D$-$	F

There is no curve, but the instructor reserves the right to increase a grade if he believes it would not reflect the student's mastery of the material. A grade can only be decreased for cheating.

Graduate students will be given alternate homework assignments.

Special Features of the Filesystem

All your work should be done in the AFS volume assigned to you. The absolute pathname is

/afs/cs.uwm.edu/users/classes/cs654/401/PantherID.

We recommend that you make a symbolic link from your UNIX home directory to this directory. Before you can access this directory, you will need to obtain authenticate yourself to AFS using Kerberos. This can be done using

/usr/afsws/bin/klog PantherID

and type your Kerberos password.

The root directory of your volume has some special subdirectories:

OldFiles

The directory includes a copy of your volume taken at 1am. If you accidentally delete a file that you need, please look for a backup here before contacting lab staff.

Grades

This directory includes a file giving the grade for each assignment. The first line gives the numeric grade and the remainder of the file gives comments. The file summary.txt lists all the scores and computes the weighted percentage.

homework$n$

Directory for homework deliverables.

PA$n$

Directory for programming assignments.

misc

Any files you don't need in an assignment.

The file system is a distributed network filesystem that permits you to do your homework on you home computer once you have installed Open AFS. The program assignments require that you have Java and Scala (both freely available) installed. You may do assignments on weise or on your home machine, but you will need an environment that enables shell scripts and make files (e.g. Linux).

Examinations

On Thursdays, there is a quiz on reading except for the three ``midterm'' examinations:

Midterm #1

February 23

Midterm #2

April 5

Midterm #3

May 10

The final examination is on May 15.

Schedule

The following schedule is subject to change.

Tuesday	Thursday
January 24What is a compiler?	January 26The Cool compilerCh 1Quiz on Reading
January 31Regular Expr. & AutomataCh 2.1.1, 2.2.1PA 1 due	February 2ScannersCh 2.2Quiz on Reading
February 7Grammars and TreesCh 2.1.2-3HW 1 due	February 9Parsing ICh 2.3.0-2Quiz on Reading
February 14Parsing IICh 2.3.3PA 2 due	February 16Error HandlingCh 2.3.4 on CDQuiz on Reading
February 21Attribute GrammarsCh 4HW 2 due	February 23MIDTERM 1Ch 1-2,4
February 28Binding & ScopesCh 3.1-3PA 3 due	March 1Symbol TablesCh 3.4-8 (inc. CD)Quiz on Reading
March 6Types & Type CheckingCh 7.0-7.2HW 3 due	March 8Type ConstructorsCh 7.3,7.4,7.10Quiz on Reading
March 13Object OrientationCh 9.0-3PA 4 due	March 15Object LayoutCh 9.4-5 (inc. CD)Quiz on Reading
March 20	March 22
SPRING	BREAK

Tuesday	Thursday
March 27Assembly LanguageCh 5.0-5.4 on CDHW 4 due	March 29Back-end & AssemblingCh 14.0-5Quiz on Reading
April 3LinkingCh 14.6-7 (inc. CD)PA 5 due	April 5MIDTERM 2Ch 3,7,9,14
April 10Expression EvaluationCh 6.0-3HW 5 due	April 12Selection & IterationCh 6.4-5Quiz on Reading
April 17Calling SequencesCh 8.0-8.2PA 6 due	April 19Other IssuesCh 8.3-5Quiz on Reading
April 24OptimizationCh 16.0-2 on CDHW 6 due	April 26PipeliningCh 5.5 on CDQuiz on Reading
May 1Local OptimizationCh 16.3 on CDPA 7 due	May 3Global OptimizationCh 16.4 on CDQuiz on Reading
May 8TBACH 10?,11?,12?HW 7 due	May 10MIDTERM 3Ch 5,6,8,16
May 15FINAL EXAMCh 1-9,14-16PA 8 due

Accomodations

If you will be needing any accomodation in this course for any reason, please contact the instructor. Please also be aware of the standard University policies: http://www.uwm.edu/Dept/SecU/SyllabusLinks.pdf