Machine Problem 1, due September 13
Part of
the homework for 22C:60, Fall 2008
|
Submit the source file mp1.a
for your solution using the submit command, documented at:
--
http://www.divms.uiowa.edu/help/msstart/submit.html
Construct a binary tree that represents the following string:
(Construct((a((binary)tree))that(represents(the((following)string)))))
The notation used here to represent a tree is based on the following idea: Each leaf of the tree is a parenthesized word, for example (word). Internal nodes of the tree include either a left child, as in ((left)word), a right child, as in (word(right)) or both, as in ((left)word(right)).
The particular string you are to represent represents the grammar of the first sentence above. The root is the verb construct. The subject is empty, because the imperitive sentence construction in English has an implied subjec of you. The object of the sentence is a long-winded compound noun phrase that pivots on the word that.
Each node in the tree is represented by a record consisting of a possibly null pointer to the left subtree, a possibly null pointer to the right subtree, and a null-terminated string representing the text of this word. Each node must be aligned on a word boundary.
A skeleton solution for this problem has been distributed on-line. You
can cut and paste, download, or otherwise work from this solution to flesh
out a complete solution to this problem.
--
http://homepage.cs.uiowa.edu/~dwjones/assem/hw/mp1.txt
This skeleton includes a code framework to link the data structure to a
test program that traverses the data structure.
Note that the skeleton has the ending .txt so that web browsers
will correctly show it as plain text. When you construct your solution,
please change the file name so it ends .a.
After you follow the
instructions in the Getting Started document, you can test your solution.
The Getting Started document is on line at:
--
http://homepage.cs.uiowa.edu/~dwjones/assem/hawkhandout.shtml
To assemble your solution -- that is, to translate your assembly code in the file mp1.a into object code in the file mp1.o, type the Unix shell command:
smal mp1.a
This will assemble your code, and it will produce error messages if your code contains syntax errors, undefined symbols or anything similar. You can examine the listing mp1.l with any text editor or with the following command.
more mp1.l
The listing file mp1.l holds a textual representation of the object code, along with the source, with the errors underlined. The more command allows you to page through any text file. The spacebar advances through the listing one screenfull at a time.
Once you have assembled your code, you can link it with the test program using the command:
link mp1.o mp1test.o
This produces an executable file, link.o. You should not encounter any linker errors unless you damage the skeleton provided on line. Specifically, if you alter the line with the INT command, preventing the test program from finding the root of your tree, or if you fail to define the symbol ROOT, it will not link properly.
Finally, to run your program under the Hawk emulator, type this command:
hawk link.o
For now, we can ignore most of the output of the emulator. What is important is that the middle line on the emulator display is a command prompt, and that the command r standing for run causes the emulator to run the test program on the data to which it has been linked. The output appears below this line when the program runs. The command q means quit and will get you out of the emulator back to the command line.
If your program runs correctly, the output should be a parenthesized string representing the tree you constructed. The most likely errors are infinite loops, caused by loop structures in the pointers making up the tree, or bus trap errors caused by pointers into random memory locations. We strongly recommend incremental development, testing the initial tree, then adding a node, then testing that, then adding a node, in order to localize the effects of errors.