Machine Problem 3, due Mar. 9

Background: Consider the problem of traversing an n-ary tree. Each tree node has the following structure:

• Word 0: The X (low halfword) and Y (high halfword) coordinates of the text.
• Word 1: Pointer to the text.
• Words 2 through n+2: Pointers to the n children of this node.
• Word n+3: A null pointer.

Note that each node may have a different number of children. Here is an example that, when traversed, outputs the string "hello world" starting at line 1, column 1 of the screen:

        TITLE   "mp3test.a -- test data for MP3"
        INT     ROOT

NULL    =       0

ROOT:   ; a node
        H       1,1
        W       TEXT1
        W       SON1,SON2,SON3,NULL

SON1:   ; a node
        H       3,1
        W       TEXT2
        W       GSON1,GSON2,NULL

SON2:   ; a node
        H       5,1
        W       TEXT3
        W       NULL

SON3:   ; a node
        H       7,1
        W       TEXT4
        W       NULL

GSON1:  ; a node
        H       9,1
        W       TEXT5
        W       NULL

GSON2:  ; a node
        H       11,1
        W       TEXT6
        W       NULL

TEXT1:  ASCII   "hel",0
TEXT2:  ASCII   "l",0
TEXT3:  ASCII   "o ",0
TEXT4:  ASCII   "wo",0
TEXT5:  ASCII   "rl",0
TEXT6:  ASCII   "d",0

        END

Assignment: Write a SMAL Hawk main program that traverses the tree provided in mp3test.o and prints every string in that tree at the indicated coordinates on the display screen. You do not know in advance how deep the tree will be nor the number of children in each node.

Your program should reference an external symbol (defined with the EXT directive) which is the address of the root node of the tree. To run your program, you will have to link it with an object file that defines this root. Assembling the example above will produce an appropriate object file.

For small scale testing, you can link it with the object code produced by assembling the above example code, or even construct simpler examples such as a tree with just one node.

We will test the program against the file mp3test.o that is in the class support directory. If you have no file by this name in your directory and you link your object code with this file, you will see the test output.

Requirements:

For full credit:

• Your source code must be well formatted. Tabs to align columns appropriately are required.
• Your source code must appropriately commented. Write comments that say why, not merely what. Comments should be written assuming that the reader the language. If some register is consistently used to hold some logical variable, say so!
• Your source code should have a TITLE directive that (in as few words as possible) gives your name (as it appears on the class list) and the fact that this is MP2. We will not do detective work to link solutions to students. Failure to meet this requirement may result in total loss of credit.
• Your code should make appropriate use of subroutines, activation records and recursion, appropriate documentation.
• Additional header comments that clearly explain what is going on are welcome, but do not belabor the obvious.
• When run, your code must produce the expected output.

Submission: Programming assignments will be submitted on-line using the on-line Online Coursework Submission tool provided by the Liberal Arts Linux server cluster. The user interface for this is awful, but but it works. Your source file must be named mp3.a (the name is case-sensitive). This is the name you will type in response to the File/directory name prompt. When the submission tool prompts for Course type cs_2630. Select the assignment directory mp3.

You must submit your work using the submit command from the a CLAS Linux machine. If you make repeated submissions, only the last one will count.

Warning: There will be questions on the Midterm on Mar 6 that you will only be able to answer if you have begun work on this assignment before the exam.

Note added Mar 3: Several students have asked how to link their main program and recursive subroutine (in file mp3.a) to the test data.

First, in your main program, you need to declare ROOT as follows:

        EXT     ROOT

This tells the assembler that ROOT will be declared somewhere else. Once you have this definition, it is legal to do things like LIL R3,ROOT (for example).

Once you've done this, you can assemble link and run main program with the following sequence of UNIX/LINUX shell commands:

smal mp3.a
link mp3.o mp3test.o
hawk link.o

If you have not assembled your own version of mp3test.a, you will get the official test data. If you have assembled your own version, you will get that. If you have assembled your own version, you can always delete your mp3test.o file in order to use the official version.

If your test data is in a file with a different name, say it is in mytest.a, you can assemble that and test your main program with your data using:

smal mp3.a
smal mytest.a
link mp3.o mytest.o
hawk link.o

Some students have speculated about using USE directives to access the test data. Don't do this. It will make your code incompatable with the official test data, and as a result, it will not work when the TA grades it.