x Programming Assignment 2 Computer Science 102

Programming Assignment 2

Computer Science 102

Spring 2001

First draft due MON, FEB 19, 11:59 pm (midnight). Each successive draft is due one week after the due date for the previous draft .

Your project is to design a program to implement string operations. The final version will be a string program interpreter. Recall that in Java there is already a String class. A String is a linked list of characters, plus a node that indicates how many characters are being stored. You are to implement an alternative string class, called StringADT, that does not store the length -- it will be determined by one of the methods --it just stores each character in a node of the linked list.

For example, to represent the string 'comp', you can use the following linked list.

        _______     ______     ______     ______
list--> |_C|___|--> |_O|__|--> |_M|__|--> |_P|__|-->null

Your project divides into two parts:
  1. A StringADT class that will implement several string operations,
  2. A client class that will use the StringADT class to implement an interpreter for strings assigned to one-letter variables,

The StringADT class

In the class StringADT, you will implement an abstract data type, that will allow several useful string operations. The interface that this class will implement is given below and is also a link on the homepage that you will be able to download.

public class StringADT
 public void concat(StringADT list1, StringADT list2) 
//Precondition: the lists exist or are null.

/*Postcondition: the implicit parameter this points to the
concatenation of list1 and list2; the nodes of the conatenated are separate
from the nodes of list1 and list2.*/

public void copy(StringADT list1 );
//Precondition:  the list exists or is null .
//Postcondition:  this points to a a copy of list1.  
//The nodes of the copied list are separate from the nodes of list1.

public void repeats(StringADT list1 ,int n); 
//Precondition: n >= 0.
/*Postcondition: this points to the concatenation of n copies of
list1.  If n = 0, then the copied list is the empty string represented by a
linked list consisting of only the null pointer.*/

public assign(StringADT list1);
//Precondition: None.  (Notice that list1 is a Java string.)
//Postcondition: this points to the link list
//representing the string as list1.

public substring(StringADT list1 ,int x, int y):

