Zwischencode-Generierung

Teil 2: Compiler-Logik

Hier wird die eigentliche Aufgabe, die Definition der Logik des Compilers, erläutert. Ohne die Grundlagen aus Teil 1 wird man allerdings nichts verstehen.

Grundlegend für die Logik des Compilers ist die Grammatik der zu kompilierenden Sprache. Ein Auszug aus der Definition einer Expression, also der Bedingung oder dem »Wahrheitswert« etwa für ein if-Block, verdeutlicht das Konzept. Eine Expression wird durch das Nichtterminal E dargestellt: 

        E -> true
        E -> false
        E -> not E
        E -> E1 and E2
        E -> E1 or E2
        E -> id1 relop id2

Wahrheitswerte können mit true und false hartkodiert sowie negiert oder durch boolsche Operatoren rekursiv (d.h. beliebig verschachtelt) verknüpft werden. Alternativ können zwei Werte verglichen werden, hierzu wird der allgemeine Vergleichsoperator relop verwendet, den man später näher definieren könnte – z.B. durch < (kleiner), > (größer).

Jeder einzelnen Grammatikregel müssen nun noch sogenannte semantische Aktionen hinzugefügt werden, die definieren, wie sich der Compiler verhalten soll. Dafür setzen wir hier einen Pseudo-Code ein.

Erinnern wir uns an die Aktionen, die mit jedem Kompilierschritt ausgeführt werden können, und weisen ihnen entsprechende Konstrukte des Compiler-Codes zu:

Weitere Sprachkonstrukte sind für den Compiler-Code erforderlich:

Wer zunächst eine theoretische Erläuterung der Konstrukte vorzieht, kann sich diese aus der praktischen Erläuterung im Folgenden herausklauben.

Expressions

        E -> id1 relop id2 {
            E.TRUELIST := genlist(NEXTQUAD);
            genquad(if id1.POS relop id2.POS goto ...);
            E.TRUELIST := genlist(NEXTQUAD);
            genquad(goto ...)
        }

Wir definieren die semantischen Aktionen, d.h. den Compiler-Code etwa für einen kleiner-Operator wie aus Teil 1. Der Funktion genquad(...) wird direkt eine einzelne zu erzeugende Zeile Zwischencode – evtl. mit Platzhaltern – übergeben. Die Schreibweise id1.POS identifiziert den Speicher des jeweiligen Bezeichners, z.B. der entsprechenden Variable. Der Wert dieses Speichers soll dann ja später zur Laufzeit verglichen werden. Es entstehen also durch die Aufrufe in Zeile 3 und 5 genau zwei Zeilen Zwischencode analog zu Teil 1. 

        if var1 < var2 goto ...
        goto ...

Bleiben die Zeilen 2 und 4 des Compiler-Codes. NEXTQUAD ist ein Zeiger, der (zur Compilezeit) immer auf die nächste Zeile Zwischencode zeigt, d.h. die Stelle bzw. Zeilennummer, an der der nächste Aufruf von genquad Code anfügt. In Zeile 2 des Compiler-Codes zeigt NEXTQUAD also auf die danach erzeugte Zeile 1 des Zwischencodes if var1 < var2 goto .... Die Funktion genlist erzeugt (zur Compilezeit und nur für die Verwendung im Compiler) eine Liste aus einem einzelnen Element. Die Position der Zwischencode-Zeile wird also in einer Liste gespeichert, genauer in der TRUELIST, um den Platzhalter in dieser Zeile später noch ausfüllen zu können. In der TRUELIST werden immer die Zeilen vermerkt, in denen noch Platzhalter (zur Compilezeit) auszufüllen sind, die (zur Laufzeit) zum Gutfall springen sollen. Das goto in Zeile 1 wird ausgeführt, wenn die Bedingung zutrifft, daher handelt es sich um den Gutfall und der entsprechende Platzhalter für das Sprungziel wird in der TRUELIST vermerkt.

Einem Nichtterminal können Attribute zugewiesen werden mit der aus der Objektorientierung bekannten Schreibweise Nichtterminal.Attribut. So kann auch auf Attribute anderer, untergeordneter Nichtterminale zugegriffen werden.

Das NEXTQUAD in Zeile 4 des Compiler-Codes zeigt entsprechend auf die zweite Zeile Zwischencode, und diese Stelle soll in der FALSELIST vermerkt werden, damit auch dieser Platzhalter später noch ausgefüllt werden kann. In der FALSELIST werden entsprechend immer die Zeilen vermerkt, in denen noch Platzhalter für den Sprung zum Schlechtfall vorhanden sind. Merken wir uns also, dass in der TRUELIST in diesem Fall die Zwischencode-Zeile 1 vermerkt ist und in der FALSELIST die Zeile 2.

Mit Definition folgender Regel: 

        E -> E1 and M E2 {
            backpatch(E1.TRUELIST, M.QUAD);
            E.TRUELIST := E2.TRUELIST;            
            E.FALSELIST := merge(E1.FALSELIST, E2.FALSELIST);
        }
        M -> ε {
            M.QUAD := NEXTQUAD
        }

