10.5. Sprünge

Ein veraltetes Sprachelement, das von Java nicht mehr unterstützt wird, ist die Sprunganweisung:

goto marke; // kein Java

Das Sprungziel wird dabei durch eine im Sprungmarke gekennzeichnet:

marke: ... // Anweisungen

Obwohl dieses Sprachelement in Java nicht vorkommt, ist es nützlich, es zu untersuchten. Der Compiler übersetzt nämlich die Steuerstrukturen auf Sprünge in Bytecode.

10.5.1. Unstrukturierte Algorithmen

Es wurde bewiesen, daß jeder Algorithmus, der mit Hilfe von Sprüngen formuliert wurde, auch ohne Sprünge (d.h. nur mit Fallunterscheidungen und Wiederholungen) formuliert werden kann. Die Strukturierung von unstrukturierten Algorithmen ist wichtig beim software recycling, d.h. bei der Entwicklung einer Neufassung alter Programme, die unstrukturiert entwickelt wurden. Die allgemeine Methode ist recht komplex, einfachere unstrukturierte Algorithmen können jedoch durch Nachvollziehen des Ablaufs strukturiert werden:

if (bedingung1) goto marke1; // nicht in Java
... // Anweisungsfolge 1
if (bedingung2) goto marke2;
marke1: ... // Anweisungsfolge 2
marke2: ;

Dieser Programmausschnitt ohne Rücksprung kann durch die Verdopplung einer Anweisungsfolge strukturiert werden:

if (bedingung1)
	... // Anweisungsfolge 2
else {
	... // Anweisungsfolge 1
	if (bedingung2)
		... // Anweisungsfolge 2 - Verdopplung
}

Wenn der Programmausschnitt auch einen Rücksprung enthält, kann er endlos laufen:

if (bedingung1) goto marke1;
marke2: ... // Anweisungsfolge;
marke1: if (bedingung2) goto marke2; // Rücksprung

Daher muß er mit Hilfe von Wiederholungen strukturiert werden:

if (bedingung1)
	do
		... // Anweisungsfolge;
	while (! bedingung2);
else
	while (bedingung2)
		... // Anweisungsfolge;

Übung 10.15: Strukturieren Sie den folgenden Programmausschnitt mit einem geschachtelten Rücksprung; er muß mit einer geschachtelten Schleife strukturiert werden:

marke1:
... // Anweisungsfolge 1;
marke2:
if (bedingung1)
	goto marke1; // Rücksprung
... // Anweisungsfolge 2;
if (bedingung2)
	goto marke2; // Rücksprung

10.5.2. Steuerstrukturfreie Programmiersprachen

Sprünge werden trotzdem häufig verwendet: Es gibt eine Reihe von Programmiersprachen, die keine Steuerstrukturen als Sprachelemente anbieten. Sie sind meistens maschinennahe Sprachen wie eine Maschinensprache oder eine Assemblersprache. Ein Programmierer, der auf solchen Sprachen programmieren und daher goto's verwenden muß, kann trotzdem strukturierte Programme erstellen. Er muß dabei seinen Algorithmus auf einer höheren Sprache oder mit Hilfe von Struktogrammen formulieren. Anschließend kann er die Steuerstrukturen mit Hilfe der zur Verfügung stehenden Sprunganweisungen simulieren. Diesen Vorgang nennen wir Entstrukturierung.

Die meisten dieser einfachen Sprachen bieten eine Anweisung an, der bedingter Sprung heißt:

goto (bedingung) marke; // nicht in Java

Die Sprunganweisung ist ein Spezialfall mit der konstanten Bedingung true.

Mit Hilfe dieser einzigen Anweisung können alle Steuerstrukturen simuliert werden. Die allgemeine Fallunterscheidung

switch (diskreterWert) {
	case wert1: ... // Anweisungsfolge 1;
		break;
	case wert2: ... // Anweisungsfolge 2;
		break;
		...
	case wertN: ... // Anweisungsfolge n;
		break;
	default: ... // Anweisungsfolge n+1;
}

kann folgendermaßen übersetzt werden:

goto (diskreterWert == wert1) marke1;
goto (diskreterWert == wert2) marke2;
	...
goto (diskreterWert == wertN) markeN;
goto (true) markeN1;
marke1: // Fall für wert1
... // Anweisungsfolge 1
	goto (true) markeN2;
marke2: // Fall für wert2
... // Anweisungsfolge 2
	goto (true) markeN2;
	...
markeN: // Fall für wertN
... // Anweisungsfolge n
	goto (true) markeN2;
markeN1: // Fall default
... // Anweisungsfolge n+1
markeN2: ; // Ende der Fallunterscheidung

Hierbei müssen bei der Übersetzung jeder Fallunterscheidung neue Marken erzeugt werden. Die einfacheren Fallunterscheidungen (Einweg und Zweiweg) können als Sonderfälle, möglicherweise vereinfacht übersetzt werden.

Die allgemeinste, die rumpfgesteuerte Schleife

while (true) {
	... // Eins-Block
if (abbruchbedingung) break;
	... // Null-Block
}

wird mit dem bedingten Sprung folgendermaßen ausgedrückt:

anfang:
... // Eins-Block
goto (abbruchbedingung) ende;
... // Null-Block
goto (true) anfang;
ende:

Die Marken anfang und ende stehen hier stellvertretend für irgendwelche Marken. Die einfacheren Wiederholungen werden als Sonderfälle der rumpfgesteuerten Schleife, eventuell vereinfacht abgebildet.

Geschachtelte Steuerstrukturen werden geschachtelt übersetzt. Beispielsweise kann der Programmausschnitt

if (bedingung1) {
	while (true) {
		... // Anweisung 1
		if (bedingung2)
			... // Anweisung 2
	if (bedingung3) break;
		... // Anweisung 3
	}
}

folgendermaßen übersetzt werden:

goto (! bedingung1) neinBedingung1;
	schleifenanfang:
		... // Anweisung 1
		goto (! bedingung2) neinBedingung2;
			... // Anweisung 2
		neinBedingung2:
	goto (! bedingung3) schleifenende;
		... // Anweisung 3;
	goto (True) schleifenanfang;
	schleifenende:
neinBedingung1:

Übung 10.16: Entstrukturieren Sie das Programm, das Sie in der Übung 10.15 durch Strukturierung erhalten haben.

Übung 10.17: Entstrukturieren Sie das Programm aus der Übung 10.8 auf Seite 233.