The aim of this practical is to make you more familiar with calling sequences which use the stack both to pass parameters and to allocate local variables. Calling sequences are very important, as is stack management.
You must understand this material if you intend to study future Computer Science courses such as Computer Architecture, or Language Translators. You will be constructing your program from multiple source files that must be linked together with some library modules we provide. This will give you experience in seeing how the process of linking works.
1.2 Overview of the assignment
This practical consists of writing recursive functions to create and traverse a binary search tree. You should put the functions in the file tree.dls You will write the functions in assembly code, and combine them with other functions that are provided.
All functions must be relocatable and use .import and .export directives to permit linking. Use four segment names in your program: Code, for instructions; Constant, for any constant data; Heap, for data allocated from the heap; and Stack, for the stack, which will hold all variables. You will not need a Data segment.
1.3 Starting files
The startup files for this assignment are available in the prac4supp directory. The files provided are:
• tree.dls - A skeleton of the file to contain your binary search tree functions;
• divide.dls - file containing divide functions;
• dsim.cfg - A DLX simulator configuration file;
• init.dls - A file containing stack initialisation code;
• input1 - A sample input file;
• input2 - A sample input file;
• io.dls - A file containing the keyboard and display I/O routines;
• main.dls - A file containing the main program;
• heap.dls -A file containing the heapGet function;
• output1 - The program output corresponding to input1;
• output2 - The program output corresponding to input2;
• readdata.dls - A file containing the readData function; and
• strings.dls - A file containing some string handling routines;
11.4 Operation of the program
The main program is already complete, and does not need to be changed. It reads the numeric from the terminal device, by calling readData. The readData function expects lines of text that contain one or two integer values separated by a comma. It stores the data it reads into an array that was passed to readData as a parameter. A line may have additional space characters before and/or after each number. Here are some example lines of input:
123,456 two numbers: 123 and 456
4 , 6 two numbers: 4 and 6
1,2,3,4 two numbers: 1 and 2 (third and subsequent numbers ignored)
1 2 3,4 one number: 1 (missing comma)
The main then repeatedly calls tInsert, to isnert data into the tree. On each call it passes one of the numbers that was stored in the array by readData. main then calls tP rint to print out the structure of the tree. (If all is well, the data will appear in increasing order.)
main then calls tRev, which reverses the tree, so that the largest number in the tree is on the left, and the smallest number on the right.
Finally, main again calls tP rint to print out the structure of the tree. (If all is well, the data will now appear in decreasing sorted order.)