... kann dann auch der Zwischencode für ein boolesches and erzeugt werden: 

        if var1 < var2 goto 3
        goto ...
        if var3 < var4 goto ...
        goto ...

Genauer wurde der oben stehende Zwischencode fast komplett bereits durch die zuvor erläuterte Compiler-Logik zur Regel E -> id1 relop id2 erstellt. Diese wurde zweimal durchlaufen, nämlich einmal für jede der beiden Expressions mit größer/kleiner-Vergleichen. Im Anschluss wird die übergeordnete and-Regel ausgeführt, die lediglich noch das Sprungziel 3 in Zeile 1 hinzufügt, ganz so, wie wir es bereits manuell in Teil 1 gemacht haben. Für das Setzen dieses Sprungziels ist die backpatch-Funktion in Zeile 2 des Compiler-Codes zuständig. Die backpatch-Funktion erwartet eine Liste von Zeilen, die noch Platzhalter enthalten, als erstes Argument, sowie das Sprungziel, d.h. die Zeile, zu der gesprungen werden soll, als zweites Argument. Die backpatch-Funktion befüllt dann (zur Compilezeit) alle Platzhalter in den angegebenen Zeilen mit dem angegebenen Sprungziel. Im vorliegenden Fall schreibt sie zur Compilezeit das Sprungziel, das in M.QUAD hinterlegt ist, in alle Zeilen, die in der Liste E1.TRUELIST hinterlegt sind. Aber was ist M.QUAD?

M ist eine sogenannte Markierungsvariable. Wir müssen uns merken, wo der Zwischencode der zweiten Expression beginnt, um dann Sprungziele dorthin ausfüllen zu können. Die Markierungsvariable ist eine zusätzliche Grammatikregel, die nach ε, also nichts, auflöst. Der Scanner erwartet also keine zusätzlichen Eingabesymbole. Wir können dann aber in Zeile 7 zusätzliche Compiler-Logik (Semantische Aktionen) definieren, nämlich, dass wir den Zeiger auf die nächste zu erstellende Zwischencode-Zeile NEXTQUAD in einer Hilfsvariable QUAD zwischenspeichern.

Eine Expression kann nicht selbst wissen, wo ihr Zwischencode beginnt, da sie beliebig verschachtelt sein kann. Bei der hier gezeigten and-Expression zum Beispiel sind alle erforderlichen Zeilen Zwischencode ja bereits erzeugt. Wo er angefangen hat, ist gar nicht mehr bekannt. Daher benötigen wir eine Markierungsvariable vor manchen Expressions.

Auf diese Hilfsvariable des Nichtterminals M können wir dann aus der übergeordneten Regel mit M.QUAD zugreifen, genauso, wie wir auf die Listen der untergeordneten Expressions durch E1.TRUELIST, E2.TRUELIST etc. zugreifen können. Die E1.TRUELIST z.B. enthält ja die Zeilennummern des bereits erzeugten Zwischencodes der ersten Expression, in denen ein goto, das zum Gutfall springen soll, noch ausgefüllt werden muss. Konkret ist in den Variablen bzw. Listen von E1, E2 und M im obigen Beispiel also Folgendes hinterlegt: 

        E1.TRUELIST: [1]
        E1.FALSELIST: [2]
        E2.TRUELIST: [3]
        E2.FALSELIST: [4]
        M.QUAD: 3

Daher schreibt der Aufruf backpatch(E1.TRUELIST, M.QUAD) zur Compilezeit den Wert 3 in das goto der ersten Zwischencodezeile, damit eben zur Laufzeit im Gutfall noch die zweite Expression für das and überprüft werden kann.

Eine Liste der untergeordneten Expressions ist also »verarztet«. Es bleiben noch drei Listen übrig, die auf jeden Fall nicht vergessen werden dürfen, weil sonst seltsam leere Stellen im Zwischencode bleiben, die der Prozessor später unmöglich ausführen kann. Aber es bleiben auch noch zwei Anweisungen der Compiler-Logik oben übrig: 

        E.TRUELIST := E2.TRUELIST;            
        E.FALSELIST := merge(E1.FALSELIST, E2.FALSELIST);

Nur wenn auch die zweite Expression wahr ist, soll zur Laufzeit zum Gutfall der gesamten and-Expression gesprungen werden (z.B. zum Körper des if-Blocks). Daher wird nur die E2.TRUELIST genauso als E.TRUELIST übernommen, also als TRUELIST der and-Expression. Dagegen soll, egal ob der Schlechtfall der ersten oder der zweiten Expression eintritt, zum Schlechtfall der übergeordneten and-Expression gesprungen werden. Mit der Funktion merge werden diese Listen daher (zur Compilezeit) vereinigt. Dies bedeutet, dass alle Zwischencode-Zeilen, die als Schlechtfall einer der beiden Expressions vermerkt sind, im weiteren Verlauf des Kompilierens mit demselben Sprungziel, z.B. der Position des else-Blocks, ausgefüllt werden. Dies geschieht allerdings nicht mehr in der Logik der and-Expression, da die Position des Sprungziels hier noch nicht bekannt ist. Die Listen der noch auszufüllenden Zwischencode-Zeilen werden daher an die wiederum übergeordnete Regel weitergegeben. In den Listen der and-Expression sind also folgende Zwischencode-Zeilen hinterlegt: 

        E.TRUELIST: [3]
        E.FALSELIST: [2, 4]

