CSCE 531: Compiler Construction (Spring 2020)

Prerequisites: CSCE 240

Meeting time and venue: TTh 1450-1505 in INNOVA 1400

Instructor: Marco Valtorta
Office: INNOVA 2269, 777-4641
E-mail: mgv@cse.sc.edu
Office Hours: M 1500-1800, or by previous appointment.
Update of 2020-03-15. Due to the closing of the university, there will be no in-person office hours.
Update of 2020-03-28. Virtual office hourse will take place as a Collaborate Ultra Session. APOGEE students will receive a guest link to join the session.

Teaching Assistant: MD Modasshir
Office: INNOVA 1203
E-mail: modasshm@email.sc.edu W 1400-1700.
Update of 2020-03-15. Due to the closing of the university, there will be no in-person office hours.
Update of 2020-03-28. Virtual office hourse will take place as a Collaborate Ultra Session. APOGEE students will receive a guest link to join the session.

Time Allocation Framework and Textbooks
Updated on 2020-03-18 and 2020-04-13

Grading Policy
Updated on 2020-03-18 and 2020-03-13

Specific objectives of this course are that the students will be able to:

• Formally define the grammar and semantics of a language
• Design and implement finite state machines appropriate for use as a lexical scanner
• Given the definition of an approptiate context-free grammar, design either a bottom-up or a top-doen parser for the grammar
• Given the semantic definitions for an appropriate language, implement the semantic routines for a top-down or a bottom-up parser
• Perform code generation.

Videos Since March 24, 2020
Lecture of 2020-03-24
Lecture of 2020-03-26
Lecture of 2020-03-31
Lecture of 2020-04-02
Lecture of 2020-04-07
Lecture of 2020-04-09
Lecture of 2020-04-14
Lecture of 2020-04-16
Lecture of 2020-04-21
Lecture of 2020-04-23

Notes
Introductory lectures
Lecture notes for Chapter 1 [W]
Lecture notes for Chapter 2 [W]
Transcript of handwritten notes of 2020-01-16 lecture, with an example of use of the technique of loop invariants.
Lecture notes for Chapter 3 [W]
Lecture notes for Chapter 4 [W]
More lecture notes for Chapter 4 [W] , used on 2020-02-11, with Java code for a recursive descent parser for CLite.
Lecture notes for Chapter 1 [M] , provided by Dr. Jost Berthold through Torben Mogensen.
Transcript of handwritten notes with details of minimization of DFA example from a slide by Dr. Jost Berhold, used in the 2020-01-30 lecture.
Lecture notes for Chapter 2 [M] , provided by Dr. Jost Berthold through Torben Mogensen.
Lecture notes for Chapters 1 and 2 [M] by Cosmin O. Oancea, provided by Dr. Torben Mogensen.
Lecture notes on syntax, with the grammar of the CLite language
Transcript of handwritten notes with details of conversion of an NFA to a DFA for SLR table construction from a slide by Dr. Jost Berhold, used in the 2020-02-18 lecture.
Lecture notes for Chapter 5 [W] , on Contextual Analysis (scope and type checking), used in the 2020-02-25 lecture.
Transcript of handwritten notes of 2020-02-25 lecture, with definition of reduce (insert, fold) and map (apply-to-all).
Lecture notes for Chapter 3 [M] by Cosmin O. Oancea, provided by Dr. Torben Mogensen.
Lecture notes for Chapter 4 [R] , provided by Dr. Aarne Ranta. Note that all slides for [R] are available at http://www.grammaticalframework.org/ipl-book/.
Lecture notes for Chapter 3 [M]
Lecture notes for Chapter 5 [R] , (Interpreters) provided by Dr. Aarne Ranta. Note that all slides for [R] are available at http://www.grammaticalframework.org/ipl-book/.
Lecture notes for Chapter 4 [M] (Interpretation).
Lecture notes for Chapter 6 [M] on Intermediate Code Generation, modified from slides by Cosmin O. Oancea, provided by Dr. Torben Mogensen.
Lecture notes for Chapter 7 [M] on Machine Code Generation, modified from slides by Cosmin O. Oancea, provided by Dr. Torben Mogensen.
Lecture notes for Chapter 8 [M] on Register Allocation and Liveness Analysis, modified from slides by Cosmin O. Oancea, provided by Dr. Torben Mogensen.
The SimpleSem simulator (java, zip archive).
A Java-based environment for teaching programming language concepts, by Manfred Hauswirth, Mehdi Jazayeri, and Alexander Winzer. A paper presented at FIE '98: Frontiers in Education '98, November 4-7, 1998, Tempe, Arizona.
Sections 6.2-6.6 [W] on functions

Quizzes (In-Class Exercises)

Tests

Homework and Projects
See lecture log for a more complete list, which includes assignments for which no handout was given. Assignments should be turned in via the departmental dropbox.
Points per assignment.
Project Assignment 1a: assigned February 4 and due February 11.
Project Assignment 1b: assigned February 13 and due February 20.
Tips on how to complete PR1b successfully for CSCE 531 students, Spring 2020.
Project Assignment 1c: assigned February 20 and due February 27.
Project Assignment 1c Update 1 of 2020-02-23: assigned February 20 and due February 27.
Project Assignment 1c Update 2 of 2020-02-24: assigned February 20 and due February 27.
Project Assignment 2a: assigned March 24 and due March 31.
Project Assignment 2b: assigned March 31 and due April 14. Update of 2020-04-13: The due date is changed to April 21 Update of 2020-04-21: The due date is changed to April 23
Hints on how to get started on PR2b for CSCE 531 students, Spring 2020.
Submission Instructions for Project 2b
Please read carefully the submission instructions in the previous entry. Here is how your program is tested:

I copy your zip or tar.gz archive and unpack it in its own directory.

I copy the test suite linked to http://www.cse.chalmers.se/edu/year/2018/course/DAT151/laborations/lab2/testsuite/index.html (direct link for the test suite: http://www.cse.chalmers.se/edu/year/2018/course/DAT151/laborations/lab2/testsuite/lab2-testsuite.tar.gz) to the same directory and unpack it, leaving it in its own directory called lab2-testsuite.

I run "make" in lab2-testsuite.

I run the test program as follows: .\progs-test-lab2.exe ..

Programs

Lecture Log

Some useful links:

• Assembler, Linkers, and the Spim simulator, by J' Larus, reference [3] in Ch.7[M] (local copy).
• Kenneth I. Appel's Obituary from the New York Times, 2013-04-29 (local copy). Kenneth Appel, with Wolfgang Haken, proved the four-color conjecture in 1976 using a computer for case analysis. He is the father of the author of the compiler "tiger books," Andrew Appel.
• 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 by Paul Graham on the original LISP interpreter: pdf, two pages per sheet, version of May 1, 2002.
• John McCarthy. "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." Communications of the ACM, 3, 4 (April 1960), 184-195 (local copy).
• John McCarthy. "A Micromanual for LISP---Not The Whole Truth." ACM SIGPLAN Notices, Vol. 13, Issue 8 (August 1978), Pages 215-216 (local copy)
• A table comparing four major versions of Lisp, recommended by Lewis Cawthorne.
• 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).
• A good reference on Java: Peter Sestoft. _Java Precisely, 3rd edition_. MIT Press, 2016 (ISBN 9780262529075).
• A good introduction to Haskell: Graham Hutton. _Programming in Haskell, 2nd edition_. Cambridge University Press, 2016 (ISBN 978-1316626221).
• JLex Information