Zwischencode-Generierung

Teil 1: Grundlagen

Dies sind nur die Grundlagen für die Erzeugung von Zwischencode. Man kann diesen Teil überspringen, allerdings wird man dann nichts verstehen. In Teil 2 wird die eigentliche Aufgabe, die Definition der Logik des Compilers, erläutert.

Codes und Ausführungszeitpunkte

Für das Verständnis müssen wir drei verschiedene Codes bzw. Sprachen unterscheiden:

• Code der höheren Programmiersprache, die wir durch unseren Compiler verarbeiten wollen. In den Beispielen ist dies Pascal.
• Zwischencode, der durch unseren Compiler aus dem Code der höheren Programmiersprache erzeugt wird.
• Compiler-Code, der zur Definition der Logik unseres Compilers dient (die »semantischen Aktionen«).

Weiterhin unterscheiden wir zwei Ausführungszeitpunkte:

• Compilezeit, zu der der Compiler-Code ausgeführt wird und der Code der höheren Programmiersprache in den Zwischencode übersetzt wird.
• Laufzeit, zu der der Zwischencode bzw. der daraus wiederum erzeugte Assemblercode direkt auf der Maschine ausgeführt wird.

Das erste Licht im Dunkeln kann mit Bedingungen und Schleifen entzündet werden.

Bedingungen im Zwischencode

Betrachten wir folgenden Pascal-Code, den wir in Zwischencode überführen wollen:

        if variable1 < 5 and variable2 == 10 then
            variable1 = 10
    

Der Zwischencode unterstützt keine boolschen Operatoren mehr, wie hier and. Sie müssen daher durch mehrere verschachtelte Bedingungen abgebildet werden. Der Zwischencode unterstützt aber auch keine wirkliche Verschachtelung. Diese wird daher mit goto realisiert, durch die an beliebige Stellen im Zwischencode gesprungen werden kann.

Wir verwenden einen Bottom-up-Parser. Daher werden durch den Compiler die kleinsten Einheiten von links nach rechts zuerst verarbeitet. Vollziehen wir dies Schritt für Schritt nach, wird beim oben gegebenen Pascal-Code zuerst der Teil variable1 < 5, eine sogenannte Expression, verarbeitet.

Expressions sind Ausdrücke mit einem Wahrheitswert, dazu gehören Vergleichsoperatoren und boolsche Operatoren. Expressions können beliebig geschachtelt werden. Sie können schlussendlich als Bedingung in einem Statement, etwa einem if-Block oder einer Schleife, eingesetzt werden.

Für diese Expression soll der Compiler folgenden Zwischencode erzeugen:

        if variable1 < 5 goto ...    
        goto ...
    

Der Platzhalter ... bedeutet dabei, dass zu diesem Schritt der Compilezeit noch nicht bekannt ist, an welche Stelle das Programm zur Laufzeit hinspringen soll, wenn es das entsprechende goto erreicht. Anstelle der Platzhalter muss zu einem späteren Schritt während der Compilezeit daher noch jeweils eine Adresse (hier Zeilennummer) eingetragen werden, zu der dann zur Laufzeit durch Ausführung des goto gesprungen werden kann.

Der bisher erzeugte Zwischencode bewirkt also zur Laufzeit folgendes: Wenn die Expression variable1 < 5 wahr ist, springe an irgendeine (hier noch unbekannte) Stelle. Dadurch wird das goto in Zeile 2 übersprungen und nicht ausgeführt. Wenn aber die Expression in Zeile 1 falsch ist, wird das goto in dieser Zeile nicht ausgeführt und es wird der Reihe nach mit der nächsten Zeile fortgefahren. In Zeile 2 wird dann an irgendeine andere Stelle gesprungen.

Es handelt sich also um ein einfaches if-else, durch das an zwei verschiedene Stellen gesprungen werden kann, je nach dem, ob die Bedingung wahr (Gutfall) oder falsch (Schlechtfall) ist.

Setzen wir die Ausführung des Compilers fort, der dann die nächsten Zeilen Zwischencode generieren soll. Es wird einfach ein weiterer if-goto-Block für die zweite Expression hinzugefügt:

        if variable1 < 5 goto ...    
        goto ...
        if variable2 == 10 goto ...    
        goto ...
    

Nun wird der Compiler im Pascal-Code das umschließende and, das die beiden Expressions verbindet, erreichen. Bei diesem Schritt können einige Platzhalter, die noch im Zwischencode vorhanden sind, ausgefüllt werden, weil nun bekannt ist, wo das Programm zur Laufzeit hinspringen soll.

Bei der boolschen and-Operation gilt: Ist die erste Expression wahr, muss die zweite Expression ebenso überprüft werden. Ist die erste Expression aber falsch, braucht die zweite gar nicht mehr überprüft zu werden, da die and-Expression in keinem Fall mehr wahr werden kann. Es kann daher direkt in den else-Fall bzw. ans Ende des if-Blocks gesprungen werden.

        if variable1 < 5 goto 3    
        goto ...
        if variable2 == 10 goto ...    
        goto ...
    

