CS-321, 322: Languages and Compiler Design I and II


Syllabus - Winter 2006

Course Reference Number:
CS-322-001, Winter 2006: CRN 40839

When and Where:
Tuesday & Thursday, 2:00PM - 3:50PM
PCAT, Room 138
First Class: Tuesday, January 10, 2006
Holidays: None
Quiz #1: Thursday, February 9 (Tentative)
Quiz #2: Thursday, March 2 (Tentative)
Final Exam: Monday, March 20, 10:15AM-12:05PM
     The final will be comprehensive. It will be closed book and closed notes.

Instructor: Prof. Harry Porter
E-Mail: harry@cs.pdx.edu
Web Page: www.cs.pdx.edu/~harry
Office space at PSU: 115-06 (Fourth Ave Bldg)
Office hours: Directly after class meetings and by arrangement.

Grader: Aaron Kryger
E-Mail: akryger@cs.pdx.edu
Office: 115-??? (Fourth Ave Bldg)
Office Hours: ???


CS-322

Misc. Material - CS-322
Checklist for FIRST meeting: (pdf, 1 page)
My Java Summary: html or (pdf, 62 pages)
Coding Style For Java Programs: pdf, 8 pages
PCAT Reference Manual: pdf, 11 pages
SPARC Overview: pdf file
SPARC Demo Programs: pdf file
ASCII Byte Encoding Chart: pdf file
Misc Useful Programs: directory
Study Guide / Terminology: pdf file or html
Grades for CS-322: PDF file of point spreadsheet or PDF file of bar chart

Homeworks - CS-322
Homework 1: pdf file
Homework 2: pdf file
Homework 3: pdf file
Homework 4: pdf file
Homework 5: pdf file
Homework 6: pdf file
Homework 7: pdf file

Projects - CS-322
Project 7 Files: ~harry/public_html/compilers/p7/ (SPARC Assembler)
Project 7a Files: ~harry/public_html/compilers/p7a/ (PrettyPrint)
Project 8 Files: ~harry/public_html/compilers/p8/ (IR Code Generation 1)
Project 9 Files: ~harry/public_html/compilers/p9/ (IR Code Generation 2)
Project 10 Files: ~harry/public_html/compilers/p10/ (IR Code Generation 3)
Project 11 Files: ~harry/public_html/compilers/p11/ (Final Code Generation)

