CS 211 - Assignment 7

Date handed out: November 11th, 1999

Due date: November 18th, 1999

1. Write a method that takes two sorted lists L1 and L2 as input, and produces a sorted list L3 as output, where L3 is obtained by merging the elements of L1 and L2 as in mergesort. This method must not alter L1 and L2, so L3 must not share any elements with L1 or L2. You may assume that the data values in L1 and L2 are of type Comparable, and that the elements of both lists are sorted in ascending order. Show the output of your program for some sample lists of your choice, in which elements are of type StudentRecord.

2. Write another method for merging two sorted lists L1 and L2 that creates the merged list by changing the references in L1 and L2. That is, this method does not allocate any new elements but simply merges the two lists in-place. You may assume that the data values in L1 and L2 are of type Comparable, and that the elements of both lists are sorted in ascending order. Show the output of your program for some sample lists of your choice, in which elements are of type StudentRecord.

3. In this problem, you must extend the simple expression compiler you implemented in a previous assignment so that it works for a small language with variables and assignment statements. Programs in this language have a single method called main that does not have any parameters. The body of this method has a variable declaration, and a set of statements. A statement is either an assignment statement or a return statement. Here is a program in this language:

   
   main() {
   	int x, y, z;
   	x = 0;
   	y = (x + 9);
   	x = (x + y);
   	z = x;
   	return z;
   }
   
   

    

   Here is the grammar for this language.

   Program -> main()
   	   {
   		Declaration			
   		StatementSequence
   	   }
   
   
   Declaration -> int VarList ;
   
   VarList -> word
   VarList -> word, VarList
   
   StatementSequence -> Statement StatementSequence
   StatementSequence -> Statement
   
   Statement -> word = Fpe ;
   Statement -> return Fpe ;
   
   Fpe -> word
   Fpe -> integer
   Fpe -> (Fpe + Fpe)
   Fpe -> (Fpe - Fpe)
   Fpe -> (Fpe * Fpe)
   

    

   Allocation of memory  for storing variables:

   Storage for the return value and program variables must be allocated on the stack. Here is how storage allocation works.

    

   Location 0: return value is stored there at end of program execution

   Location 1,2...n:

   if there are n local variables, first one is allocated location 1 on stack, second one is allocated location 2 on stack, etc.

    

   So for our example, here is how the bottom part of the stack will look:

    

   Stack Location	Memory Contents	Register Values
   4	...	< SP points to location 4
   3	value of z
   2	value of y
   1	value of x
   0	return value	< FBR points to location 0

    

   This is called the stack frame for this method. Storage for the return value and variables is allocated by adding "n+1" to the stack pointer, where n is the number of variables in the Declaration. See the code below for an example.

   The region of stack above this frame (locations 4 and up) are used for pushing and popping values during evaluation of expressions.

   When the program terminates, it must leave return value in location 0, and storage for variables must be deallocated. This is accomplished simply by setting SP to 1.

    

   Addressing variables

   Variables are always accessed as offsets from the FBR which we will assume always contains 0. For our example, we would store 0 into x with the following SaM code:

   
   PUSHIMM 0  //this pushes 0 on top of stack
   STOREOFF 1 //pop top of stack and store it into location at
              //offset of 1 from FBR (ie., x)
   

   Your code generator must create a Hashtable (see the description in java.util) and store (variable,offset) pairs in it as it reads in the Declaration. The Hashtable is an implementation of the Map interface (see the java.util package). This hashtable is called the symbol table in the compiler literature. During code generation, you can look in this symbol table for the offset of a variable by using the get method of the Map class.

    

   Examples

   • x = 0;
     
     PUSHIMM 0   //push 0 on Top of Stack (TOS)
     STOREOFF 1  //pop TOS and store into x
     

   • y = (x + 9) ;
     
     PUSHOFF 1 //push value of x on TOS
     PUSHIMM 9
     ADD
     STOREOFF 2
     

   • return z ;
     
     PUSHOFF 3
     STOREOFF 0 //store return value
     ADDSP -3   //deallocate space for local variables
     STOP
     

    

   SaM code for the example program above

   ADDSP 4 //allocate space for return value,x,y,z
   
   // x = 1;
   PUSHIMM 1
   STOREOFF 1
   
   // y = (x + 9) ;
   PUSHOFF 1
   PUSHIMM 9
   ADD
   STOREOFF 2
   
   // x = (x + y);
   PUSHOFF 1
   PUSHOFF 2
   ADD
   STOREOFF 1
   
   // z = x;
   PUSHOFF 1
   STOREOFF 3
   
   // return z ;
   PUSHOFF 3
   STOREOFF 0
   ADDSP -3 //deallocate space for local variables
   STOP
   

    

   Implementation hints

   Your code generator must be written as a set of recursive methods. There is one method for reading in and generating code for each of the constructs in the grammar. These methods are described briefly below. (You may pass additional parameters to the methods, if necessary)

   public static String getProgram(String fileName)
   //this is the top level method that reads in the program
   //from the file and generates code for it. It calls the other methods
   //to help it read in and generate code for the various
   //constructs in the grammar
   //This method also creates the symbol table and passes it
   //to the helper methods it invokes.
   
   public static void getDeclaration(Map SymbolTable)
   //this reads in the Declaration in the program and store identifiers
   //and their offsets into the symbol table that is passed
   //in as a parameter
   
   public static String getStatementSequence(Map SymbolTable)
   //this reads in a sequence of statements, calling
   //getStatement as a helper method, and returns the
   //SaM code for executing these statements.
   //Hint: to determine if it has more statements to get from the input file,
   //it should do a peek to see if the next thing in the input is '}'.
   
   public static String getStatement(Map SymbolTable)
   //this reads in a single assignment statement or return
   //statement and returns code for executing it.
   //It calls getFpe as a helper method to read in fpe's.
   
   public static String getFpe(Map SymbolTable)
   //this is an extended version of the method you wrote in a
   //previous assignment that can read in expressions with variables
   
   

   What to submit

   1. A well-documented copy of your code for reading in a program and generating SaM code. You may assume that the name of the file containing the program will be passed to you as a command line parameter. You may assume that the program is legal, so you do not have to check for errors.
   2. The SaM code produced by your code generator for the simple program discussed above.
   3. The SaM code produced by your code generator for the following program:

      
      main() {
      	int x, y;
      	x = 2;
      	y = ((x + 3) * (x - 3));
      	return (x + y);
      	x = 5;
      }
      

   4. The last assignment statement in the program in part (c) is never executed, so it is known as "dead code". Explain briefly how you might modify your code generator so that it does not produce SaM instructions for dead code. You do not have to implement this optimization.