In TRUELIST und FALSELIST werden für Expressions Stellen vermerkt, die zu einem späteren Zeitpunkt der Compilezeit noch mit einem Sprungziel ausgefüllt werden müssen. Es müssen schlussendlich immer alle Listen behandelt werden, sonst bleiben Lücken im Zwischencode.

Bedingungsblöcke

Um nun endlich einen ganzen if-Block verstehen zu können, wie müssen wir unsere Compiler-Logik noch ergänzen?

Es folgt der hierfür erforderliche Compiler-Code. Das Nichtterminal S repräsentiert eine Liste von Statements, also sonstigen Befehlen, hier innerhalb des Körpers des if-Blocks. Was bei den Expressions die TRUELIST und FALSELIST ist, ist bei Statements die NEXTLIST. Sie merkt sich Zwischencode-Zeilen, die an das Ende eines Blocks springen wollen. Hier werden daher die in der FALSELIST der Expression vermerkten Stellen sowie die in der S1.NEXTLIST vermerkten Stellen innerhalb des Körpers des if-Blocks, die ans Ende des if-Blocks springen wollen, der übergeordneten Regel zur Bearbeitung überlassen. 

        S -> if E then M S1 {
            backpatch(E.TRUELIST, M.QUAD);
            S.NEXTLIST := merge(E.FALSELIST, S1.NEXTLIST);
        }

Die S1.NEXTLIST wird etwa relevant, wenn der if-Block verschachtelte if-Blöcke enthält, oder bei einer Schleife, die ein continue enthält.

Wenn ein else-Block hinzukommen soll, wird die Sache noch etwas haariger: 

        S -> if E then M1 S1 N else M2 S2 {
            backpatch(E.TRUELIST, M1.QUAD);
            backpatch(E.FALSELIST, M2.QUAD);
            S.NEXTLIST := merge(S1.NEXTLIST, N.NEXTLIST, S2.NEXTLIST);
        }
        M1, M2 -> ε {
            M.QUAD := NEXTQUAD
        }
        N -> ε {
            N.NEXTLIST := genlist(NEXTQUAD);
            genquad(goto ...)
        }

Die in der E.FALSELIST angegebenen Stellen sollen stattdessen nun direkt zum else-Block springen. Hierfür brauchen wir eine zusätzliche Markierungsvariable M2. Außerdem muss daran gedacht werden, am Ende des Blocks für den Gutfall den else-Block zu überspringen, sonst würden ja beide Blöcke ausgeführt werden. Hierfür führen wir ein weiteres Nichtterminal N ein, das ein neues goto am Ende des Gutfall-Blocks erzeugt und sich die Position desselben in seiner NEXTLIST merkt. Gemeinsam mit den NEXTLIST der zwei Blöcke kann dies dann später mit dem Sprungziel ausgefüllt werden, wenn bekannt ist, an welcher Position der Zwischencode hinter dem gesamten if-Block steht, zu dem gesprungen werden soll.

Die Nichtterminale N und M2 könnte man, wenn man es richtig macht, auch vereinen.

Die Zeilen des Zwischencodes werden normalerweise der Reihe nach ausgeführt. Wenn Abschnitte übersprungen werden sollen, etwa bei else-Blöcken oder Schleifendurchläufen, muss goto eingesetzt werden. Zum Einfügen der goto-Statements können zusätzliche Markierungsvariablen notwendig sein.

Schleifen

        S -> while M1 E do M2 S1 {
            backpatch(E.TRUELIST, M2.QUAD);
            backpatch(S1.NEXTLIST, M1.QUAD);
            genquad(goto M1.QUAD)
            S.NEXTLIST := E.FALSELIST;            
        }

Zum Abschluss eine Schleife: Hier werden ebenfalls zwei Markierungsvariablen benötigt. Zum einen vor den Expressions, zu denen zur Laufzeit bei jedem Schleifendurchlauf wieder gesprungen werden muss, um sie zu überprüfen; zum anderen vor den Statements, zu denen im Gutfall gesprungen werden soll. Mit backpatch behandelt werden also die TRUELIST der Expressions sowie die NEXTLIST der Statements. Denn die in der NEXTLIST vermerkten Stellen irgendwo im Schleifenkörper sollen auch wieder an den Schleifenkopf springen.

Noch wichtiger ist aber, am Schleifenende ein zusätzliches goto zu generieren, das ebenso wieder an den Schleifenkopf springt. Da zu diesem Zeitpunkt durch den Bottom-up-Parser ja bereits alle Expressions und Statements verarbeitet sind, kann dies einfach in der Compiler-Logik der Schleife selbst erfolgen. Schlussendlich folgt noch die übliche Prokrastination: Um das Sprungziel für die FALSELIST muss sich später noch gekümmert werden.

In Anlehnung an die durchzuführenden Aktionen kann man sich also folgende Fragen stellen: