CS 226/326 Homework

General comments

Written homework should be turned in at the beginning of class on the date due. Clarity, simplicity, and neatness are important for written assignments. If necessary, write a draft version and then edit it for final submission. Homework exercises marked with an asterisk (*) are required for those taking CS326 (grad students), and can be completed by undergraduates for extra credit.

How to submit homework code

The Homework Style Guidelines should be followed in preparing programs for submission.

Each student has an individual CVS project whose name is their email id. These projects are found in a CVS repository on the server scarba.cs.uchicago.edu and are password protected. If you are not familiar with CVS, the main commands will be described below, and online documentation is available at the CVS home page. To access your project, define the shell variable CVSROOT as follows (ushing bash syntax):

   export CVSROOT=":pserver:name@scarba.cs.uchicago.edu:/home/cs226/repos"

where "name" should be replaced by your email name. Then to gain access to your project, execute the command

   cvs login

which will prompt you for a password, which you will be given.

Your project has been set up with a subdirectory for each programming exercise, named after the corresponding chapter of the text (chap1, chap2, etc.). To check out a working copy of your project

   cvs checkout name

(where again name should be replaced by your id). You can add files to your project by first creating them in or copying them to your working copy of the project, then executing

   cvs add filename

and then executing the following commit command in the top level project directory.

   cvs commit -m "some appropriate message" 

This commit command should also be executed after editing existing project files.

Test cases

The tarball testcases.tgz contains Appel's set of Tiger programs that you can use as test cases. The code packages for individual assignments may also contain sets of test cases. For grading purposes, additional tests will be used.

---

Homework 1

• Program 1, Appel, pages 10-12 (submit a file named prog1.sml)
• Exercise 1.1, parts a,b,c, page 12 (submit two source files named ex1_1a.sml (for part a) and ex1_1b.sml (for part b). The solution for part c can be provided within a comment in the second source file.
• Due April 9 at beginning of class.

Project 2

Due Wednesday April 16. Implement a lexer for Tiger (Program 2, Appel, pages 31-32).

• Complete the skeleton tiger.lex in the chap2 code bundle.
• Deal with nested comments and strings with escape sequences (p. 517).
• Deal with errors, including open comments and strings at end of file.

Homework 2

Due Monday, April 14.

1. Exercise 2.2(a)
2. Exercise 2.3(a)
3. Exercise 2.4(b)
4. [326] Generate a DFA from the NFA we constructed for the regular expression "b*(abb*)*(a|#)" (where # stands for epsilon, the empty r.e.).

Project 3

Due Friday April 25.
Implement the parser and abstract syntax for Tiger. This project combines the programs for Chapters 3 and 4 of Appel. I suggest first working on the parser with null parser actions (Chapter 3) and then adding the actions to build abstract syntax once the parser is debugged.

• Skeleton code will be available in the chap3 and chap4 directories of the tiger project, and in chap3.tgz and chap4.tgz tarballs.

Homework 3

Due Monday, April 28.

1. Exercise 3.6(a)
2. Exercise 3.11
3. Exercise 3.12(a,b,c)
4. Exercise 4.1
5. [326]Exercise 4.4
6. [326]The program rd-parser.sml implements the recursive descent parser of Appel, p. 46. Define data structure(s) for parse trees and add code so that the parser builds a parse tree as it parses.

Homework 4

Due Wednesday, May 7.

1. Exercise 5.3
2. Exercise 6.5

Project 4

Due Friday, May 2, 5:00pm.
Implement the type checker for Tiger based on the tiger/chap5 code. The two files tcenv.sml and typech.sml need to be completed. Test cases and sample output are provided, as well as a catalogue of suggested error messages (file ERRORMSGS).

Project 5

Due Friday, May 9, 5:00pm.
Implement the FindEscape module (chap6/findesc.sml), which analyzes programs to determine which local variables are escaping. Also, complete the unimplemented parts of MIPSFrame (chap6/frame.sml).

Project 6

Due Friday, May 16, 5:00pm.
Implement the translation from abstract syntax to intermediate representation (IR trees, chap7/tree.s??) based on the tiger/chap7 code. The two files transutil.sml and translate.sml need to be completed. Test cases and sample output are provided. The module TransUtil (transutil.sml) corresponds to the module Translate from the text. The module Translate implements the pure translation part of the Semant module of the text, which combines type checking and translation.

Homework 5

Due Wednesday, May 21.

1. Exercise 8.1, 8.2a, 8.3, 8.6, 8.7
2. Summarize significant differences between your submitted typech.sml and the reference version provided in tiger/chap7/typech.sml. This could be done by adding comments to your version of typech.sml.