Machine Problem 3, due Mar 18 25
Part of
the homework for 22C:60 (CS:2630), Spring 2013
|
Background: Consider the problem of representing a tree where each item in the tree has a value and an arbitrary number of children. There are many possible solutions to this problem:
All of the above alternatives can be made to work. The first midterm will definitely include questions focused on at least two of these alternatives.
For this assignment, focus specifically on the second alternative, where each node contains a pointer to a null-terminated character string as the value of each item. Here is SMAL code to construct a 3-node binary tree using this representation:
NULL = 0 ROOT: W ROSTR ; value W LEFT ; child[0] W RIGHT ; child[1] W NULL ; child[2] ROSTR: ASCII "This ",0 ALIGN 4 LEFT: W LESTR ; value W NULL ; child[0] LESTR: ASCII "might ",0 ALIGN 4 RIGHT: W RISTR ; value W NULL ; child[0] RISTR: ASCII "work.",0
Traversing the above tree in pre-order (that is, listing the value of the child before the values of each of its children) would output "This might work." If you were writing the traverse routine in C or C++ using Hawk monitor routines for output, it might look something like this:
traverse( node * p ) { int i = 0; puts( p->value ); while ( p->child[i] != NULL ) { traverse( p->child[i] ); i = i + 1; } }
A minimal SMAL Hawk main program that calls the traverse routine and passes it the above test data might look like this:
MAIN: STORES R1,R2 LIL R3,ROOT ; -- parameter ADDI R2,R2,ARSIZE LIL R1,TRAVERSE JSRS R1,R1 ; traverse( root ) ADDI R2,R2,-ARSIZE LOADS R1,R2 JUMPS R1 ; return
The Assignment: Write a well commented SMAL Hawk subroutine called TRAVERSE that functions as described above. That function, should sit, by itself, in a file structured as follows:
TITLE "mp3.a -- Your Name Here" USE "hawk.h" USE "monitor.h" INT TRAVERSE ; your code goes here END
Testing Your Code: To test your program, you will need to link it with the test program. To do so, use the following line to link your code:
link mp3.o mp3test.o
We have written the mp3test program to provide test data for your program. It is based on the suggested main program given above, but with more ornate test data. It is the main progra, so your file mp3.a only needs to hold the subroutine, with no need for its own main program. The object file mp3test.o is in the Hawk system library so you don't need a copy of it in your own directory. Feel free, however, to write your own main program with your own test data to test your subroutine. Do not include your test program in your submission!
Hints: The high-level language code given above contains the expression: p->child[i]. This means: The ith element of the array which makes up the child field of the structure (or object) pointed to by p. To compute this, you will need to do the following:
Multiplication by 4 can be done with SL Rd,2. This is much faster than calling a multiply subroutine (and it involves writing much less code). The instruction ADDSL Rd,Rs,2 combines an add with a shift, adding 4 times Rd to Rs and putting the result in Rd.
Turn In Your Work: Use the divms coursework submission tools to submit your solved work. Your assignment must be in a file named mp3.a and you must submit it as a solution for mp3 in the course c_060. You may re-submit your work, so if you have something you think might be worth submitting, submit it, and if you improve on that solution, submit again.
Half of the credit for this assignment will be based on whether your code works. The other half will be based on the quality of your code, readability and clean concise comments are more important than efficiency, but code that serves no purpose will be penalized.
A major penalty will be assessed for failing to follow the basic requirement for a TITLE line on your program that gives your name!