//Precondition: 0<= x <= y < leng(list1).  
/*Postcondition: this points to the link list representing the
substring of list1 that goes from the xth indexed character to the yth indexed

public leng(list1 : string_type) : integer;
{Precondition: None.
 Postcondition: Returns the number of characters of list1.}

public Print(StringADT list1);
//Precondition: list1 exists or is null
//Postcondition: Displays the characters of list1 on the terminal. 

//private Link head;
//This cannot be included in the interface

Encapsulation dictates that the class's field be declared private. Thus the private field cannot be used as a parameter for the methods of the object; however as we see here, the object -- list1 -- can. Also, the private field cannot be included in the ADT -- an interface cannot contain variables. However, you must include it in your StringADT class in your program. When you finish your StringADT class and have implemented all the methods, change the public class statement so that it ends with implements ADT, e.g., public class StringADT implements ADT. Once you indicate that your class implements the interface, all of its methods must be included in your StringADT class, so it you implement the iterface when you are developing your methods, you should supply dummies for the methods not yet written.

Draft 1

For draft 1, you are required to first write a class called StringADT which contains as methods the usual string operations: assignment (x = "nyu"), concatenation (z = x + y), multiplication (w = 12 * z), substring (w = x [2,5]), copying (u = x), and printing. These operations are to be implemented with linked lists. The private field of the class is a pointer to a linked list.

When you write the methods, remember that when you assign null to a pointer, you are assigning a new address to the pointer. What happens if Link p = new Link() and then q.next = p is executed? The answer is that p is the address stored in q.next. If another p = new Link() is executed, q.next is still the address stored in the old p. If p = null is executed instead, q.next is still the address stored in the old p and not null.

An example of a method heading is public assignment( StringADT st1); So if st1 is "nyu", the implicit parameter this is the object that contains the pointer to the first node of the three node linked list containing 'n', 'y', and 'u'. The object is defined and implemented in class StringADT. There is a class tester.java (available on the homepage) that checks your StringADT.

Draft 2

The Compiler Class
The Compiler class will be a string interpreter. In other words, the user will input a file with a series of string commands. The file is available on the web. After each command, your class will parse the command and then print out it's result. Each command will have one of the following forms:

  1. x = "Hello"
  2. x = y + z
  3. x = y
  4. x = 17 * y
  5. x = y [10,20]
  6. length x
  7. x
  8. quit

Here x, y, and z represent string variables (possibly the same variables). The only variable names allowed will be a single character, either a lowercase letter ('a' to 'z') or an uppercase letter ('A' to 'Z'). As in Pascal, an uppercase letter refers to the same variable as its lowercase counterpart.

Each of the tokens in the input line will be separated by one or more blanks. Your lexical analyser should use this fact to separate the tokens,

If the input line is not in one of the formats above, your class should print an error message, and then skip that input line. Similarly, if one of the variables on the right side of an assignment has not been initialized, your class should complain and skip that line. Use a symbol table to keep track of those variables assigned values. Also, the actual StringADT parameters should be elements of an array of StringADT.

Discussion and explanation
Draft 2 requires you to write a string interpreter that will execute an input stream of string operations. For instance, if the input is:

x = "nyu"
y= "hello"
z = y + x
where z is the instruction to print the string stored in z, then the result would be "hellonyu". A variable in the input can only be a single letter. The interpreter is not case sensitive, so that "z" and "Z" represent the same variable.

The front end of the interpreter breaks the input into constituent parts called tokens. Then in the parser, it determines which statement (assignment, print, etc.) a line of token represents. I have written the scanner for you, and the initial stage of the parser (again, these are available on the homepage in analyse.pas). The scanner is elementary because the tokens in the input must be separated by at least one blank. The parser indicates which method further parses a statement. The parsing up to this point is done simply by determining how many tokens appear in the input. Thus x = "hello" and x = y are parsed such that the same method is executed. It is up to you to further parse them by distinguishing between an assignment and a copy statement.

Use a symbol table to check whether a variable that must have a value in any operation, has in fact been assigned a value. This in x = y, you would check whether y has been assigned a value. Do this by using a globally declared array static boolean[] symbolTable, where the dimension of the array is 26. If the input contains an undefined variable, the interpreter must print an error message.

How do you associate a variable with the pointer to the linked list? The natural way is to have an array of the object, i.e., static StringADT[] table. Assume that if x = "nyu" and y = "hello"; and Px is the pointer to the linked list for x; and Py, for y, then Table['X'] contains Px and Table['Y'] contains Py.

How is this implemented? For instance in x = "nyu", stream[0] is "x", stream[1] is "=" and stream[2] is the string "nyu". First you must strip the quotes from "nyu". The quotes are the first and last elements of stream[2]. These are referred to as stream[2].charAt(0) and stream[2].charAt(4) respectively. The element of table is the implicit parameter of method assign. Remember that the header for the method is: public assign( String st). In order to have the pointer for the linked list that stores "nyu" being the contents of the element 'X' of Table, you must write:


where stripped is the assigned string with its quotes deleted (here, nyu); variable is the first character of stream[0] converted to an uppercase char variable; and sADT is the instance of StringADT. We subtract 'A' from variable in the brackets because we want the variable A to correspond to the zeroth element of table.

The data for draft 2 is also on the home page.

Deleting linked lists

When a variable is assigned a new string in a simple assignment statement, e.g.,
   x = "nyu"
   x = "jay"
if you assign a new pointer to x, the pointer for the linked list representing nyu will no longer be accessible. That means that the locations for n, y and u in the heap will consume heap memory and will no longer be addressable. We say that leakage has occurred. The portion of the heap that is inaccessible (here,that which stores nyu) is called garbage. A language like Lisp eliminates garbage by performing garbage collection. Java also does this. So in this project, this will be done automatically.