Homework # 3
due 2004/10/14

In this assignment you get experience writing classical attribute grammars.

What You Need To Do

Write an ordered attribute grammar for some of Cool static semantics (in APS syntax). You are given part of the solution. All in all, about 600 lines of APS (including blank lines and comments) need to be added.

We will not be implementing all of Cool for this assignment. In particular, we will not be implementing inheritance: every class is assumed to be self-contained. Additionally, for simplicity, your code need not check for duplicate definitions. Thus in summary, you do not need to write error-checking for the following:

• inheritance, overriding, static dispatch calls;
• case expressions and branches;
• ``void'' (that is, null) subtyping;
• doubly defined names (classes, methods, attributes, formals).

But you should check for:

• undeclared things (types, methods, objects); Undergraduates need only complete this check!
• declarations with name ``self'';
• type equality (not compatability) for method parameters, assignment, ``if'' branches;
• arithmetic types.

You may not assume that classes, methods or attributes are defined lexically before being used.

You may use conditional equations (APS's if statement), but may not use any other of the APS attribute grammar extensions (in particular collections and remote attribution). The grammar should be schedulable as an ``ordered'' (conditional) attribute grammar; this is checked by the apscpp compiler. The Makefile uses the following options:

-S

Generate a statically scheduled implementation. The attribute grammar must be ``ordered.'' (Undergraduates may remove this requirement.)

-DO

Turn on the O debugging flag. This will dump the ``order'' of the attributes for each nonterminal, if static scheduling is being used.

-G

Generate tracing information that can be turned on in the executable with the -s option. (This slows down the executable a lot, but is invaluable for debugging.)

If the attribute is not ordered, you will get a terse error message. To find out more information, you will need to turn on more debugging flags. The UPPERCASE debugging flags are more high-level and more useful. You can list all the flags with apscpp -DH. Some of the relevant flags to consider (in increasing relevance, decreasing verbosity) are as follows:

c

Print every edge that is being considered for a transitive closure;

e

Print every edge added to an augmented dependency graph;

x

Print every edge possibly added to an augmented dependency graph from a summary graph;

i

Print every node added to an augmented dependency graph;

E

Print every edge added to a summary graph from an augmented dependency graph;

2

Check immediately for a simple cycle after every edge addition;

I

Print out all augmented and summary dependency graphs after every iteration of the DNC algorithm, including those after setting the order;

D

Print out all augmented and summary dependency graphs after the DNC algorithm has reached closure, including after the order is set;

3

Turn on debugging flag 2 after setting an order (This helps find type-3 circularities);

T

Print the (conditional) total order of attributes in every augmented dependency graph;

C

Print any cycles in the summary dependency graph that prevents an order being found;

O

Print out the order (if found).

Files

In your homework3 directory in your AFS volume:

grid.cs: make -f /afs/cs.uwm.edu/users/classes/cs754/src/homework3/Makefile

This will get several files:

README

File with questions to answer.

bad.cl

Cool file with errors.

good.cl

Cool file without errors.

bad.expected

Error messages generated by the solution.

phase.a basecpp.a cool-parser.o

Library files to be linked with your attribute grammar.

apscpp

The APS compiler.

cool-noinherit-semant-driver.cpp

The driver program for running your AG.

aps-builtin.aps

Built-in precedence rules for APS.

basic.aps

Built-in types and functions for APS.

cool-symbol.aps

A stub for a symbol package.

cool-tree.aps

The description of the Cool abstract syntax tree.

cool-noinherit-semant.aps

The semantic analyzer attribute grammar (incomplete!)

Only the README and the last file should be edited. The others should not be edited. To remind you of this, they are established as symbolic links.

The Makefile will go ahead and run the APS compiler on the incomplete attribute grammar (which generates a bunch of warnings) and link everything together into an executable. As before, you may make my-own-libs to create your own copy of the binaries, if you are not running Solaris 9.

Deliverables

Your only code deliverable is the completed cool-noinherit-semant.aps attribute grammar. I also ask you to answer the questions in the README file (on paper, or in the file)