C programmieren: Wie arbeitet ein C-Compiler?

Wie entsteht aus geschriebenem C-Code ein Programm, dass das Zielsystem auch versteht und Umsetzen kann? In diesem Beitrag sehen wir uns Aufbau und Arbeitsweise des C-Compilers genauer an.

Unser vorheriger Grundlagenartikeln zum Programmiere mit C befasste sich speziell mit der Standardbibliothek und dem Präprozessor der Programmiersprache. Speziell letzterer ist eines der Elemente, mit dem geschriebener C-Code auch in eine Form umgewandelt wird, die der Rechner umsetzen kann, die sog. Maschinensprache. Dieser Vorgang nennt sich auch Compiling.

Die vier Compilerphasen beim Programmieren mit C

Die Übersetzung eines in C geschriebenen Programms erfolgt in insgesamt vier Phasen, von denen der Compiler an zweien unmittelbar beteiligt ist. Die vier Phasen sind:

Bildergalerie

Bildergalerie mit 12 Bildern

• Präprozessorphase

• Frontendphase des Compilers

• Backendphase des Compilers

• Linkerphase

Die Präprozessorphase wurde bereits erwähnt. Hierbei handelt es sich um eine Vorbereitung des zu übersetzenden Sourcecodes. Textmakros werden ersetzt, die so genannten include-Dateien eingesetzt, Kommentare gelöscht, die Zeilen immer durch ein Newline-Zeichen getrennt usw. Der Output dieser Phase ist ein reiner Sourcecode, der bislang noch keine Überprüfung oder Übersetzung erfahren hat.

Im Frontend des Compilers (siehe Bild 1) wird dieser Sourcecode eingelesen (Scanner) und überprüft (Parser). Ziel ist es dabei, die korrekte Syntax zu überprüfen, eine erste Syntaxumwandlung und erste Optimierungen durchzuführen. Das Ziel dieser Phase ist ein Zwischencode, der noch von dem Zielsystem (dem Mikroprozessor) unabhängig ist, aber dennoch die Umsetzung in Assembler- oder Maschinensprache vorbereitet. Der Output dieses Frontendteils wird im nächsten Abschnitt genauer betrachtet.

Im Backend des Compilers erfolgt das Einlesen des Zwischencodes (intermediate representation, IR), die Umsetzung in Assemblersprache einschließlich der maschinenspezifischen Optimierung und der Assemblerlauf. Ziel dieses Abschnitts ist der so genannte Objektcode, der neben dem Maschinencode – noch unvollständig – auch Informationen zu den Daten und Programmabschnitten mitführt.

Der Linker liest dann abschließend den Objektcode ein, dazu die angegebenen Standard- und spezifischen Bibliotheken, und fügt das zusammen. Nunmehr sind alle Adressen, auch die der aus der Bibliothek genutzten Funktionen (wie etwa printf) bekannt, und der Maschinencode kann mit allen Adressen vervollständigt werden. Output des Linkers ist ein ausführbarer Maschinencode (in einem File-format).

Die Erzeugung des Zwischencodes

Für den Zwischencode existiert kein genormtes Format, jeder Compiler nutzt dort seine hauseigene Syntax. Besonders interessant ist jedoch das Lance2-Compiler-System, das aus C ein low-level-C erzeugt und dieses als Zwischencode nutzt. Diese Untermenge von C, die dieses Compilersystem als Zwischencode (Intermediate Representation, IR) nutzt, ist natürlich beschränkt. Wesentliche Merkmale sind:

Anweisungen (Statements):

• Zuweisungen (Assignments): a = b + c, y = function( a, b ), ...

• Sprünge (Jumps): goto label_1; (diese Sprünge sind Compiler-berechnet und somit ”zugelassen“)

• Bedingte Sprünge (Conditional Jumps): if( cond ) goto label_2;

• Marken (Label): label_1:

• Rücksprung ohne Rückgabewert (return void): return;

• Rücksprung mit Rückgabewert (return value): return x;

Ausdrücke (Expressions):

• Symbole: main, a, count …

• Binäre Ausdrücke (binary expressions): a * b, x / y …

• Unäre Ausdrücke (unary expressions): ~a, *p …

• Type Casts: (int), (char)

• Konstanten (in verschiedenen Formaten): -5, 3.141592653589

Ein kurzer Blick in die obige Liste verrät, dass bei den Anweisungen Schleifen wie for, while und do .. while komplett fehlen. Diese Schleifen werden durch die aufgezählten Konstrukte abgebildet bzw. in diese übersetzt, und es gilt noch zu zeigen, wie dies erfolgt.

Der wichtigste Zusatz, das Zwischencodeformat betreffend, besteht noch in der Beschränkung der Ausdrücke und der Zuweisungen: Sie werden auf ein 3-Adressformat eingeschränkt, d.h., eine Wertzuweisung an ein links stehendes Symbol (a = ...) wird rechtsseitig durch einen unären oder einen binären Ausdruck bestimmt. Längere „Kettenrechnungen“ müssen dementsprechend in Teilrechnungen mit Einfügung temporärer Variablen geteilt werden, eine Aufgabe, die dem Compiler zufällt. Der Grund für diese Einschränkung ist sehr offen-sichtlich: Dem 3-Adressformat entsprechen häufig direkt Assemblerbefehle (etwa: ADD R3, R1, R2, was R3 = R1 + R2 bedeutet).

Bild 2 zeigt die Übersetzung einer if/else if/else-Verzweigung. Dabei wird deutlich, dass nur if-Konstrukte mit anschließendem Sprung (also zusammengefasst der ”bedingte Sprung“) genutzt werden. Die Bedingungen selbst müssen dabei invertiert ausgewertet werden, da ja die Liste der Anweisungen, die bei Erfüllung der ursprünglichen Bedingung auszuführen sind, nun übersprungen werden.

Dies mag etwas holprig wirken, denn bei Zulassung einer üblichen if-Verzweigung wäre dies wesentlich einfacher zu übersetzen. Diese Form der Übersetzung hat jedoch den entscheidenden Vorteil, dass nur bedingte Sprünge verwendet werden, und die lassen sich 1:1 in eine Sequenz von Assemblerbefehlen übersetzen, wie etwa:

Bild 3 zeigt die Übersetzung der while-Schleife, Bild 4 die der etwas komplexeren for-Schleife. In beiden Fällen werden bedingte und unbedingte Sprünge verwendet, um die Schleifenstruktur entsprechend abzubilden, wobei die Bedingung auch wieder invertiert verwendet werden müssen, um den Sprung aus der Schleife zu beschreiben. Entsprechend den hier gezeigten Codeabschnitten können nun auch die switch/case-Verzweigung (Bild 5) und die do..while-Schleife (Bild 6) übersetzt werden, wobei die Mehrfach-Fallunterscheidung (switch/case) etwas komplexer ist.

(ID:45439187)