CSE 401: Compilers

Assignment #6 (Parser; APT; Set Runtime)

Due Friday, 07Nov97

This assignment should be done as a group effort within your project group.
Design and implement the necessary extensions to the PL/0 parser and AST class hierarchy to represent the extended PL/0 language. (Use the extended yacc grammar description we distributed in class as the language definition.)
Implement a C++ class Set that has public member functions to implement all primitive operations needed for the PL/0 set data type. This will entail writing about 150 lines of C++ code; much of the code is structurally similar to itself. This part of the assignment is completely independent from the first part of the assignment, and is little more than an exercise in programming a (relatively) simple data structure in C++.
Do not do any of these things in your Set class.
- Do not be particularly clever.
- Do not use C++ operator overloading.
- Do not use inlining.
- Do not use any virtual functions.
- Do not use static member functions.
- Do not use ... arguments (varargs syntax).
- Do not use any dynamic storage allocation (eg, your member functions must not call new, delete or their evil twins malloc or free).
- Do not pass classes by value to member functions.
- Do not return classes by value from member functions.
- Except for writing a disposable testing jig, do not include any files into your implementation, and do not do any I/O.
Do these things in your Set class.
- Do make efficient use of storage.
- Do be reasonably concerned about time efficiency, but do not be overly concerned.
- The only arguments to pass to your member functions should be of type integers, unsigned integer, pointers to Sets, or references to Sets.
- Do use arrays of unsigned integers, where an integer is assumed to hold 32 bits.
- The only basic data type you should use is an int or an unsigned int; do not use char or short.
- Do use const as appropriate.
- When in doubt about C++ operator precedence and associativity, be sure to parenthesize.
- Make your member functions be of the form:
```
  void add(const Set *rv1, const Set *rv2);
```
  Where add will take take the union (set addition) of the set referenced by rv1 and rv2, and write the value representing that union into the data referenced by the this pointer.
Write a main program that calls your Set member functions, and tests each of them thoroughly. This test harness program, and any I/O which you do, should be guarded using #ifdef ... #endif. Be sure to test boundary cases involving multiples of 32 plus (0,1,-1), and other gross boundary conditions.
Turn in:
- your files (including the Set implementation) electronically, and:
- double sided print outs of your changed implementation, with your changes clearly highlighted with highlighter pen.

401admin@cs.washington.edu (Last modified: 27Oct97)