Lecture Notes - CS-322
Packet-19 (Intro to CS322): pdf
Packet-20 (SPARC Architecture - part 1): pdf
Packet-21 (SPARC Architecture - part 2): pdf
Packet-22 (SPARC Architecture - part 3): pdf
Packet-23 (Code Generation-Part 1): pdf
Packet-24 (Project-8): pdf
Packet-25 (Tolmach's AST): pdf
Packet-26 (Project-9): pdf
Packet-27 (Code Generation-Part 2): pdf
Packet-28 (Parameter Passing): pdf
Packet-29 (Code Generation-Part 3): pdf
Packet-30 (Project 10): pdf
Packet-31 (Target Gen-Part 1): pdf
Packet-32 (Target Gen-Part 2): pdf
Packet-33 (Register Allocation): pdf
Packet-34 (Tiling): pdf
Packet-35 (Project 11): pdf
Packet-36 (Optimization, Part 1): pdf
Packet-37 (DAG-Based Optimization): pdf
Packet-38 (Data Flow Analysis): pdf
Packet-39 (Loop Optimizations): pdf
Packet-40 (The SPANK Project): pdf


CS-322: Policy on Late Project Submissions

Each programming project will have a due date and you should plan on submitting your project before that date. If you submit something late, there is a penalty. The late policy is:
   Up to 48 hours late - No points off
   Up to 7 days late   - 5 points off
   Later than 1 week   - 5 points off for every additional week, or part thereof 
The last assignment will be due approx. 1 week before the final. Every project must be received before the final exam, with absolutely no exceptions. Furthermore, you must complete project 8 before you begin working on project 9, and you must complete project 9 before you begin working on project 10. By complete, I mean you must sucessfully pass all tests. You need not finish project 7 before you begin working on 8, nor must you complete project 10 before you begin working on project 11.

This policy effectively recognizes that events like illness or funerals will occassionally come up, so projects cannot always be handed in on time. You are effectively allowed to fall behind. Although there is a small point loss if things are late, it is not large. I decided to take off a few points to prevent students from holding on to project submissions longer than necessary, then handing in everything at the time of the final, which would overwhelm the grader.

If you fall behind, it is your responsibility to find the time in the remainder of the term to catch up. If you fall behind by more than a week, it will hurt you on other projects later in the term, since you may run out of time before the final hard deadline, and be unable to complete the last project.

I strongly encourage you to keep up and hand in projects before the due date, and not fall behind. Experience has shown that students who allow themselves to fall behind, often have great difficulty catching up later.

If projects are handed in within 48 hours of the due date, they will be graded immediately and returned with the others. When projects are later than that, their grading will be delayed, possibly by a couple of weeks.


CS-322 Schedule

    Week 1 - SPARC Assembly Code
        Tuesday (Jan 10)
        Thursday (Jan 12)

    Week 2 - SPARC Assembly Code
        Tuesday (Jan 17)
            Reading: Complete "Overview of SPARC Architecture" before class
        Thursday (Jan 19)
            Reading: Begin reading ch. 7
            HW #1 due

    Week 3 - Generating Intermediate Code, Runtime Environment
        Tuesday (Jan 24)
            Reading: Read ch. 7, through page 373
            Project P7 due ("SPARC Assembly Language")
        Thursday (Jan 26)
            HW #2 due

    Week 4 - Execution Stack, Function Activations, Parameter Passing
        Tuesday (Jan 31)
            Reading: Complete ch. 7 before class
            Project P8 due ("Generate Intermediate Code, part 1")
        Thursday (Feb 2)
            HW #3 due

    Week 5 - Records, Arrays, Switch Statement
        Tuesday (Feb 7)
            Reading: Read ch. 8, through page 428, before class
        Thursday (Feb 9)
            Quiz # 1

    Week 6 - Target Code Generation
        Tuesday (Feb 14)
            Reading: Read ch. 8, through page 467, before class
            Project P9 due ("Generate Intermediate Code, part 2")
        Thursday (Feb 16)
            HW #4 due

    Week 7 - Register Allocation
        Tuesday (Feb 21)
            Project P10 due ("Generate Intermediate Code, part 3")
        Thursday (Feb 23)
            HW #5 due

    Week 8 - Code Generation via Tiling
        Tuesday (Feb 28)
            Reading: Complete ch. 8 before class
        Thursday (Mar 2)
            Quiz #2

    Week 9 - Introduction to Code Optimization
        Tuesday (Mar 7)
        Thursday (Mar 9)
            HW #6 due

    Week 10 - Data Flow Analysis, Loop Optimizations
        Tuesday (Mar 14)
            Project P11 due ("Generate Target Code")
        Thursday (Mar 16)
            HW #7 due

    Finals Week
        Monday (Mar 20)
            Exam 10:15 AM (2 hours)


CS-321

Misc. Material - CS-321
Checklist for FIRST meeting: (pdf, 1 page)
Hello-World Assignment: (pdf, 1 page)
My Java Summary: html or (pdf, 62 pages)
Coding Style For Java Programs: pdf, 8 pages
PCAT Reference Manual: pdf, 11 pages
PCAT Sample Programs: directory
Terminology / Study Guide for Exams: pdf file or html
Grades for CS-321: PDF file of point spreadsheet or PDF file of bar chart

Homeworks - CS-321
Homework 1: pdf file
Homework 2: pdf file
Homework 3: pdf file
Homework 4: pdf file
Homework 5: pdf file
Homework 6: pdf file

Projects - CS-321
Project 0 Files: ~harry/public_html/compilers/p0/ (Tree)
Project 1 Files: ~harry/public_html/compilers/p1/ (E Language)
Project 2 Files: ~harry/public_html/compilers/p2/ (Lexer)
Project 3 Files: ~harry/public_html/compilers/p3/ (Parser 1)
Project 4 Files: ~harry/public_html/compilers/p4/ (Parser 2-Build AST)
Project 5 Files: ~harry/public_html/compilers/p5/ (Checker 1)
Project 6 Files: ~harry/public_html/compilers/p6/ (Checker 2)

Lecture Notes - CS-321
Packet-1 (Course Introduction): pdf
Packet-2 (Introduction to Java - optional, not covered in class): pdf
Packet-3 (The Tree Assignment): pdf
Packet-4 (Intro-part 1): pdf
Packet-5 (Intro-part 2): pdf
Packet-6 (Lexical-part 1): pdf
Packet-7 (Lexical-part 2): pdf
Packet-8 (Lexical-part 3): pdf
Packet-9 (Lexical-part 4): pdf
Packet-10 (Project 3-Parser): pdf
Packet-11 (Syntax-Part 1): pdf
Packet-12 (Project 4-Abstract Syntax Tree): pdf
Packet-13 (Syntax-Part 2): pdf
Packet-14 (Syntax-Part 3): pdf
Packet-15 (Project 5): pdf
Packet-16 (Semantics-Part 1): pdf
Packet-17 (Project 6): pdf
Packet-18 (Semantics-Part2): pdf

Bonus Question
Answers to the bonus question


CS-321 Schedule

    Week 1 - Overview of Compiling
        Tuesday (Sept 27)
        Thursday (Sept 29)
            Complete HelloWorld Assignment

    Week 2 - Lexical Analysis and Scanning
        Tuesday (Oct 4)
            Reading: Complete ch. 1 before class
            Project P0 due ("Working with trees")
        Thursday (Oct 6)
            HW #1 due

    Week 3 - Lexical Analysis and Scanning
        Tuesday (Oct 11)
            Reading: Complete ch. 2 before class
            Project P1 due ("The E Language")
        Thursday (Oct 13)
            HW #2 due

    Week 4 - Context Free Grammars
        Tuesday (Oct 18)
            Reading: Complete ch. 3 before class
            Project P2 due ("Build a lexical scanner")
        Thursday (Oct 20)
            HW #3 due

    Week 5 - Top-Down Parsing
        Tuesday (Oct 25)
            Reading: Complete ch. 4 before class
            Project P3 due ("Build a parser")
        Thursday (Oct 27)
            Quiz # 1

    Week 6 - Top-Down Parsing
        Tuesday (Nov 1)
            Reading: Begin reading ch. 5
            Project P4 due ("Build the Abstract Syntax Tree")
        Thursday (Nov 3)
            HW #4 due

    Week 7 - Bottom-Up Parsing
        Tuesday (Nov 8)
            Reading: Complete ch. 5 before class
        Thursday (Nov 10)
            HW #5 due

    Week 8 - Bottom-Up Parsing
        Tuesday (Nov 15)
            Reading: Begin reading ch. 6
            Project P5 due ("Semantic Analysis-part 1")
        Thursday (Nov 17)
            Quiz #2

    Week 9 - Attribute Grammars and Semantic Analysis
        Tuesday (Nov 22)
            Reading: Complete ch. 6 before class
        Thursday (Nov 24)
            Thanksgiving Holiday - no class

    Week 10 - Attribute Grammars and Semantic Analysis
        Tuesday (Nov 29)
            Project P6 due ("Semantic Analysis-part 2")
        Thursday (Dec 1)
            HW #6 due

    Finals Week
        Monday (Dec 5)
            Exam 10:15 AM (2 hours)


Course Description

This course studies the principles of programming languages with an emphasis on programming language implementation and compiler design. This includes various techniques for describing and defining a language, as well as techniques for implementing compilers. The course is centered on a large programming project-the construction of a complete compiler for a small programming language-which will be completed over the two term sequence CS 321 and CS 322. Topics to be covered over the two terms include: lexical analysis, syntactic analysis, recursive descent parsing, LR parsing, syntax-directed translation, type checking, run-time environments, code generation, code optimization, and various language design issues.

This is a two term sequence. Students are strongly encouraged to take CS 321 and CS 322 in consecutive quarters from the same instructor.


Textbooks

TextbookPhoto
Required: Compiler Construction: Principles and Practice, Kenneth C. Louden, PWS Publishing, 1997, ISBN 0-534-93972-4. This is our primary textbook and will be available through the PSU Bookstore.

Required: You will definitely need a book on Java, but the choice is yours.


The Java Programming Language

Here are two recommended books on Java:

The Java Programming Language, 3rd Edition, Ken Arnold, James Gosling, and David Holmes, Addison-Wesley, 2000. ISBN 0-201-70433-1.

Thinking in Java, 2nd Edition, Bruce Eckel, Prentice-Hall, 2000. This book is also available free on the web at www.mindview.net/Books/TIJ

Related Websites

Harry Porter's Java Summary: html or (pdf, 62 pages)
Java Web Site: java.sun.com/j2se/1.4/docs/index.html
Java Class Documentation (Frames): java.sun.com/j2se/1.4/docs/api/index.html
Java Class Documentation (No Frames): java.sun.com/j2se/1.4/docs/api/overview-summary.html


Prerequisites

The official prerequisites are:
Students will work on a large programming project; as such, they will need the previous experience in writing and debugging large programs provided in classes like CS 202 and CS 300. Java will be used as the implementation language for the compiler project, but no previous experience with Java is required. This course will look at regular languages, finite-state automata, and context-free languages in some depth; CS 311 will have provided the student's first exposure to these topics.

The prerequistes for the second term (CS-322) also include having passed the first term (CS-321).

In the second term (CS-322), you will learn a new machine architecture, the SPARC architecture. We will assume you are familiar with the concepts of machine language and that you have written assembly language programs before, but we will not assume any familiarity with the SPARC architecture.

It is the student's ressponsibility to ensure that he/she has the appropriate background before attempting this class.


Programming Projects

Over the course of two terms, students will work on a single large programming project, which is the implementation of a compiler for the "PCAT" language. This project will be implemented in Java.

There will be approximately 6 programming projects during the first term, taking about 2 weeks each. All but the first project are part of the overall compiler project. Since later programs will make use of earlier programs, it is critical that students complete all projects on time.

You may develop your code on any machine and operating system you like, as long as it supports Java (SDK version 1.2 or later, corresponding to "Java 2"). However, the code you submit will be tested and graded on the CS department's Sparc machines, using SDK version 1.4. It is your responsibility to make sure that your code works properly on this system; since Java is highly portable, this should not be a significant difficulty.

Students must not work together: All programs must be designed and coded independently. You must compose and type in every line code you submit, with the exception of code I distribute to the class. Any form of code sharing will be considered cheating.

Grading will be based on style, organization, and aesthetics; submissions will also be tested for correctness.

Late programming submissions will not be accepted without prior approval.

For CS-322:

There will be approximately 5 programming projects during the second term, taking approximately 1-2 weeks each. Later programs will make use of earlier programs, so it is critical that students complete all projects.

In CS-321, it is assumed that you wrote a lexical analyser, parser, and type-checker for the PCAT language. It is assumed that you are familiar with PCAT from CS-321. In CS-322, we will complete the compiler. In outline, the projects will be: The compiler projects in this term will make use of the code written last term, in my section of CS-321

If you did not take CS-321 from me last term, I will provide .jar files that can be linked with the code you write this term. In other words, I will provide the lexer, parser, and type-checker and, during CS-322, you will create the back-end to give a full, working compiler. (There are subtle differences in the PCAT language used in other sections of this course which make it impractical to use a front-end implemented in another instructor's section of CS-321.)


Homework Assignments

There will be approximately 5 homework assignments per term, generally weekly and due at the beginning of class. Late homeworks will not be accepted without prior approval.


Class Mailing List

A "MailMan" e-mailing list will be maintained for this class.

Students must subscribe to this list.

From time to time I will post notices about the class and hints/comments about assignments.

Students are encouraged to send mail to the list, too. However, please be careful to send your completed project code to the proper address, and not to the mailing list!

To subscribe, go to the following web page and enter your email address and a password and click "subscribe".
    
webmail.cecs.pdx.edu/mailman/listinfo.cgi/cs321-001
The MailMan program will email you a confirmation message. You must reply, but you can simply hit your email "reply" button. After being adding to the mailing list you will get a "welcome" message from me.

To post a message to all the list members, send email to:
    cs321-001@cs.pdx.edu
For additional documentation, see
    http://staff.imsa.edu/~ckolar/mailman/mailman-userguide-0.1.pdf (pdf, 8 pages)
    http://www.list.org/mailman-member 
(By the way, if Internet Explorer does not work with MailMan on the Mac, use the "Safari" web browser instead.)


Using "FTP" to Obtain Class Files

You may wish to use an "ftp" program to transfer class files from my directory (the "remote") to your computer (the "local"). If you want to use the standard UNIX ftp program, type the following command:
    ftp anonymous@ftp.cs.pdx.edu
Then, change to my directory. For example, to get to the directory containing the files for project 1, at the "ftp>" prompt type:
    cd /pub/users/harry/compilers/p1
To list all the files in the remote directory, type:
    ls
To copy all files from the remote directory into the current directory on your local machine, type
    mget *
To suppress verbose interaction, answer "a" to the "mget filename [anpqy?]?" prompt. You can also type "help" or "quit" to leave ftp.

For further info, in UNIX type:
    man ftp

Grading

The final exam may test on material covered only in class and on material covered only in the reading assignments. Your grade will be based approximately, as follows. These percentages are tentative; I may change them. I will compute your grade as follows. Each homework will be worth some number of points. For example, HW #2 might be worth 25 points. Each homework will also count for a certain percentage of your grade. For example, HW #2 might be worth 3% of your final grade. The actual number of points you make on an individual assignment will then be divided by the number of points earned by the high scorer for that assignment and the result will be multiplied by the percentage weight of the assignment to give a normalized number of points. (For example, if you got 18 points on HW #2 and the highest score on the assignment was 23 points, you would get 2.35 normalized points, i.e., (18/23) * 3%.) Likewise, for the programming projects and the final exam, I will compute your normalized points, based on the percentage weights for each of the programs and the final. Summing the normalized points from each of your homeworks, programs, and the final, you will then have a net score between 0 and 100. I will then sort everybody on net score and give people with more points better grades. Grading will be based on a curve; in other words, I will select the range for A's, B's, etc., after seeing how the net scores distribute. I will select the percentage weights of the individual homeworks and programs at the end of the term (keeping within the general percentages listed above), since some assignments may be harder than others and will deserve larger weights in the final score.

Incompletes will not be given.


Attendance

Successful students will arrive on-time, relaxed and full of curiosity.

Attendance in class is mandatory; it will be checked and will count for part of your grade.


Academic Dishonesty

The programming project is not a group project. You must create the code on your own!

I encourage students to discuss the material in this class. Feel free to discuss the programming projects amongst yourselves, but only at a higher-level than the code. Do not share code.

Do not work together on any programming project in this class. Do not look at anyone else's code. Do not allow anyone to use your code. Every line of code you submit must be your own work, except of course the code I provide. You may discuss the assignments with other students, but only in general terms. You may not look at someone else's code or share Java code.

It is NOT okay to look at someone else's code, even for the purposes of helping that person or for comparing your different approaches. Each student must do the coding alone. You must type in every line of code you submit. You must not copy another student's code. Do not look at some one else's code, then turn around and type that code in.

It will be considered cheating to copy code.

It will be considered cheating to decompile or look inside any .class or .jar file I provide. If you have questions about what these files do, just ask me!

It will be considered cheating to send your project code to the class mailing list, even if it is an accident. I simply cannot allow students to send their completed solution code to the mailing list!


Class Cancellation

Snow Closure: For inclement weather information, call the University switchboard, 725-3000, for a recorded message about university-wide class cancellation. Snow closure info is also available at: www.flashnews.net/pdx.html (click on "View Current Info").

Other Cancellations: If I should need to cancel class for any reason, I will email the mailing list.


YAPP: An SLR Parser Written in PCAT

YAPP (Yet Another PCAT Parser) is an SLR generator written in PCAT. YAPP can read in a grammar and a sample string. It will build parsing tables according to the SLR algorithm and then use those tables to parse the sample string. YAPP can easily handle a grammar for the PCAT language and can parse a PCAT program. YAPP can even parse itself.

YAPP is the largest known PCAT program in the universe, consisting of more than 2100 lines of PCAT code.

Over the years that CS-321 has been taught, there have been many, many PCAT parsers produced. YAPP is not just another PCAT parser.

Click here to see the YAPP source code.

Click here to look at the system in more detail.


Problems / Comments on This Web Page

Send email to: harry@cs.pdx.edu