Von C zur PRG: Funktionsweise eines C-Compilers
Eines der wichtigsten Werkzeuge bei der Software-Entwicklung ist zweifelsohne der Compiler. Diese Artikelserie beleuchtet die Arbeitsweise einer Compiler-Sprache am Beispiel von C.
Selbst wenn Sie nicht in C, oder auch gar nicht programmieren, erfahren Sie viele interessante Details über Programmiersprachen im allgemeinen. Deshalb vorab eine Entschuldigung an die Profis: Lieber eine gute Lüge zur leichteren Vermittlung grundlegender Regeln unter Vernachlässigung der Ausnahmen, als die Verwirrung des weniger erfahrenen Lesers durch komplexe Wahrheiten.
Verschiedenste Programmiersprachen können nicht darüber hinwegtäuschen: Die einzige Sprache, die ein Computer wirklich versteht, ist die prozessorspezifische Maschinensprache: eine Folge von Nullen und Einsen, die der Normalsterbliche nur schwer mit der ursprünglichen Formulierung einer durch den Computer zu lösenden Aufgabe assoziieren kann.
Trotzdem wurde und wird in Assembler, einer etwas bequemeren Notation der Maschinensprache, programmiert. Die Vorteile sind nicht von der Hand zu weisen: Wenn ein Profi am Werk war, sind die resultierenden Programme kurz und schnell und stellen wohl meist das Optimum dessen dar, was aus einem Computer an Leistung herausgeholt werden kann.
Die Nachteile sollten jedoch nicht übersehen werden: Assembler-Programmierung ist zeitaufwendig und fehleranfällig; die Programme sind schwer zu warten und in hohem Maße systemabhängig, also nur schwer auf andere Computer zu übertragen - »portieren«, wie der Fachmann sagt.
Dessen bewußt, machte man sich frühzeitig an die Entwicklung sogenannter »höherer Programmiersprachen«, die den Programmierer von den Computerin-terna entlasten sollten. Er konnte sich bei der Programmierung vollständig auf die Problemlösung konzentrieren, anstatt sich mit dem Betriebssystem (oder gar der Hardware) herumschlagen zu müssen. Wenngleich in den Anfangszeiten solche höheren Programmiersprachen noch immer von Hand in den eigentlichen Maschinencode umgesetzt wurden, breiteten sich doch bald zwei Arten der Implementation dieser höheren Programmiersprachen aus: Interpreter und Compiler, die bezüglich ihrer Arbeitsweise und Anforderungen verschiedene Wege gehen.
Interpreter und Compiler
Ein Interpreter betrachtet den Quelltext - so nennt man üblicherweise die vom Programmierer geschriebene Hochsprachendarstellung eines Programms -Stück für Stück und entscheidet abhängig vom Quelltext über das weitere Vorgehen. Zur Vereinfachung und Beschleunigung der Programmausführung liegt der Quelltext meist in einer etwas modifizierten Form im Computer vor. Typische Interpretersprachen sind beispielsweise Basic oder Lisp. Die Anweisung
LET A = B * C + 1
könnte einen Basic-Interpreter zu folgenden Betrachtungen und Operationen veranlassen: »'LET': Aha! Hier soll etwas zugewiesen werden. Es sollte jetzt also eine Variable kommen ...ist auch tatsächlich der Fall. Na dann schauen wir doch mal nach, ob 'A' schon existiert.« Der Interpreter durchwühlt seine internen Tabellen und findet nichts. »Auch nicht tragisch, legen wir sie also neu an. Womit war ich noch beschäftigt? Ah ja, 'LET'! Nächstes Zeichen ist ein '=' genau wie ich es erwartet habe. Und jetzt wird es kompliziert, es muß ein Ausdruck ausgewertet werden.«
Die Auswertung findet ein elementares Symbol: die Variable 'B'. Der Wert von 'B' wird irgendwo vermerkt und anschließend der Multiplikationsoperator '*' erkannt. Jetzt wird wieder ein Teilausdruck erwartet, es findet sich ebenfalls ein elementares Symbol, die Variable 'C'.
»Auf geht'sz um Multiplizieren.« HALT! Wer sagt denn, daß nicht noch ein Potenzierungsoperator mit höherer Priorität folgt? »Na gut, also erst einmal weiterlesen:'+', eine Addition. Die hat eine niedrigere Priorität als die Multiplikation, also doch zunächst die beiden gemerkten Werte (von 'B' und von 'C') verknüpfen. Der nächste Teilausdruck besteht aus der Konstanten '1', und weil nichts mehr folgt, darf ich die Addition direkt ausführen. Und was mache ich nun mit dem Endergebnis? War da nicht die 'LET'-Anweisung? Richtig! Also den Wert in der Variablen TV speichern und weiter zum nächsten Befehl.«
Wenn Sie nun der Meinung sind, daß dies doch recht aufwendig sei, so haben Sie zweifelsohne recht, obwohl die obigen Erklärungen noch extrem vereinfacht waren und beispielsweise Datentypen gar nicht beachtet wurden! Man stelle sich all das in einer Schleife vor, die der Rechner unzählige Male wiederholt. Der Assembler-Programmierer denkt hier natürlich eher an eine so einfache Anweisungsfolge wie
MOVE B,temp ; hole B
MUL C,temp ; multipliziere mit C
ADD #1,temp ; addiere 1
MOVE temp,A ; speichere in A
Wäre es denn da nicht effizienter, untersuchte der Computer nur EINMAL die gesamte Anweisung VOR der Abarbeitung und führte dann immer die gleichen konstanten Anweisungen aus? Herzlichen Glückwunsch, genau das ist die Aufgabe eines Compilers: die Umwandlung des Quelltextes eines Programms einer höheren Programmiersprache in Objectcode.
»Objektcode«? Das ist ein weiterer Begriff, den sich Programmierer haben einfallen lassen, um den Einstieg in die Materie ein wenig zu erschweren. Es handelt sich um eine spezielle Darstellungsform des Maschinencodes, die es erlaubt, mehrere sogenannte »Objektdateien« (oder auch Objektmodule) zu einem fertigen, ausführbaren Programm zu kombinieren. Auch ist der Objektcode noch nicht auf eine bestimmte Speicheradresse (im Unterschied zum absoluten Maschinencode) festgelegt, kann also noch verschoben werden.
Interne und externe Durchläufe
Die Übersetzung eines Quelltextes in einen verschiebbaren Objektcode ist eine recht komplexe Angelegenheit, die sich in verschiedene Phasen aufteilen läßt. Für einen C-Compiler - und auf diese wichtige Compilersprache für den Atari wollen wir uns konzentrieren -könnten diese Phasen wie folgt aussehen:
1. Preprozessor
Das ist eine spezielle Fähigkeit von C und hat wenig mit dem eigentlichen Compiler zu tun. Hier wird der Quelltext Zeile für Zeile getrennt behandelt (sofern eine Zeile nicht mit einem Backslash endet oder sich ein Makro über mehrere Zeilen erstreckt) und es werden dabei gewisse Symbole definiert, die dann im laufenden Quelltext (meist durch Konstanten) ersetzt werden. Auch übernimmt der C-Preprozessor durch die »#include«-Anweisungden Import und Export von Symbolen.
»Makro«, »Import« und »Export« - das war vielleicht doch etwas zuviel auf einmal. Ein Makro ist eine spezielle Eigenschaft der Programmiersprache C. Ein Makro ist eine Funktion, die eine Gruppe von Anweisungen direkt an der Stelle des Aufrufs, möglicherweise nach der Ersetzung bestimmter Parameter, einsetzt oder ausführt. Das ist meist länger als der Aufruf einer Unterroutine, dafür jedoch schneller.
Bleiben noch Import und Export: Wie bei der Erklärung des Objektcodes bereits angedeutet, ist es in bestimmten Fällen sinnvoll, ein Programm in mehrere Module, also separat zu übersetzende Portionen, aufzuteilen. Auf irgendeine Weise müssen jedoch zwischen den Modulen Informationen ausgetauscht werden, sei es über Variablen, deren Typen oder über Funktionen. Damit der Compiler weiß, worum es sich bei bestimmten Symbolen handelt, werden diese ex-oder importiert. Das geschieht in C meist durch gemeinsame Fleader-Dateien über den Preprozessor.
2. Lexikalische Analyse
Zur Vereinfachung für den nächsten Schritt wird der Quelltext in sogenannte »Tokens« zerlegt. So können in C bestimmte Zeichenfolgen als zusammengehörig betrachtet werden, etwa Operatoren, die aus mehreren Zeichen bestehen:
++ != >= *= -> || <<
Ebenfalls werden in dieser Phase Kommentare entfernt sowie Wörter, Zahlen-, Zeichen- und Stringkonstanten erkannt. Reservierte Wörter stellen dann wiederum Sonderfälle der gültigen Bezeichner dar. Bezeichner (neudeutsch: Identifier) ist wieder so ein Wort, das dem Basic-Programmierer vielleicht noch nicht untergekommen ist: Es steht allgemein für alle Arten von Namen: für Variablen, Funktionen, Typen, Strukturen, Strukturelemente, Sprungmarken und einiges mehr. Ein Identifier setzt sich aus einer nicht unterbrochenen Folge von Buchstaben, Unterstrichen und Ziffern zusammen, darf jedoch nicht mit einer Ziffer beginnen.
So besteht die Zeile
printf ("%d\n", ++s->m); /* Kommentar*/
break;
aus 12 Tokens:
printf s_ident "printf"
( s_leftpa
"%d\n" s_string "%d\n"
, s_comma
++ s_inc
s s_ident "s"
-> s_pling
m s_ident "m"
) s_rightpa
; s_semicolon
break kw_break
; s_semicolon
Die Namen/Typen der Tokens sind hierbei völlig willkürlich gewählt und man erkennt, daß zu manchen Tokens noch weitere, spezifische Informationen geliefert werden müssen.
Das Token selbst gibt noch nicht unbedingt einen Hinweis auf seine Verwendung. So kommen Klammern in C schließlich in allen möglichen Zusammenhängen vor, und ein Doppelpunkt könnte als Abschluß einer Sprungmarke, bei Bitfeldern oder als Teil der bedingten Bewertung Vorkommen. Trotzdem können bestimmte Fehler schon hier erkannt werden, etwa nicht beendete Strings, Kommentare und Zeichenkonstanten. Auch völlig fremde Zeichen, etwa nichtdruckende Steuerzeichen, Dollar ($), Klammeraffe (@) oder ASCII-Zeichen ab dem Wert 160, die (außer in Kommentaren oder Strings/Zeichenkonstanten) gar nicht in einem C-Quelltext Vorkommen dürfen, resultieren in einer Fehlermeldung.
Eine einfache Form dieses »Zusammenziehens« gewisser Symbolgruppen wird - wie bereits erwähnt -üblicherweise auch von Basic-Interpretern (und nicht nur diesen) bei der Ablage von Quelltexten durchgeführt. Dies spart Platz und erleichtert ebenfalls die Interpretation.
3. Syntaktische Analyse (Parsing)
Hier wird kontrolliert, ob der Quelltext gewissen Strukturregeln der Programmiersprache genügt. Dieses Regelwerk, genauer: die Syntax einer Sprache, wird durch eine sogenannte »Grammatik« definiert. Diese wird oft in der Backus-Naur-Form (oder einer Anlehnung daran) festgelegt. Nicht alle strukturellen Eigenschaften aller Sprachen können auf diese Weise festgehalten werden. So weigern sich die »tagged section-brackets« von BCPL standhaft; das ist aber für eine typische Compilersprache auch das einzige Beispiel, das mir auf Anhieb einfällt. Auf die Anwendung solch grausamer Sprachenteile kann man aber ohnehin verzichten, daher auch keine weitere Erklärung hierzu.
Für C sind diese Regeln in Anhang A des Kernighan/Ritchie festgelegt, die Syntax von Modula-2 belegt in Niklaus Wirths »Programming in Modula-2« gerade zwei (Anhang 1), die von Ada immerhin schon sechs eng bedruckte Seiten.
Alle bisherigen Schritte - Sie glauben doch nicht etwa, daß es hiermit schon getan sei? - sind relativ einfach zu implementieren, zu einem großen Teil lassen sich hierbei sogar bestimmte Werkzeuge einsetzen. Ein Beispiel hierfür: aus einer Grammatik gleich den fertigen Quelltext für den Parser fertigen. Die richtige Arbeit fängt jedoch im nächsten Teil unseres Grundlagenkurses zu C-Compilern an. Frei nach dem Motto: »Was Sie schon immer über Compiler wissen wollten, aber bisher nicht zu fragen wagten.« (ah)
Ralph Babel