Machine Problem 3, due Mar. 9

Part of the homework for CS:2630, Spring 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

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

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


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.


For full credit:

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.