Copyright by Xin Software Design 2014 
Die bekannten Lehrbücher ( [4], S.685, [5, S.12], [13, S.6]) unterteilen den Prozess vom Lesen des Quelltextes bis zum Endprodukt in 4 Phasen.
Die Codegenerierung wird häufig noch weiter aufgeteilt in 3 einzelne Phasen, so dass sich folgendes Bild ergibt:
Die Analyse-Schritte 1-3 werden als Front-End des Compilers bezeichnet, als Back-End gelten die Schritte 4, bzw. 4-6. Im Verlauf des Kapitels, gehe ich vom 6 Phasen-Modell aus.
Das erste Problem bei der Kompilierung eines Quelltextes ist Schlüsselwörter, Delimiter und unbekannte Wörter (Typnamen oder Variablennamen) zu erkennen und nachfolgenden Phasen in einer verständlichen und genormten Form zu liefern.
Eine lexikalische Analyse wird bei textbasierten Eingaben erforderlich. Das Unterprogramm, das diese Aufgabe vornimmt, wird als „Scanner“ bezeichnet. Es durchsucht den Quelltext nach bekannten Schlüsselwörtern wie beispielsweise „if“ oder „while“ und überspringt dabei für den Compiler überflüssige Zeichen (zum Beispiel Line-Feed, Leerzeichen oder Kommentare).
Im Informatik-Duden [13, S.364] wird die lexikalische Analyse als „Bindeglied zwischen Quellprogramm und syntaktischer Analyse“ bezeichnet, dass „das Quellprogramm in eine Folge von Terminalzeichen, die so genannten Tokens, übersetzt“. Ein Token kann als konstanter Wert mit festgelegter Bitbreite leichter verarbeitet werden, als ein String mit einer unbekannten Länge. So existieren für alle Schlüsselwörter und Standard-Operatoren eigene Token.
Die lexikalische Analyse ist in der Lage „solche Fehler erkennen, bei denen die in der Eingabe befindlichen Zeichen kein Symbol der Sprache bilden.“, so das Drachenbuch[5, S.14]. Das bedeutet, dass die Syntaxanalyse unbekannte Zeichen wie das Bell-Zeichen (ASCII-Zeichen 7) oder Backspace-Zeichen (ASCII-Zeichen 8) innerhalb des Quelltextes als Fehler erkennen.
Der Ausdruck x=35a4; stellt in einer Sprache mit C-ähnlicher Syntax keine gültige Anweisung dar und enthält ausschließlich Symbole, die in C-ähnlichen Sprachen gültig sind. „Fehler, bei denen der Symbolstrom Strukturegeln (Syntax) der Sprache verletzt, werden von der Syntaxanalyse-Phase entdeckt.“, so das Drachenbuch [5] weiter.
Ob dieser Fehler nun in der lexikalischen oder in der nachfolgend erklärten, syntaktischen Analyse auffällt, ist davon abhängig, ob die lexikalische Analyse das ‚a’ am Ende der Zahl 35 als Trennsymbol verarbeitet und damit 35a4 als in zwei Tokens „Zahl 35“ und „Identifier a4“ bewertet, oder versucht es als vollständiges Symbol „35a4“ zu parsen. Dies kann je nach Implementierung variieren.
Der GNU-C Compiler scheint den zweiten Weg zu gehen. Das folgende Programm
C++-Quelltext
int main(void) { long x = 35a4; return x; }
erzeugt beim Kompilieren folgende Fehlermeldung:
test.c:3: nondigits in number and not hexadecimal
Dies kann als Hinweis interpretiert werden, dass der GNU-C Compiler diese Kontrolle in der lexikalischen Analyse vornimmt. Doch „nur wenige Fehler sind lokal auf der lexikalischen Ebene eindeutig identifizierbar“ [5, S.104], da es nicht die Aufgabe der lexikalischen Analyse ist, zu entscheiden, ob die Tokens als sinnvoll oder sinnlos zu gelten haben, sondern lediglich den Quelltext in Tokens für die im folgenden erklärte, syntaktische Analyse zu übersetzen.
Der Genesys Compiler würde in der semantischen Analyse feststellen, das er den Wert 35 zuzuweisen hat, wenn der Datentyp die Einheit ‚a4’ verlangt. Verlangt der Datentyp keine oder eine andere Einheit oder wurde die Einheit ‚a4’ nie deklariert, so läge ein semantischer Fehler vor.
Das Ergebnis einer lexikalischen Analyse ist eine Auflistung aller für die Sprache relevanten Schlüsselwörter in einer leicht zu verarbeitenden Datenstruktur, und die Entfernung aller für die Kompilierung nicht erforderlichen Zeichen (u.a. Zeilenumbrüche und Kommentare).
Die Schwierigkeit lexikalische Fehler zu erkennen lässt sich an folgendem Beispiel aufzeigen. Die Eingabe „fi“ kann ein lexikalischer Fehler sein, wenn das Schlüsselwort „if“ gemeint ist. Es kann allerdings ebenfalls die gültige Bezeichnung einer Variablen darstellen. Somit wären lexikalische Fehler in der lexikalischen Analyse nur auffindbar, wenn der Programmierer seine Absicht ein Schlüsselwort zu verwenden zuvor ausdrücklich ankündigen würde.
Da ein Computerprogramm frei von Interpretationen sein muss, verlangen Computersprachen die Beschreibung von Algorithmen in eindeutigen Formulierungen. Diese strenge Regelung der Formulierung wird als Syntax, bzw. Grammatik einer Sprache bezeichnet und sorgt dafür, dass jede Anweisung genau eine eindeutige Semantik besitzt.
Der Programmteil, der die eingehenden Befehle interpretiert und auf eine gültige Kombination prüft, wird als „Parser“ bezeichnet. Der Parser fragt dafür Token für Token aus der lexikalischen Analyse ab und gleicht dies mit den Fällen ab, die die dem Parser einprogrammierte Grammatik für gültig erklärt. Sollte die Grammatik keinen Fall besitzen, der den zu interpretierenden Tokens entspricht, so liegt ein Fehler im Quelltext vor, der dem Benutzer zur Korrektur gemeldet werden sollte.
Um die syntaktische Kontrolle über das Programm durchführen zu können, müssen Symboltabellen aufgebaut werden (zum Beispiel die bekannten Namen) und Hinweise über bereits benutzte, allerdings noch nicht korrekt deklarierte Variablen verwaltet werden. Hier sei als Beispiel ein Methodenaufruf innerhalb einer Klasse genannt, der jedoch erst später deklariert wird.
Um diesen Verwaltungsaufwand zu strukturieren werden nun alle Operationen in einen so genannten Parserbaum eingehängt, der ein syntaktisch fehlerfreies Abbild des Quellcodes darstellt. Der Parserbaum ist hier nicht mit der 4. Phase (Zwischencode) zu verwechseln. Beim Parserbaum handelt es sich nicht um eine flache Darstellung als serialisierten Code, sondern um eine Darstellung aller Programmzweige in einem Baum.
Syntaktische Analyse und lexikalische Analyse arbeiten normalerweise nicht getrennt voneinander, sondern gleichzeitig. Es lohnt sich nicht, zuerst die lexikalische Analyse vollständig durchlaufen zu lassen, da ein vorzeitiger Abbruch der Kompilierung Teile der lexikalischen Analyse überflüssig machen würde. Aus diesem Grund durchläuft der Scanner den Quelltext oftmals nicht als eigenständiges Programm, sondern als Unterprogramm des Parsers. Dabei fordert der Parser ein Token vom Scanner an, welches der Scanner aus dem Quelltext heraussucht und anschließend seine Arbeit wieder unterbricht, bis das darauf folgende Token angefragt wird.
Syntaktische Fehler sind problemlos zu erkennen, die Reaktionen auf syntaktische Fehler werden normalerweise nicht von der Sprachdefinition abgedeckt, sondern vom jeweiligen Implementierer willkürlich beschlossen. Eine möglichst verständliche Fehlermeldung sollte realisiert werden.
Die Hauptaufgabe, die die semantische Prüfung zu leisten hat, ist zu garantieren, dass alle Ausdrücke typkompatibel verarbeitet werden können. Das Drachenbuch[5, S. 6 und 9] trägt dem Rechenschaft, in dem die semantische Analyse ihre Erwähnung lediglich in der Einleitung findet und von dort auf das Kapitel „Typüberprüfung“ verwiesen wird.
Die Semantik beschreibt die Bedeutung eines Ausdrucks, also wie Instruktionen interpretiert werden. Als Beispiel lässt sich der Ausdruck 'A' nehmen, dessen Semantik in der Sprache C gleichbedeutend mit der Zahl 65 ist, da 65 der ASCII-Wert für ein großes A darstellt. Jedes ASCII-Zeichen kann in 8 Bit dargestellt werden, entsprechend ist dieser Ausdruck 8 Bit breit. Diese Semantik wurde in C++ geändert, da C++ ohne explizite Datentypangabe grundsätzlich vom Datentyp int ausgeht. Dies gilt auch hier. Damit steht der Ausdruck 'A' in C++ für eine 32 Bit große Zahl. Berechnungen, die mit dem Ausdruck sizeof( 'A' ) gerechnet werden, werden in C bzw. C++ unterschiedliche Ergebnisse erzielen, da sich die Bedeutung in C++ geringfügig geändert wurde.
Da auch hier kein Freiraum zu Interpretation bleibt und sich die Übersetzung bereits in einem syntaktisch korrekten Parserbaum befindet, sind Ausdrucksfehler wie if = 7 bereits ausgeschlossen.
Hierbei werden Fehler erkannt, die in der Syntax-Prüfung nicht erkannt werden können. Folgender Quelltext
C, C++, Java, C#-Quelltext:
s = "Hallo Welt";
stellt einen syntaktisch gültigen Ausdruck dar, die semantische Analyse kann hier einen Typenfehler finden, wenn die Variable s zum Beispiel als Integer deklariert wurde oder als konstanten String, auf den eine Zuweisung nicht möglich ist.
Beim Aufbau des Parserbaums werden weiterhin einige Prüfungen durchgeführt, die beispielsweise nicht deklarierte bzw. mehrfach deklarierte Variablen oder die unsachgemäße Verwendung von Schlüsselwörtern bemängelt:
Fehlerhafter C-Quelltext
if( true ) break;
Die break-Anweisung darf innerhalb einer Verzweigung nicht verwendet werden. Dies fällt auf, wenn eine break-Anweisung als Kind eines Knotens in den Parserbaum eingehängt werden soll, der keine Schleifen- oder Switch-Anweisung abbildet.
Der Informatikduden[13, S.593] schreibt der semantischen Analyse eine zusätzliche Funktion zu: Die Zuordnung von Zieladressen für alle Variablen und jedem Ausdruck und Zwischenergebnissen, wobei bei Zwischenergebnissen vorrangig Prozessor-Register gewählt werden. Ebenfalls erhalten Anweisungen Adressen innerhalb des Zielprogramms, beispielsweise bei einer if-Anweisung für den Sprung hinter den then-Part, falls die Bedingung nicht erfüllt wird.
Dem kann ich nicht folgen, bei der Implementierung des GeCCo-Compilers, ließ sich in der semantischen Analyse nicht feststellen, wie viele Bytes der zu überspringende then-Part einer if-Abfrage in Maschinensprache belegen wird. Diese Information steht erst zur Verfügung, nach dem der Codegenerator den then-Part vollständig übersetzt hat.
Die Festlegung, wo sich Variablen relativ zum Stack befinden, kann je nach Implementierung bereits in der semantischen Analyse geschehen. Dieser Part wird im GeCCo Compiler in der Codegenerierung durchgeführt, da Festlegungen, die in Maschinensprache formuliert werden, in meinen Augen auch in der Compilerphase erledigt werden sollten, die die Maschinensprache formuliert. Ein zweiter, wichtigerer Grund ist, dass die semantische Analyse die Registerbreite des Prozessors nicht kennen kann und bei einer sauberen Trennung der Phasen auch nicht kennen muss. Geht die semantische Analyse bei einer 32 Bit-Variable von 32 Bit Platzverbrauch auf dem Stack aus, wird die nächste Variable um 32 Bit auf dem Stack verschoben platziert.
Würde man dieses Programm nun auf einem Computer mit anderen Registerbreiten (z.B. auf einer Cray Cyber 7600), so wäre eine Verschiebung von 32 Bit falsch, da der 60-Bit Prozessor auch 60 Bit benötigt, um die Variable in den Speicher zu kopieren. Diese Information wäre dem Code-Generator für diesen Prozessortyp bekannt, so dass er bei einer 32-Bit-Variable, den nächst größeren Typ wählen kann und hier die Variable auf 60 Bit Breite auslegen kann.
Nachdem der Parserbaum vollständig und fehlerfrei eingelesen wurde, kann der Parserbaum nach Möglichkeiten durchsucht werden, um überflüssige Handlungen zu entfernen oder Anweisungen zu vereinfachen. Ein Beispiel für eine einfache Optimierung wäre die Zuweisung a = 4 + 6; durch die weniger aufwendige, aber gleichwertige Zuweisung a = 10; zu ersetzen.
Ebenfalls optional ist es möglich aus dem Parserbaum einen flachen, serialisierten Zwischencode zu erzeugen. Beim Genesys Compiler übernimmt diese Aufgabe der 'Virtual Computer Code'[8], der allerdings im Unterschied zu anderen Compilern so angebracht ist, dass er auch ohne Codeerzeugung gespeichert und durch den im Compiler eingebetteten Interpreter sofort interpretiert werden kann. Dieser Zwischencode ist sehr maschinennah, so dass Codegeneratoren für beliebige Zielplattformen schnell zu entwickeln sind und eignet sich ebenfalls für eine zusätzliche Optimierung. Mit der Verwendung von Zwischencodes wird gewissermaßen ein Low-Level-Compiler hinter einen Hochsprachen-Compiler in Reihe gesetzt, der den Zwischencode in ausführbaren Code konvertiert (häufig auch 1:1 assembliert).
Aus dem Compilerbaum, bzw. bei Sprachen mit Zwischencodeerzeugung aus dem Zwischencode, muss am Schluss ein dem Quelltext entsprechendes Programm für die Zielplattform erstellt werden. Diese Übersetzung wird durch den Codegenerator geleistet, wobei das Ziel - je nach Compiler - eine ausführbare Datei oder auch eine Objektdatei sein kann. Objektdateien enthalten bereits Maschinencode, können allerdings nicht direkt ausgeführt werden. Der Linux-Kernel benutzt sie zur dynamischen Erweiterung, sie werden dabei ähnlich den DLLs (Dynamik Link Library) bei Windows zur Laufzeit an den Kernel gebunden.
Mit Hilfe eines Linkers können auch weitere Objektdateien und Bibliotheken zu einer ausführbaren Datei gelinkt werden.
Der Linker ist nicht Teil des Compilers. Ein Compiler, der einen Linker benötigt, ruft ihn jedoch häufig bereits aus den Standardeinstellungen auf, um den Aufwand für den Programmierer zu verringern.