Tatsächlich können wir leider erst einen Platzhalter ausfüllen: Wir wissen, dass zur Laufzeit, wenn die Expression in Zeile 1 wahr wird, zur Überprüfung der zweiten Expression in Zeile 3 gesprungen werden muss. In Zeile 2 muss an das Ende des if-Blocks gesprungen werden, es ist aber noch nicht bekannt, in welcher Zeile dieses Ende ist, da die entsprechenden Zeilen (zur Compilezeit) noch nicht erzeugt wurden. Dies gilt ebenso für Zeile 4.

Das goto in Zeile 3 soll als einziges zum Körper des if-Blocks springen, da nur dann gewährleistet ist, dass beide Expressions wahr sind (die erste Expression wurde ja bereits vorher überprüft). Auch die Position des Körpers des if-Blocks ist aber noch nicht bekannt. Es könnten ja theoretisch auch noch weitere Bedingungen hinzukommen, die noch nicht eingelesen wurden.

Setzen wir das Kompilieren fort. Als nächstes wird der Körper des if-Blocks erzeugt:

        if variable1 < 5 goto 3    
        goto ...
        if variable2 == 10 goto ...    
        goto ...
        variable1 = 10
    

In diesem Beispiel wird der Pascal-Code eins zu eins in den Zwischencode übernommen. Die Details interessieren uns hier nicht weiter. Im nächsten Schritt erreicht der Bottom-up-Parser das Ende und schließt somit den gesamten if-Block ab. Dabei kommen keine neuen Codezeilen mehr hinzu – die if-Statements im Zwischencode wurden ja bereits vorher bei den Expressions generiert. Es kann aber noch ein Platzhalter aufgelöst werden:

        if variable1 < 5 goto 3    
        goto ...
        if variable2 == 10 goto 5    
        goto ...
        variable1 = 10
    

Es ist nun bekannt, wo der Körper des if-Blocks beginnt: in Zeile 5. Daher wird in das goto in Zeile 3, der einzigen Stelle, bei der zum Körper gesprungen werden soll, die Zeile 5 als Ziel eingetragen. Die anderen beiden goto sollen ans Ende springen. Es ist weiterhin nicht bekannt, wo dieses Ende ist – es könnte ja noch weiterer Code unten hinzukommen. Diese Platzhalter können daher erst später aufgelöst werden, wenn der Pascal-Code um den if-Block herum, außerhalb dieses Beispiels, verarbeitet wurde.

Nehmen wir denselben Pascal-Code wie oben und ersetzen das and durch ein or, erhalten wir folgenden Zwischencode:

        if variable1 < 5 goto 5    
        goto 3
        if variable2 == 10 goto 5    
        goto ...
        variable1 = 10
    

Beim or gilt: Wenn die erste Expression wahr ist, kann bereits zum Körper des if-Blocks nach Zeile 5 gesprungen werden. Ansonsten muss die zweite Expression in Zeile 3 überprüft werden. Daher wird in Zeile 2 nach Zeile 3 gesprungen. Ist die zweite Expression wahr, kann ebenfalls nach Zeile 5 gesprungen werden. Nur falls nach der ersten auch die zweite Expression falsch ist, muss in Zeile 4 an das noch unbekannte Ende des if-Blocks gesprungen werden.

In diesem Beispiel könnte man das goto in Zeile 2 weglassen, da ja automatisch die nächste Zeile ausgeführt würde. Das würde aber den Compiler komplizierter machen, der das goto dort generiert, weil es manchmal (etwa beim and) gebraucht wird. Daher lassen wir das lieber.

Schleifen im Zwischencode

        variable1 = 0
        variable2 = 0
        while variable1 < 5 do
        begin
            variable1 = variable1 + 1
            variable2 = variable2 + variable1
        end
    

Die weniger Pascal-Versierten werden sich freuen zu erfahren, dass begin und end einfach gesagt nichts anderes sind als geschwiffene Klammern in vielen anderen Programmiersprachen.

Eine solche normale kopfgesteuerte Schleife könnte so im Zwischencode aussehen:

        variable1 = 0
        variable2 = 0
        if variable1 < 5 goto 5    
        goto ...
        variable1 = variable1 + 1
        variable2 = variable2 + variable1
        goto 3
    

Solange die Bedingung noch wahr ist, wird zur Laufzeit immer wieder in den Körper der Schleife gesprungen (von Zeile 3). Das goto danach (in Zeile 7) darf nicht vergessen werden, um nach einem Schleifendurchlauf wieder an den Beginn zu springen und die Bedingung erneut zu überprüfen. Ist die Bedindung nicht mehr wahr, wird an einen noch unbekannten Ort ans Ende gesprungen.

Ginge man die Erzeugung dieses Zwischencodes wieder Schritt für Schritt durch, würde man zwei Dinge bemerken, die für später relevant sind:

• Das goto in Zeile 3 muss wiederum zwischenzeitlich vermerkt werden und kann erst später mit der richtigen Zielsprungmarke befüllt werden.
• Für das goto in Zeile 7 muss man sich vorher vermerkt haben, wo der Zwischencode der Schleife beginnt.

Schleifen funktionieren im Zwischencode wie if-Blöcke. Die Expressions können daher ebenso verwendet werden. Zusätzlich muss am Ende des Schleifenkörpers ein Sprung zurück an den Anfang ausgeführt werden.