Binary Tree Manipulation mit dem 8080

VON MIKE GABRIELSON Box 2692 Stanford, Calif. 94305

Stellen wir uns vor, wir schreiben einen Compiler. Wie soll die Symboltabelle organisiert werden? Eine Möglichkeit ist die Benutzung eines binären Baumes. Abbildung 1 stellt einen binären Baum mit sieben Symbolen dar (Zeichenketten repräsentieren Variablen-Namen). Jedes Symbol ist eingebunden in einen Knoten (Node) zusammen mit zwei Zeigern. Die Zeiger werden benutzt, um die Knoten des Baumes zu verbinden. Ein spezieller Zeiger, genannt Root, zeigt auf den obersten Knoten im Baum. (Computerbäume wachsen von oben nach unten.) Geerdete Zeiger der alleruntersten Knoten zeigen auf nichts.

Beim 8080 und ähnlichen Computern kann ein Zeiger durch eine 16 Bit Adresse dargestellt werden und jedes Symbol durch eine ASCII Zeichenkette. Abbildung 2 zeigt einen Teil unseres Baumes, wie er tatsächlich an einer beliebigen Stelle im Speicher abgelegt werden könnte. Es wird festgelegt, dass ein geerdeter Zeiger belegt wird mit dem Wert Null und und jede Zeichenkette beendet wird mit dem Zeichen NUL. Eine echte Symboltabelle für einen Compiler würde in jedem Knoten einige zusätzliche Bytes für Kontroll- und andere Informationen über das jeweilige Symbol beinhalten. Dies wird aber hier der Einfachheit halber in den Beispielen weggelassen.

Die Symbole in unserem Baum werden auf eine besondere Weise angeordnet: wenn wir einen Knoten auswählen, so finden wir, dass der linke Zeiger (so er nicht geerdet ist) auf einen Unterbaum weist. Dieser enthält Symbole, die alphabetisch vom Wert kleiner sind (absteigend) als das Symbol im Knoten. In ähnlicher Weise enthalten die rechten Zeiger den Verweis auf einen Unterbaum, dessen Symbole alphabetisch alle größer (aufsteigend) sind als das Symbol im Knoten. Die Pflege des in dieser Weise angeordneten Baumes erlaubt uns die Gestaltung sehr einfacher aber leistungsfähiger Algorithmen zur Handhabung von Daten im Baum. Als Beispiel sei angenommen, dass unser Compiler Zugriff auf ein Symbol im Baum benötigt. Wie soll der Baum durchsucht werden? Beginnend mit dem ersten Knoten (auf den Root verweist), vergleichen wir das Symbol des Knotens mit dem Symbol, nach dem wir suchen. Stimmt der Vergleich, dann ist die Suche beendet. Wenn unser Symbol kleiner ist als das Symbol des Knotens, dann folgen wir dem linken Zeiger des Knotens und wiederholen den Vergleich mit diesem Knoten. Wenn unser Symbol größer ist, dann wählen wir den rechten Unterbaum und so weiter an den Abzweigungen, bis wir eine Übereinstimmung finden oder einen geerdeten Zeiger, der anzeigt, dass das Symbol nicht im Baum enthalten ist. Das Beispielprogramm, genannt SEARCH, sucht in einem binären Baum wie dem unserem, wobei es eben diesen Algorithmus verwendet.

Wie lassen wir nun einen Baum als erstes wachsen? Ein notwendiger Bestandteil für das Wachsen eines Baumes ist Speicher. Nehmen wir an, wir haben Zugriff auf zwei neue Zeiger. Ein Zeiger heißt FIRST und ist die Adresse auf das erste Byte eines zusammenhängenden Speicherbereiches, das für den Baum zur Verfügung steht. Der Zeiger auf das letzte Byte in diesem Bereich heißt LAST. Diese Anordung verdeutlicht Abbildung 3.

Abbildung 3. Speicherbelegung

Immer wenn unser Baum ein Byte zum Wachsen benötigt, kann er das Byte, auf das FIRST zeigt, aufgreifen und dann FIRST erhöhen. Der Speicher ist ausgeschöpft, wenn FIRST größer wird als LAST. Nun können wir unserer Suche so abändern, dass, wenn ein Symbol nicht im Baum enthalten ist, automatisch ein neuer Knoten dafür angelegt wird. Das nächste Unterprogramm, genannt LOOKUP, hängt bei Bedarf neue Symbole an den Baum an. (Um das Programm einfach zu halten, wird in dieser Version von LOOKUP keine Überprüfung durchgeführt, ob FIRST größer wird als LAST, was einen Speicherüberlauf anzeigt.) Ein Beispiel, LOOKUP aufzurufen, zeigt folgender Programmausschnitt

	LXI	B,STRING	;get address of string
	LXI	H,ROOT		;get address of ROOT
	MOV	D,M		;get contents of ROOT
	INX	H
	MOV	E,M
	DCX	H		;restore address of ROOT
	XCHG			;adjust registers for LOOKUP
	CALL	LOOKUP

Der Aufrufablauf kann vereinfacht werden, wenn die Inhalte der 16-Bit Root und der Knotenzeiger gehandhabt werden im Standard-Intel-Format - also in umgedrehter Reihenfolge - anstatt in nicht gedrehter Reihenfolge, wie es aktuell vorgesehen ist. Die Änderung der Kodierung, so dass alle Zeiger in gedrehter Form vorliegen, ist eine leichte Übung für den Leser. Abbildung 4. zeigt, wie der Baum gewachsen ist nach dem Aufruf von LOOKUP für das Symbol THETA.

Eine gute Einrichtung für unseren Compiler wäre die Fähigkeit, die Symboltabelle in alphabetischer Reihenfolge auszugeben. Wie können wir unseren Baum auflisten? Aufgrund der Art, wie der Baum angeordnet ist, können wir einen eleganten Algorithmus benutzen, der wie folgt funktioniert: vor der Ausgabe eines beliebigen Knotens wird erst der Knoten (oder Unterbaum, falls vorhanden), auf den links gezeigt wird, ausgegeben. Danach den Originalknoten und dann den Knoten (Unterbaum), auf den rechts gezeigt wird. Gestartet wird mit dem Knoten, auf den Root zeigt, aber zuallererst wird versucht, den linken Unterbaum eines jeden Knotens zu durchlaufen.

Das ist ein rekursiver Algorithmus, der einfach programmiert werden kann an Maschinen mit einem Stack wie bei der 8080. Das letzte Beispielprogramm ist eine rekursive Routine, genannt PUTREE, die unseren Baum ausgibt, wobei eben dieser Algorithmus verwendet wird. Ein Beispiel, um PUTREE aufzurufen, ist

	LHLD	ROOT	;get contents of ROOT
	MOV	A,H	;swap H and L
	MOV	H,L	;to be consistent with 
	MOV	L,A	;rest of tree
	ORA	H	;is root grounded?
	CNZ	PUTREE	;no, output tree

Abbildung 5. Baumdurchquerung

Ich habe für die drei Assemblerroutinen (Z80-Version) ein kleines Testprogramm geschrieben: BINTREE.MAC. Hierzu müssen die Module LOOKUP, PUTREE und SEARCH assembliert werden sowie das Programm BINTREE. Anschließend alle Module linken (z.B.: LINK TEST=LOOKUP,PUTREE,SEARCH,BINTREE). Danach das Programm (im Beispiel TEST) aufrufen.