CSCE 531: Compiler Construction (Spring 2010)

Prerequisites: CSCE 240

Meeting time and venue: TTh 1100-1215 in 300M B102

Instructor: Marco Valtorta
Office: Swearingen 3A55, 777-4641
Office Hours: TBD, or by previous appointment.


Grading and Program Submission Policy

Reference materials:

  • Watt, David A. and Deryck F. Brown. Programming Language Processors in Java. Prentice-Hall, 2000 (required text). Supplementary materials from the author, including an errata list, are available.
  • Here are the
  • current departmental syllabus for CSCE 531, and the
  • old departmental syllabus for CSCI 531, which is provided for historical information.
  • Please note that the Spring 2010 offering of this course does not fully conform to the departmental syllabus.
  • Specific objectives of this course are:

    Beginning of course questionnaire with answer to non-survey questions

    Introductory lectures
    Transcript of handwritten notes of 2010-01-19 lecture
    Lecture notes for Chapter 1
    Transcript of handwritten notes of 2010-01-21 lecture
    Lecture notes for Chapter 2
    Notes on Denotational Semantics
    More Notes on Denotational Semantics
    Notes on axiomatic semantics by Tucker and Noonan, used in CSCE 330, fall 2009
    Figures for Chapter 3 of Robert Sebesta's Concepts of Programming Languages, Eighth Edition, (local copy), on syntax and semantics (Link to publisher's web site)
    Slides for the above (local copy)
    Lecture notes for syntax used in CSCE 330, fall 2009
    Lecture notes for Chapter 3
    Transcript of handwritten notes of 2010-01-28 lecture
    Transcript of handwritten notes of 2010-02-02 lecture
    Lecture notes for Chapter 4
    Lecture notes for Lexical Analysis (part of Chapter 4 and handout)
    Notes on MT1, based on an observation by Mr. Gary Fredericks
    Lecture notes for Chapter 5
    Lecture notes for Chapter 6
    Lecture notes for Section 7 of Chapter 6
    Lecture notes for Chapter 7
    Lecture notes for Chapter 8
    Notes on Paul Graham's reconstruction of John McCarthy's 1960 Lisp interpreter
    Lecture notes for Chapter 9

    Quizzes (In-Class Exercises)
    Quiz 1 of 10-01-14 (with answer)
    Quiz 2 of 10-01-14 (same date as Quiz 1) (with answer)
    Quiz 3 of 10-01-19 (with answer)
    Quiz 4 of 10-01-26 (with answer)
    Quiz 5 of 10-03-02 (with answer)

    Old Test 1 with Correction Guide (in postscript format)
    Old Test 1 with Correction Guide (in pdf format)
    Test 2 from Fall 2001 (in postscript format)
    Test 2 from Fall 2001 (in pdf format)
    Topics for the Final
    Final exam from Fall 2001 (in pdf format)
    Final exam from Spring 2002 (in pdf format), with partial correction guide

    Graduate Student Presentations

    Homework and Projects
    See lecture log for a more complete list, which includes assignments for which no handout was given.
    Points per assignment.
    Programming Assignment 1: assigned February 11 and due February 16.
    Programming Assignment 2: assigned February 16 and due February 23.
    HW7: Exercises 7.1, 7.2, 7.3, due April 13.
    HW8: Exercises 8.5 and 8.6, due April 20
    Term Project (PR4): Exercises 9.6, 9.7, 9.8, 9.12(a), and 9.15 [W&B], due April 29. The term project requires you to modify the Triangle compiler. The source code for Triangle can be obtained locally, or directly from the authors at The project consists of exercises 9.6, 9.7, 9.8, 9.12(a) and 9.15 in the text- book. Teams of two students (i.e., pairs) are allowed. If you decide to do the project as a pair, please email the composition of your pair to the instructor. You must submit source code (in Java, of course). You should clearly mark with comments the code you wrote. The code must compile on the departmental Linux. It is very difficult to evaluate properly code that does not compile. Therefore, you may receive a grade of zero on parts of the term project that do not compile. The same holds for code that compiles but does not run at all. Submit your code as an archive (tar or zip) using the departmental dropbox. Use the PR4 (Term Project) dropbox. Include instructions on how to compile and run your code. Include an example of use.
    Test cases for PR4 (tar archive) A few students have noted that one of the cases for strings uses single quotes instead of double quotes. Please modify the test program to use double quotes.
    Grading policy and test cases for the term project.

    Programs A brief guide to the Triangle language processor.

    Lecture Log

    The USC Blackboard has a site for this course.

    Some useful links:
    An article on the importance of learning multiple programming languages (including functional ones)
    John Backus's Obituary from the New York Times, 2007-03-20.
    Robin Milner/s Obituary from the (London) Independent, 2010-04-14.
    Robin Milner's entry on wikipedia
    Jay Earley and Howard Sturgis. "A Formalism for Translator Interactions." Communications of the ACM, 13, 10 (October 1970), pp.607-617. Available electronically from the ACM digital library, via USC Thomas Cooper library: local copy.
    Paper by Paul Graham on John McCarthy's original LISP interpreter.
    Paper by Paul Graham on John McCarthy's original LISP interpreter (pdf, local copy, one page per sheet, version of January 18, 2002)
    Local copy of the paper on the original LISP interpreter: postscript, two pages per sheet, version of May 1, 2002.
    Local copy of the paper on the original LISP interpreter: pdf, two pages per sheet, version of May 1, 2002.
    A table comparing four major versions of Lisp, recommended by Lewis Cawthorne.
    How to use your cse email account.
    A site on decompilers. (It includes text of a dissertation. This pointer is provided to follow up on a question by a student in an earlier edition of the course.)
    Jukka Paaki. "Attribute Grammar Paradigms---A High-Level Methodology in Language Implementation." ACM Computing Survey, 27, 2 (June 1995), 196-255 (local copy).
    Norman Matloff's Introduction to the vi Text editor
    Norman Matloff's Unix Tutorial Center
    A good reference on Java: Peter Sestoft. _Java Precisely, 2nd edition_. MIT Press, 2005 (ISBN 0-262-69325-9).
    JLex Information