[X] Compiler

[Ben04]

auf neue seite komm

[Ben04]

Auf neue Seite komm um nicht eine elendig lange html Seite zu haben.

[Ben04]

...

[Ben04]

...

[Ben04]

Ich hab mich endlich dazu durchringen können eine Einleitung zu schreiben und auch sonst noch Kleinigkeiten auszubessern. Wenn keiner mehr etwas zu kommentieren hat dann mach ich, das Inhaltsverzeichnis und es kann in die Rechtschreibkorrektur gehen.

Kann sich einer bitte diese Version durchlesen und vor allem ausprobieren, ob er den Code ans laufen kriegt. Nicht, dass die Leser später an irgend etwas blödem verzweifeln.

======

Inhaltsverzeichnis

• 1 Einleitung
• 2 Backtracking
• 3 Einfachstes Program
• 4 Immer noch einfach
• 5 Schon etwas komplizierter
• 6 Taschenrechner
• 7 Klammern
• 8 Variablen
• 9 Hello World!
• 10 If und Schleifen
• 11 Funktionen
• 12 Parser Baum
• 13 Schlussbemerkung

1 Einleitung

Programmiersprachen sind eines der zentralsten Themen mit denen sich Programmierer auseinandersetzen müssen. Trotzdem werden sie von vielen als magische Kiste, entwickelt von Spezialisten angesehen. In der Tat ist es ganz und gar nicht einfach einen guten Compiler zu entwickeln vor allem sobald Optimierungen ins Spiel kommen. Die Grundlagen sind jedoch gar nicht so schwer. Dieser Artikel soll eine recht praxisnahe Einführung in das Thema Compilerbau darstellen und richtet sich an jeden der C++ kann und Grundkenntnisse in x86 Assemblerprogrammierung hat. Auf theoretische Konstrukte wie Grammatiken wird vereinzelt hingewiesen jedoch braucht man sie nicht zu kennen um folgen zu können.

Es muss irgendein GCC installiert sein um die Beispiele ausführen zu können. Ich werde nämlich dessen Assembler und Linker einsetzen.

2 Backtracking

Bei einem Compiler handelt es sich um ein Programm das eine Textdatei einließt und dann übersetzt. Es sollte offensichtlich sein, dass das Einlesen der einzelnen Zeichen ein wichtiger Baustein ist. Es muss möglich sein in der Eingabe zurück zu spulen da ein Übersetzer oft einfach ein paar Sachen durchprobieren muss um herauszufinden was ein gewisser Abschnitt darstellt. Zum Beispiel könnte ein Compiler an einer Stelle eine Logik ähnlich zu folgender anwenden: Wenn es keine Zahl ist dann wird es wohl ein String sein und wenn es dies auch nicht ist dann handelt es sich um einen Fehler im Programmcode. Wenn es aber keine Zahl ist so müssen aber alle Zeichen die nötig waren um fest zu stellen, dass es keine Zahl ist erneut interpretiert werden um festzustellen ob es sich vielleicht um einen String handelt. Bei einer Zahl kann man es bereits beim ersten Buchstaben feststellen, jedoch gibt es aber auch komplexere Beispiele wo dies nicht so einfach ist. Hier benötigt man irgendeinen Weg zurückspulen zu können.

Es gibt viele Wege dies nun zu realisieren. Zum Beispiel kann man Zeichenströme schreiben welche immer nur das absolute Minimum von Zeichen im Speicher halten. Man muss ja nicht überall hin spulen können. Es reicht an ein paar bekannte Stellen zurück spulen zu können. Dies ermöglicht es selbst wahnsinnig große Quelldateien zu übersetzen und doch nur ein paar Byte Speicher zu benötigen.

In diesem Artikel wollen wir es allerdings nicht zu kompliziert machen und kopieren die Datei kurzerhand in den Speicher. Eine effiziente Implementierung eines Zeichenstroms wäre ein Thema das in einen anderen Artikel gehört. Unser primitiver Strom wird aus zwei Zeigern bestehen. Einer zeigt auf das Zeichen welches als nächstes verarbeitet werden sollen und der andere auf das erste Zeichen nach dem Ende des Puffers. Es entspricht also einem Iteratorenpaar im Sinn der STL.

Die meisten Funktionen im Übersetzer werden der folgenden ähnlich sehen:

bool foo(..., const char*&pos, const char*end, ...){
	// Do stuff
}

Der erste Zeiger wird per Referenz übergeben damit auch der Aufrufer weiß bis wohin gelesen wurde. end dagegen ist immer gleich und muss deswegen nicht per Referenz übergeben werden. Der Rückgabewert gibt an ob "es" geklappt hat. Was das nun im Detail heißt hängt natürlich von der Funktion ab.

Da wir im Fehlerfall backtracken müssen und eine Ausnahme einen solchen Fall darstellt werde ich Scopeguards einsetzen um den Code ausnahmesicher und lesbar zu halten. Wir werden zwar keine Ausnahmen einsetzen allerdings sollte man doch dafür sorgen, dass der Code ausnahme-freundlich ist.

class BacktrackGuard{
public:
	explicit BacktrackGuard(const char*&pos):
		pos(pos), start(pos){}

	~BacktrackGuard(){
		if(start)
			pos = start;
	}

	void no_backtrack(){
		start = 0;
	}

private:
	const char*&pos;
	const char*start;

	BacktrackGuard(const BacktrackGuard&);
	BacktrackGuard&operator=(const BacktrackGuard&);
};

In vielen Compilen sind diese Zeichenströme auch dafür verantwortlich die Position in der Datei zu merken. Das heißt konkret welche Zeile und das wie vielte Zeichen in dieser. Dies ist zum Beispiel nötig um sinnvolle Fehlermeldungen ausgeben zu können. Wir werden es uns hier aber einfach machen und dieses Problem einfach ignorieren: Wir geben keine Positionsinformationen mit den Fehlern aus.

3 Einfachstes Program

Um anzufangen wollen wir einen Compiler schreiben welche nur eine sehr einfache Sprache übersetzen kann, eine die so einfach ist, dass es schon an Spot grenzt sie als Sprache zu bezeichnen. Ein Programm besteht aus einer einzigen Ziffer und diese muss eine '1' sein. Ein korrektes (und sogar das einzig korrekte) Programm wäre also:

1

Man sollte beachten, dass der Einfachheit zu Liebe keine Leerzeichen erlaubt sind.

Das "1" soll bewirken, dass "1" auf der Konsole ausgegeben wird. Der Compiler hierfür sieht wie folgt aus:

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
using namespace std;

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of program"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Auch wenn dieses Programm nicht all zu kompliziert sein dürfte, reicht es aber um die Grundstruktur zu verdeutlichen. Source code wird eingelesen, dann verarbeitet und der Assembler Code wird in eine Datei namens "out.s" geschrieben. Wo etwas fehlschlagen kann und warum sollte durch die Fehlermeldungen deutlich werden.

Um eine ausführbare Datei zu erzeugen muss "out.s" gegen ein C Sourcecode-Datei gelinkt werden welche folgendermaßen aussieht:

#include <stdio.h>

void prog();

int main(){
	prog();
}

void print_int(int n){
	printf("%d", n);
}

Dieser Schnipsel C Code stellt sozusagen die Laufzeit Bibliothek unserer Sprache dar. Darum nenne ich die Datei "rt.c" (steht für runtime). Übersetzen kann man das ganze recht einfach.

gcc out.s rt.c -o out.exe

Manche GCC Inkarnationen hängen nicht automatischen einen Unterstrich vor C-Funktionsnamen. Wenn die angegebene Commandozeile einen Linkerfehler produziert dann wird das wahrscheinlich der Grund sein. Ändern Sie in diesem Fall die Datei "rt.c" zu:

#include <stdio.h>

void _prog();

int main(){
	_prog();
}

void _print_int(int n){
	printf("%d", n);
}

Nun sollte es keine Probleme mehr geben.

4 Immer noch einfach

Man braucht keinen Hellseher zu sein, um zu bemerken, dass unsere Sprache noch nicht zu viel zu gebrauchen ist. Dies wird vorerst aber leider auch so bleiben. Zuerst arbeiten wir nämlich an der Syntax unserer Sprache.

Es wäre doch gut wenn man mehr Freiheiten beim Setzen der Leerzeichen hätten. Hierfür schreiben wir uns eine Funktion welche Leerzeichen überspringen.

#include <cctype>
//...
void skip_spaces(const char*&pos, const char*end){
	while(pos != end && isspace(*pos))
		++pos;
}

In einem komplexeren Compiler würde diese Funktion auch Kommentare überspringen. Der Rest des Compilers ändert sich nur leicht:

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	skip_spaces(pos, end);		// Ich bin neu (1)
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected at end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		skip_spaces(pos, end);		// Ich auch (2)
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Wozu die erste neue Zeile dient sollte selbsterklärend sein. Die zweite sorgt dafür, dass Leerzeichen sich auch am Ende des Programms befinden können.

Als nächstes werden wir es möglich machen die 1 in Buchstaben auszuschreiben. Dazu schreiben wir eine Funktion welche überprüft ob wir uns vor einem Wort befinden oder nicht. Falls ja wird dieses auch gleich übersprungen.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Nun müssen wir nur noch parse_one anpassen.

void write_print_one_code(std::ostream&out){
	out
		<<"pushl $1"<<endl
		<<"call _print_int"<<endl
		<<"addl $4, %esp"<<endl;
}

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(ignore(pos, end, "1") || ignore(pos, end, "one")){
		write_print_one_code(out);
		return true;
	} else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
}

Wer genau hinschaut bemerkt, dass sich in parse_one kein skip_spaces mehr befindet. Dadurch, dass wir in ignore einen Aufruf platziert haben werden beinahe alle anderen überflüssig und damit ist der Code schon viel weniger fehleranfällig und lesbarer.

Und schon können wir Programme wie folgendes übersetzen.

one

Jedoch hat sich bereits der erste Bug eingeschlichen. Betrachten wir mal:

onehundred

Das Programm wird zwar wie erwünscht abgelehnt aber nicht aus dem richtigen Grund. Der Compiler ließ nur bis zum Ende von "one", übersetzt dies dann auch und das Programm wird nur abgelehnt weil der Compiler nichts mit "hundred" hinter dem Ende des erkannten Programms anzufangen weiß. Das heißt der Compiler reißt Wörter ohne Gewissensbisse in zwei. Es hängt natürlich von der Sprache ab, ob dies ein Fehler ist oder nicht, allerdings nimmt ein C-Compiler kein "staticintfoo" an sondern verlangt, dass diese schön mit Leerzeichen getrennt werden. Dies hat auch seinen guten Grund denn dadurch werden Zweideutigkeiten vermieden. Allerdings übersetzt ein C-Compiler auch "1+2" obwohl zwischen der "1" und dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Operatoren eigene Funktionen schreiben. Die eine würde zusätzlich noch überprüfen ob sich ein Leerzeichen hinter dem Wort befindet.

Es geht allerdings auch einfach.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			--what;
			if(isalpha(*what))
				if(isalnum(*pos))
					return false;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Streng genommen ist dies zwar ein Hack aber er macht doch vieles einfacher und angenehmer.

5 Schon etwas komplizierter

So nun wollen wir auch mal eine Sprache verwenden welche ansatzweise eine Verwendung hat. Ziel ist es einen Compiler zu schreiben der Programme wie folgendes annimmt:

print 1
print 2 print 3
print 4 print 
5

Das Programm besteht aus einer Reihe von "print" Befehlen welche jeweils eine positive Ganzzahl ausgeben.

Als erstes ersetzen wir parse_one (und auch den Aufruf in main) durch folgende Funktion:

bool parse_program(const char*&pos, const char*end, ostream&out){
	while(parse_command(pos, end, out))
		{}
	return true;
}

Wie bereits erwähnt besteht ein Programm aus einer Reihe von Befehlen und darum sollte die Funktion die ein Programm liest auch nur dies tun. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtlich und verständlich.

Um das Lesen eines Befehls kümmert sich dann die Funktion parse_command welche dann wieder auf eine Reihe von Unterfunktion zurückgreift.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		int n;
		if(read_number(pos, end, n)){
			out
				<<"pushl $"<<n<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

bool read_number(const char*&pos, const char*end, int&n){
	skip_spaces(pos, end);
	if(pos != end && isdigit(*pos)){
		n = 0;
		do{
			n *= 10;
			n += *pos - '0';
			++pos;
		}while(pos != end && isdigit(*pos));
		return true;
	}else
		return false;
}

read_number könnte man nun natürlich ach das Lesen von Hexadezimal- oder Octalzahlen beibringen. Wir wollen uns aber mit einfachen Dezimalzahlen begnügen um nicht den Rahmen zu sprengen.

In welche und wie viele Unterfunktionen man aufbrechen soll hängt von der eigenen Erfahrung ab. Hier kann ich höchstens als Faustregel angeben, dass man alles auslagern soll für das man einen passenden Funktionsnamen findet.

6 Taschenrechner

Als nächstes nehmen wir uns vor komplexere Ausdrücke zu unterstützen. Also zum Beispiel folgendes Programm.

print 1+1
print 5*8
print 4 + 8*7

Jeder der mit dem Überladen von Operatoren in C++ vertraut ist, der weiß, dass man Operatoren auch als Funktionsaufrüfe ansehen kann. Den Code oben könnte man auch wie folgend umschreiben.

print add(1, 1)
print mul(5, 8)
print add(4, mul(8, 7))

Auf diese Weise wollen wir unsere Operatoren auch umsetzen, als inline Minifunktionen. Wer schon einmal x86 Assembler geschrieben hat der weiß, dass man eax für Rückgabewerte nutzt. Dies wollen wir auch hier tun. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumente nacheinander aus und nutzt den Stack um Werte zwischen zu speichern.

Allerdings bevor wir uns um die Generierung des Assembler Codes kümmern müssen wir zuerst dafür sorgen, dass wir den Ausdruck richtig lesen können. Hier hilft es sich eine Reihe von Fragen zu stellen:

Woraus besteht ein Program? Aus Befehlen
Woraus besteht ein Befehl? Aus "print" gefolgt von einem Ausdruck
Woraus besteht ein Ausdruck? Aus einer Summe oder Differenz von Termen
Woraus besteht ein Term? Aus einem Produkt, Quotient oder Modulo von Faktoren
Woraus besteht ein Faktor? Aus einer Zahl mit vielleicht einem Vorzeichen

Wer sich für den theoretischen Hintergrund dieser Fragen interessiert der kann mal nach EBNF suchen. In diesem Artikel werde ich aber nicht weiter darauf eingehen.

Nun wissen wir schon welche Funktionen gebraucht werden. Einige der Funktionen sind bereits implementiert und darum werde ich sie nicht wiederholen.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

Diese Funktion sollte selbst erklärend sein.

bool parse_expression(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_term(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "+")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after +"<<endl;
					return false;
				}
				out
					<<"addl (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "-")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after -"<<endl;
					return false;
				}
				out
					<<"subl %eax, (%esp)"<<endl
					<<"pop %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Diese Funktion sieht auf den ersten Blick bedrohlich aus allerdings ist sie an sich recht einfach. Die einzelnen Terme der Summe werden nacheinander ausgewertet und zusammen gezählt beziehungsweise von einander abgezogen.

Die Multiplikation wird ähnlich behandelt.

bool parse_term(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_factor(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "*")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after *"<<endl;
					return false;
				}
				out
					<<"imull (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "/")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl;
			}else if(ignore(pos, end, "%")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl
					<<"movl %edx, %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Die Funktion um Faktoren auszuwerten ist recht einfach da ein Faktor nur aus einer Zahl bestehen kann.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	int n;
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

7 Klammern

Als nächstes wollen wir geklammerte Ausdrücke unterstützen. Fragen wir uns erneut woraus ein Faktor bestehen kann. Wirklich nur aus einer Zahl? Nein unter Umständen auch aus einem geklammerten Ausdruck. Ein Ausdruck besteht - über Umwege - aber wieder aus einem Faktor. Es mag auf den ersten Blick nicht offensichtlich sein allerdings stellen solche rekursiven Definitionen an sich kein Problem dar. Man muss die entsprechende Funktion legentlich rekursiv aufrufen.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	int n;
	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else if(ignore(pos, end, "(")){
		parse_expression(pos, end, out);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

8 Variablen

Das nächste was jeder Compiler beherrschen sollte sind Variablen. Wir wollen uns hier auf lokale Variablen beschränken. Das heißt alle werden auf den Stack gepackt und keine kommen in statischen Speicher. Um die Sache noch weiter zu vereinfachen sind alle Variablen vom Typ int. Dies ist eine ziemlich starke Einschränkung aber irgendwo muss ich ja streichen damit dieser Artikel nicht zu groß wird.

Das erste was benötigt wird ist eine Datenstruktur welche die Variablen verwaltet. Hierfür definiere ich eine Klasse.

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
};

Auf die Implementierungsdetails werde ich nicht eingehen. Eine fertige Implementierung findet man hier.

Es soll möglich sein in höheren Scopes Variablen zu definieren welche Variablen aus den unteren Scopes verdecken. Dieses Verhalten ist natürlich sprachabhängig allerdings wollen wir uns hier einfach an die C Regeln halten. Mit ihnen dürfte jeder Leser vertraut sein.

• create_var erzeugt eine Variable im obersten Scope mit einem gewissen Namen. Falls es bereits eine solche Variable gibt so wird false zurückgegeben andernfalls wird true zurückgegeben.
• Mit is_var_defined kann man ermitteln ob es eine Variable bereits gibt oder nicht. Hier sollte darauf hingewiesen werden, dass diese Funktion nichts über die Erfolgsaussichten von create_var aussagt da Variablen verdeckt werden können.
• get_var_address gibt die Stackadresse der Variable aus. Adressen werden von ebp aus gezählt. Wir müssen also auch die main Funktion anpassen damit ebp einen brauchbaren Wert enthält.
• push_scope sollte aufgerufen wenn sich der Compiler in einen neuen Scope begibt.
• Beim verlassen eines Scopes sollte pop_scope aufgerufen werden. Alle Variablen dieses Scopes werden zerstört.

Der out Parameter ist der Zeichenstrom der den Assembler Code ausgibt. Methoden mit ihm können Code generieren.

Nun müssen wir noch dafür sorgen, dass VarManager überall zugänglich ist. Eine Möglichkeit wäre eine Instanz global anzulegen oder ein Singleton zu basteln. Dies ist aber nicht wirklich die feine Art und führt zu Problemen sobald man den Code parallelisieren möchte. Eine andere Möglichkeit ist eine Instanz in main anzulegen und dann eine Referenz auf diese von Funktion zu Funktion weiter zu geben. Diese Lösung ist viel flexibler allerdings sind Variablen nicht das einzige was verwaltet werden will.

Wer sich ein bisschen mit Schleifen auskennt der weiß, dass da Sprungadressen verwaltet werden müssen. Wenn man Variablen in Register packen will so müssen diese auch verwaltet werden. Wenn wir jetzt auf alles eine Referenz übergeben dann verlieren wir uns bald in endlosen Parameterlisten. Ein noch viel schlimmeres Problem ist, dass man keine neue Struktur einführen kann ohne den ganzen Code umzubauen.

Die Lösung ist recht einfach. Man baut eine Hilfsstrukture welche diese Referenzen verwaltet. Dies sieht dann etwa folgendermaßen aus:

class Env{
public:
	explicit Env(VarManager&var):
		var(var){}

	VarManager&var;
};

Eine Referenz auf diese Klasse wird dann von Funktion zu Funktion übergeben. Wenn eine neue Verwaltungsstruktur hinzugefügt wird so braucht man nur Env und main zu verändern. Der gewählte Name steht für Environment. Als Environment verstehe ich die Zusammenfassung aller Verwaltungsstrukturen.

Man kann die Ausgabe auch als Teil von Env ansehen.

class Env{
public:
	explicit Env(VarManager&var, ostream&out):
		var(var), out(out){}

	VarManager&var;
	ostream&out;
};

Die main Funktion wird also wie folgend abgeändert:

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	Env env(var, out);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
	}
}

parse_command muss nun auch geändert werden da unsere Sprache ja nun zusammengesetzt Befehle mittels Scopes unterstützt. Wir werden hier wie in C Akkoladen verwenden um Scopes zu begrenzen. Um die Funktion klein zu halten lagere ich Teile der Funktion in eine neue Funktion namens parse_block aus.

bool parse_block(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "{")){
		env.var.push_scope();

		while(parse_block(env, pos, end))
			{}

		if(ignore(pos, end, "}")){
			env.var.pop_scope(env.out);
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Missing }"<<endl;
			return false;
		}
	}else{
		guard.no_backtrack();
		return parse_command(env, pos, end);
	}
}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

parse_program können wir dann auch abändern da mehrere Befehle durch die Benutzung von Akkoladen möglich sind.

bool parse_program(Env&env, const char*&pos, const char*end){
	return parse_block(env, pos, end);
}

Nun ist es möglich Programme wie folgendes zu übersetzen.

{
	print 1
	print 2
	{
		print 3
		{}
	}
	print 4
}

Die äußeren Akkoladen sind nötig.

Auch wenn das schon nicht schlecht aussieht haben wir doch einen wesentlichen Bestandteil vergessen. Es gibt noch keine Variablen!

Zuerst brauchen wir eine Funktion die Namen von Variablen liest.

bool read_identifier(const char*&pos, const char*end, string&identifier){
	skip_spaces(pos, end);
	if(pos != end && (isalpha(*pos) || *pos == '_')){
		identifier = "";
		do{
			identifier += *pos;
			++pos;
		}while(pos != end && (isalnum(*pos) || *pos == '_'));
		return true;
	}else
		return false;
}

Das nächste was wir brauchen ist ein Befehl um Variablen zu erschaffen und einen weiteren um ihnen etwas zuzuweisen.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Argument to print is missing"<<endl;
			return false;
		}
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;

	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Jetzt brauchen wir nur noch Möglichkeit lesend auf eine Variable zuzugreifen. Dazu verändere ich parse_factor. Hier lagere ich auch wieder einen Teil der Funktion aus.

bool parse_literal(Env&env, const char*&pos, const char*end){
	int n;
	if(read_number(pos, end, n)){
		env.out<<"movl $"<<n<<", %eax"<<endl;
		return true;
	}
	string identifier;
	if(read_identifier(pos, end, identifier)){
		if(env.var.is_var_defined(identifier)){
			env.out<<"movl "<<env.var.get_var_address(identifier)<<", %eax"<<endl;
			return true;
		}else{
			cerr<<"Undefined variable "<<identifier<<endl;
			return false;
		}
	}

	return false;
}

bool parse_factor(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(parse_literal(env, pos, end)){

	}else if(ignore(pos, end, "(")){
		parse_expression(env, pos, end);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		env.out<<"negl %eax"<<endl;

	guard.no_backtrack();
	return true;
}

Langsam aber sicher entwickelt sich unsere Sprache weiter. Ein Programm sieht jetzt schon aus als könnte es für irgendetwas zu gebrauchen sein.

{
	var a
	var b
	a = 5
	b = a + 5
	{
		a = a-1
		var c
		c = b
		print c
	}
	print a+b
}

9 Hello World!

Im vorherigen Kapitel habe ich gesagt alle Variablen wären vom Typ int. Daran werde ich jetzt auch nichts ändern allerdings benötigt jede Sprache wenigstens eine minimale Unterstützung für Strings. Ohne kann man noch nicht einmal ordentliche Beispielprogramme schreiben. Noch nicht einmal ein "Hello world!"-Programm ist möglich.

Ziel dieses Kapitels ist es den print Befehl ein wenig aufzumotzen. Er soll auch Stringliterale als Parameter übernehmen können und mehrere durch Kommas getrennte Parameter sollen auch unterstützt werden. Er wird aber einzigartig bleiben in dem Sinn, dass nur er Strings als Argument nehmen kann.

Als erstes benötigen wir eine Funktion welche Stringliterale parsen kann.

char unescape_character(char c){
	switch(c){
		case 'n':return '\n';
		case 't':return '\t';
		case '\\':return '\\';
		case '\"':return '\"';
	}
	cerr<<"Unknown escape sequence \\"<<c<<endl;
	return c;
}

bool read_string(const char*&pos, const char*end, string&str){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);
	if(pos != end && *pos == '"'){
		++pos;
		str = "";
		do{
			if(*pos == '\\'){
				++pos;
				if(pos == end){
					cerr<<"EOF in string literal"<<endl;
					return false;
				}
				str += unescape_character(*pos);
			}else
				str += *pos;
			++pos;
		}while(pos != end && *pos != '\"');
		++pos;
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Als nächstes brauchen wir eine Möglichkeit Zeichenketten in den Code einzufügen. Diese werden wir in einer Data-Sektion unterbringen. Wir brauchen also eine weitere Klasse welche die Stringliterale verwaltet.

class DataSection{
public:
	void add_string_data(string label, string data);
	void write_data_section(ostream&);
};

Auch hier werde ich auf eine fertige Implementierung verweisen. Es gibt den offensichtlichen Weg diese Klasse zu implementieren oder man kann versuchen ein paar Bytes zu sparen indem man versucht die Strings so anzuordnen, dass sie sich überlappen. Dies geht natürlich nur solange die originalen Zeichenketten in der Data Sektion nicht verändert werden dürfen.

• Mit add_string_data kann man einen String ablegen. Es wird ein Nullbyte angefügt und Label wird so gesetzt, dass es auf das erste Byte zeigt.
• write_data_section macht das was der Name sagt.

Da DataSection ein Label braucht, brauchen wir auch jemand der diese verwaltet.

class LabelManager{
public:
	string make_unique();
};

• make_unique erzeugt einen eindeutigen Labenamen und gibt diesen zurück.

Die Implementierung gibt es hier.

main und Env müssen auch angepasst werden

class Env{
public:
	explicit Env(VarManager&var, ostream&out, DataSection&data, LabelManager&label):
		var(var), out(out), data(data), label(label){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
};

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	DataSection data;
	LabelManager label;
	Env env(var, out, data, label);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else{
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl
				<<".data"<<endl;
			data.write_data_section(out);
		}
	}
}

Schlussendlich muss auch noch "rt.c" angepasst werden damit Zeichenketten ausgegeben werden können.

#include <string.h>

void print_string(const char*str){
	fwrite(str, 1, strlen(str), stdout);
}

printf will ich nicht benutzen da man bei dieser Funktion auf Prozentzeichen achten muss. Durch die Benutzung von fwrite gehe ich allen möglichen Probleme aus dem Weg, selbst denen die durch Printf-Format-Erweiterungen entstehen könnten.

Da der print-Befehl komplizierter geworden ist lagere ich ihn aus.

bool parse_print(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		do{
			string str;
			if(read_string(pos, end, str)){
				string label = env.label.make_unique();
				env.data.add_string_data(label, str);
				env.out
					<<"pushl $"<<label<<endl
					<<"call _print_string"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(parse_expression(env, pos, end)){
				env.out
					<<"pushl %eax"<<endl
					<<"call _print_int"<<endl
					<<"addl $4, %esp"<<endl;
			}else{
				cerr<<"Argument to print is missing"<<endl;
				return false;
			}
		}while(ignore(pos, end, ","));
		guard.no_backtrack();
		return true;
	}else
		return false;

}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;
	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Nun endlich können wir ein "Hello world"-Programm schreiben.

{
	print "Hello" , " world!\n"
	var a
	var b
	a = 3
	b = 5
	print a, " + ", b, " = ", a+b
}

10 If und Schleifen

Was jetzt noch fehlt sind Abfragen und Schleifen. Diese sind auch nicht sonderlich schwer. Zuerst benötigen wir eine Funktion um ein if einzulesen. Der Einfachheit halber werden wir nicht versuchen die Werte im Statusregister zu halten und wenn möglich wieder zu verwenden. If nutzt einfach wie überall eax und nimmt natürlich auch ein int als Bedingung. Dies ist recht Ineffizient allerdings macht es die Sache doch wesentlich einfacher.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string label = env.label.make_unique();
		if(parse_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<label<<endl;
			if(parse_block(env, pos, end)){
				env.out<<label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

So nun muss nur noch parse_command leicht angepasst werden.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(parse_if(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else 
		...
}

An sich war es das schon allerdings ist ein Vergleich ob denn nun zwei Werte gleich sind noch ziemlich haarig.

{
	var a
	var b
	a = 4
	b = 3
	if a - b
		print "nicht gleich"
}

Deswegen muss parse_expression verändert werden. Als erste nenne ich parse_expression in parse_numeric_expression um und schreibe ein paar weitere Funktion. Diese kümmert sich um das Einlesen der Vergleichsoperatoren und der logischen Verknüpfungen. Dadurch werden die Funktionen nicht endlos lang.

bool parse_compare_expression(Env&env, const char*&pos, const char*end){
	if(ignore(pos, end, "true")){
		env.out<<"movl $1, %eax"<<endl;
		return true;
	}else if(ignore(pos, end, "false")){
		env.out<<"movl $0, %eax"<<endl;
		return true;
	}else if(parse_numeric_expression(env, pos, end)){
		BacktrackGuard guard(pos);
		string condition_code;
		if(ignore(pos, end, "="))
			condition_code = "e";
		else if(ignore(pos, end, "!="))
			condition_code = "ne";
		else if(ignore(pos, end, "<="))
			condition_code = "be";
		else if(ignore(pos, end, ">="))
			condition_code = "ae";
		else if(ignore(pos, end, "<"))
			condition_code = "b";
		else if(ignore(pos, end, ">"))
			condition_code = "a";
		else
			cerr<<"Unknown compare operator"<<endl;
		env.out<<"pushl %eax"<<endl;
		if(parse_numeric_expression(env, pos, end)){
			env.out
				<<"cmpl %eax, (%esp)"<<endl
				<<"movl $0, %eax"<<endl
				<<"set"<<condition_code<<" %al"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

bool parse_boolean_expression(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool not_operation = false;
	if(ignore(pos, end, "!"))
		not_operation = true;
	if(parse_compare_expression(env, pos, end)){
		for(;;){
			string operation;
			if(ignore(pos, end, "&"))
				operation = "and";
			else if(ignore(pos, end, "|"))
				operation = "or";
			else if(ignore(pos, end, "^"))
				operation = "xor";
			else{
				if(not_operation)
					env.out<<"notl %eax"<<endl;
				guard.no_backtrack();
				return true;
			}
			env.out<<"pushl %eax"<<endl;
			if(!parse_compare_expression(env, pos, end))
				return false;
			env.out
				<<operation<<" %eax, (%esp)"<<endl
				<<"addl $4, %esp"<<endl;
		}
	}
	return false;
}

Man sollte beachten, dass die Reihenfolge der Abfragen in parse_compare_expression nicht egal ist. Wenn mehrere Operatoren mit dem gleichen Zeichen anfangen so muss man zuerst auf den längsten testen ansonsten wird der Operator in zwei gerissen. Aus "<=" würde ein "<" gefolgt von einem "=" und dies würde zu einem Fehler führen.

In parse_if wird natürlich parse_boolean_expression verwendet und nicht parse_numeric_expression. Dadurch ist die doppelte Bedeutung von "=" auch nicht zweideutig. Aus dem Kontext heraus kann bestimmt werden ob es ein Vergleich oder eine Zuweisung sein soll.

Nun fehlt nur noch ein else. Dafür müssen wir parse_if anpassen.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string false_label = env.label.make_unique();
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<false_label<<endl;
			if(parse_block(env, pos, end)){
				if(!ignore(pos, end, "else")){
					env.out<<false_label<<":"<<endl;
					guard.no_backtrack();
					return true;
				}
				string end_label = env.label.make_unique();
				env.out
					<<"jmp "<<end_label<<endl
					<<false_label<<":"<<endl;
				if(!parse_block(env, pos, end))
					return false;
				env.out<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Schleifen sind auch nicht sonderlich verschieden von einem if. Als erstes schreibe ich eine parse_while Funktion und die wird dann in parse_command genauso wie parse_if aufgerufen.

bool parse_while(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "while")){
		string 
			reloop_label = env.label.make_unique(),
			end_label = env.label.make_unique();
		env.out<<reloop_label<<":"<<endl;
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<end_label<<endl;
			if(parse_block(env, pos, end)){
				env.out
					<<"jmp "<<reloop_label<<endl
					<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Nun ist unser Compiler schon fähig sinnvolle Programme zu übersetzen. Folgendes Programm zählt von 0 bis 10:

{
	var i
	i = 0
	while i<=10{
		print i, "\n"
		i = i+1
	}
}

Hier ist zum Beispiel ein Programm das alle Primzahlen bis 100 sucht

{
	print "Between 1 and 100 the following prime numbers exist : 2"
	var p
	p = 3
	while p < 100{
		var d 
		d = 2
		var is_prime
		is_prime = 1
		while d<p{
			if p%d = 0{
				is_prime = 0
			}
			d = d+1
		}
		if is_prime != 0{
			print ", ", p
		}
		p = p+1
	}
}

Aufmerksamen Lesern fällt wahrscheinlich auf, dass ich is_prime nicht mit true initialisiere. Nun dies liegt daran, dass dies kein numerischer Wert ist. Diese strikte Unterscheidung zwischen boolschem und numerischem Wert ermöglicht aber auch ein einfaches Gleichzeichen für sowohl eine Zuweisung und einen Vergleich zu nehmen. Es hat also sowohl Vor- wie auch Nachteile. In einer kompletten Sprache gäbe es natürlich auch einen boolschen Typ und dadurch wäre das Problem elegant gelöst.

Eine for-Schleife ist nicht signifikant anders und ihre Implementierung wird dem Leser überlassen.

11 Funktionen

Funktion sind die Bausteine jedes komplexeren Programms. Darum will ich sie auch in diesem Artikel nicht auslassen. Mit Funktionen kann man an sich was die Komplexität angeht beliebig nach oben steigern. Templatefunktionen sind ein gutes Beispiel dafür. Hier will ich mich aber auf recht einfache Funktionen beschränken. Für jede Funktion speichern wir den Namen und die Anzahl der Parameter. Da es nur int als Variabletyp gibt brauchen wir keine Informationen über die Typen der Parameter zu speichern. Der Rückgabewert ist auch immer ein int. Funktionen ohne Rückgabetyp machen natürlich Sinn aber das machen Templatefunktionen auch. Als Kompromiss zwischen Sinnvollkeit und Einfachheit lassen wir es zu, dass ein Rückgabewert nicht initialisiert ist. Das heißt er enthält Schrott.

Funktionen müssen wie in C im voraus deklariert werden und können mehrfach gleich deklariert werden. Sie können nicht überladen werden. Als Aufrufskonvention werden wir eine verwenden die des GCCs ähnlich ist. Dadurch können wir auch ohne weiteres gegen C Code linken. Der Unterschied besteht darin, dass Argumente von links nach rechts auf den Stack gepackt werden. Beim GCC werden die Parameter von rechts nach links auf den Stack gepackt. Der Grund hierfür ist, dass es so für uns einfacher ist. Der Aufrufer ist dafür verantwortlich die Argumente wieder vom Stack zu nehmen. Eine Funktion darf ihre Parameter verändern. Der Aufrufer darf also keine Argumente recyceln. Der Rückgabewert befindet sich in eax.

Als erstes brauchen wir eine Klasse um die Informationen zu verwalten. Ich werde wieder einmal nur auf die Klassenschnittstelle eingehen und auf eine Implementierung verweisen.

class FuncManager{
public:
	bool declare(string name, unsigned parameter_count);
	bool exists(string name)const;
	string get_label(string name)const;
	unsigned get_parameter_count(string name)const;
};

• declare macht eine Funktion bekannt.
• exists überprüft ob eine Funktion bekannt gemacht wurde.
• get_label gibt das Label des Funktionskörper zurück.
• Mit get_parameter_count findet man heraus wie viele Parameter eine Funktion braucht.

Um auf Argumente zurück greifen zu können und Wert zurück geben zu können müssen wir auch VarManager verändern. Konkret werden ein paar Methoden hinzugefügt und die Klasse sieht nun folgendermaßen aus:

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool add_arg(string name, unsigned pos);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
	void simulate_pop_all_scopes(ostream&out)const;
};

• add_arg gibt einem Parameter einen Namen. pos gibt an um das wie vielte Argument von links es sich handelt. Das erste Argument hat den Index 0. Der Rückgabewert gibt an ob es bereits einen solchen Parameter gab oder nicht. Argumente werden in ihrem eigenen Scope angelegt und darum können sie mit gleichnamigen lokalen Variablen koexistieren. Sie werden jedoch von denen verdeckt.
• simulate_pop_all_scopes generiert Code um alle Scopes zu löschen ohne dies jedoch zu tun. Dies wird benötigt um ein return wie in C zu realisieren. Für andere Formen von Sprüngen wie zum Beispiel break würde man einen ähnlichen Mechanismus benötigen.

Eine Implementierung gibt es hier.

In einem C Programm unterscheidet man zwischen globalen Scope und Funktionskörper. In beiden Bereichen sind unterschiedliche Sprachkonstrukte erlaubt. So kann man zum Beispiel keine Funktion innerhalb einer anderen definieren. Schleifen können sich auch nicht im globalen Scope befinden. Diesen Unterschied wollen wir nun auch in unserer Sprache einführen.

Da wir keine globalen Variablen zulassen kann man sich fragen ob ein VarManager im globalen Scope Sinn macht. Meiner Meinung nach nicht. Deswegen gibt es auch für beide Teile des Programms unterschiedliche Env Strukturen. Die eine nenne ich FuncEnv da sie nur innerhalb einer Funktion Sinn macht und die andere einfach Env. Da wir uns bis jetzt nur um den Inhalt von Funktionen gekümmert haben wird jedes alte Env in ein FuncEnc umbenannt.

struct FuncEnv{
	explicit FuncEnv(VarManager&var, ostream&out, DataSection&data, LabelManager&label, const FuncManager&func):
		var(var), out(out), data(data), label(label), func(func){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
	const FuncManager&func;
};

struct Env{
	explicit Env(ostream&out, DataSection&data, LabelManager&label, FuncManager&func):
		out(out), data(data), label(label), func(func){}

	ostream&out;
	DataSection&data;
	LabelManager&label;
	FuncManager&func;
};

Der FuncManager in FuncEnv ist konstant da man keine Funktion innerhalb einer anderen erschaffen kann. In main wird eine Instanz von FuncManager angelegt wie wir es bereits für die meisten anderen Verwaltungsstrukturen gemacht haben.

Als nächstes brauchen wir eine Funktion zum Einlesen von Funktionsdefinitionen und Deklarationen.

bool read_arg_list(const char*&pos, const char*end, vector<string>&args){
	BacktrackGuard guard(pos);
	if(!ignore(pos, end, "("))
		return false;
	string arg_name;
	while(read_identifier(pos, end, arg_name)){
		args.push_back(arg_name);
		if(!ignore(pos, end, ","))
			break;
	}
	if(!ignore(pos, end, ")"))
		return false;
	guard.no_backtrack();
	return true;
}

bool parse_function(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;

	vector<string>arguments;
	if(!read_arg_list(pos, end, arguments))
		return false;

	if(env.func.exists(func_name)){
		if(env.func.get_parameter_count(func_name) != arguments.size())
			cerr<<"Function "<<func_name<<" redeclared with wrong argument number"<<endl;
	}else
		env.func.declare(func_name, arguments.size());

	if(ignore(pos, end, ";")){
		guard.no_backtrack();
		return true;
	}

	VarManager var;

	for(unsigned j=0; j<arguments.size(); ++j)
		if(!var.add_arg(arguments[j], arguments.size()-j-1))
			cerr<<"2 arguments with same name "<<arguments[j]<<" in function "<<func_name<<endl;

	env.out
		<<".globl "<<env.func.get_label(func_name)<<endl
		<<env.func.get_label(func_name)<<":"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;
	;

	FuncEnv fenv(var, env.out, env.data, env.label, env.func);
	if(parse_block(fenv, pos, end)){
		env.out
			<<"pop %ebp"<<endl
			<<"ret"<<endl;
		guard.no_backtrack();
		return true;
	}

	return false;
}

Als nächstes sorgen wir dafür, dass man eine Funktion auch aufgerufen werden kann. Dafür schreiben wir uns als erstes eine Funktion die einen Aufruf einliest.

bool parse_function_call(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;
	else{
		if(ignore(pos, end, "(")){
			unsigned parameter_count = 0;
			if(!ignore(pos, end, ")")){
				do{
					if(!parse_numeric_expression(env, pos, end))
						return false;
					env.out<<"pushl %eax"<<endl;
					++parameter_count;
				}while(ignore(pos, end, ","));
				if(!ignore(pos, end, ")"))
					return false;
			}

			if(!env.func.exists(func_name))
				cerr<<"Unknown function "<<func_name<<endl;
			else if(env.func.get_parameter_count(func_name) != parameter_count)
				cerr<<"Wrong number of parameters to function "<<func_name<<endl;
			else{
				env.out<<"call "<<env.func.get_label(func_name)<<endl;
				if(parameter_count != 0)
					env.out<<"addl $"<<4*parameter_count<<", %esp"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
		return false;
	}
}

Eine Funktion kann innerhalb eines Ausdrucks und eines Befehls aufgerufen. Es müssen also parse_factor und parse_command verändert werden. In parse_factor muss man parse_function_call vor parse_literal aufrufen, da ansonsten der Funktionsname als Variable interpretiert wird.

Nun fehlt nur noch die Möglichkeit einen Wert zurück zu geben. Die Funktion die sich darum kümmert sollte nicht zu kompliziert sein wenn man es geschafft hat bis hier zu folgen.

bool parse_return(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	if(ignore(pos, end, "return")){
		if(parse_numeric_expression(env, pos, end)){
			env.var.simulate_pop_all_scopes(env.out);
			env.out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Diese Funktion wird nun noch in parse_command aufgerufen und schon können wir Funktionen übersetzen.

Nun müssen wir nur noch parse_program und main anpassen.

bool parse_program(Env&env, const char*&pos, const char*end){
	while(parse_function(env, pos, end))
	{}

	return true;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out<<".text"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	DataSection data;
	LabelManager label;
	FuncManager func;
	Env env(out, data, label, func);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			data.write_data_section(out);
	}
}

Ein "Hello World"-Programm sieht nun wie folgend aus:

prog(){
	print "Hello World!"
}

Selbst rekursive Funktionen sind kein Problem. Folgendes Programm berechnet die Fakultät einer Zahl rekursiv:

fact(n){
	if n = 0
		return 1
	else
		return n*fact(n-1)
}

prog(){
	print fact(9)
}

Wir können aber nun auch gegen C-Funktionen linken. Zum Beispiel kann man so etwas von der Konsole einlesen.

int read_int(){
	int r = -1;
	scanf("%d", &r);
	return r;
}

read_int();

prog(){
	var a
	print "a = "
	a = read_int()
	var b
	print "b = "
	b = read_int()
	print "a + b = ", a+b
	print "a - b = ", a-b
	print "a * b = ", a*b
	print "a / b = ", a/b
	print "a % b = ", a%b

}

Man muss nur beachten, dass die Parameter in C eine andere Reihenfolge haben werden. Die Funktion test(a,b,c) würde der C-Funktion test(c,b,a) entsprechen.

12 Parser Baum

Wer schon mal vorher mit der Materie in Kontakt gekommen ist wird sich wahrscheinlich wundern warum ich ihn bis jetzt noch nicht erwähnt habe, ja vielleicht sogar wundern wie wir überhaupt so weit ohne ihn gekommen sind. Die Rede ist vom Parser Baum.

Die Idee ist es das Interpretieren der Eingangszeichenkette und dem Generieren der Assembler Codes zu trennen. Diese Trennung bietet viele Vorteile wobei die Möglichkeit elegant mehrere Prozessoren zu unterstützen nur die offensichtlichste ist.

Der Parser liest den Code und generiert einen Baum welcher alle wichtigen Informationen enthält. Der Generator nimmt diesen Baum dann und generiert den entsprechenden Code. Dies macht Arbeitsteilung im Entwickelerteam viel einfacher da beide Teile nun unabhängig von einander sind.

Ein weiterer großer Vorteil ist, dass es möglich wird Funktionen zu inlinen und auch andere Optimierungen durch zu führen. Ich wüsste nicht wie man dem Compiler so wie er hier vorgestellt wurde beibringen soll Funktionaufrüfe zu ersetzen. Wenn man den Code allerdings als Baum vorliegen hat entspricht so muss man nur einen Ast des Baums kopieren und noch ein paar Umformungen bezüglich der Variabelnamen durchführen. In einem Baum ist es auch leicht Informationen über Unterausdrücke einzuholen. Zum Beispiel ob ein Ausdruck noch was anderes tut außer den Rückgabewert zu berechen. Dies ist wichtig um zum Beispiel 0*x durch 0 zu ersetzen.

In diesem Artikel wollen wir aber keinen Parserbaum mehr entwickeln. Es würde einfach den Rahmen sprengen.

13 Schlussbemerkung

Ziel dieses Artikels war es den Leser in das Gebiet des Compilerbaus einzuführen und zwar ohne ihn mit Theorie zu bombardieren. Ich hoffe Sie haben jetzt einen Überblick über die Materie und können sich vorstellen wo man die Aussagen der Theorie praktisch einsetzen kann. Wer sich für das Thema interessiert dem sei gesagt, dass es sich hier nur um die Spitze des Eisbergs handelt. Es gibt noch sehr viel was in diesem Artikel noch nicht einmal mit einem Wort erwähnt wurde.

Ob es von meiner Seits einen weiteren Artikel zu diesem Thema geben wird ist ungewiss. Es fällt mir schwer ein zu schätzen ob ich in Zukunft noch genug Zeit aufbringen kann und Motivation. Natürlich hängt es auch davon ab wie viele Leute sich dafür interessieren.

[GPC]

Soooo... ich hab' noch mal alles gelesen und kann logisch keine Ungereimtheiten erkennen. Den Code habe ich auch zusammengesucht und durch den Compiler (VC++ 8.0) gejagt.

Und da unten ist er dann auch, abgesehen von einigen Sachen, die ich in Headern ausgelagert habe.

Folgende Änderungen meinerseits, dass er kompiliert:
+ FuncManager::declare hab' ich mal const gemacht.
+ zwei static_casts wegen Typkonvertierung eingeführt (in parse_function)
+ In parse_function: arguments[i] statt arguments übergeben
+ VarManager fehlt in main bei Konstruktion von Env.
+ Außerdem wird in der main zum Schluß ein normales Env konstruiert, ich jedoch habe alles auf FuncEnv umgestellt (war mir nicht sicher, ob das passt oder nicht)
+ Beim Aufbau von parse_command war ich mir nicht sicher, wie's aussehen muss

Nun ja, er kompiliert, funktioniert aber nicht. Es haut mir bei der Quelldatei:

{
    var i
    i = 0
    while i<=10{
        print i, "\n"
        i = i+1
    }
}

immer "Unexpected trailing characters at end of file" an den Kopf. Und ich finde nicht raus, warum.

#include <iostream>
#include <ostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <iterator>
#include <string>
#include <algorithm>
#include <cctype>
#include <cassert>

#include "backtrackguard.hpp"
#include "varmanager.hpp"
#include "datasection.hpp"
#include "labelmanager.hpp"

using namespace std; 

class FuncManager{
public:
	bool declare(string name, unsigned parameter_count) const {return false;}
	bool exists(string name)const {return false;}
	string get_label(string name)const {return "";}
	unsigned get_parameter_count(string name)const {return 0;}
};

struct FuncEnv{
    explicit FuncEnv(VarManager&var, ostream&out, DataSection&data, LabelManager&label, const FuncManager&func):
        var(var), out(out), data(data), label(label), func(func){}

    VarManager&var;
    ostream&out;
    DataSection&data;
    LabelManager&label;
    const FuncManager&func;
}; 

/*class Env{
public:
    explicit Env(VarManager&var, ostream&out, DataSection&data, LabelManager&label, FuncManager&func):
        var(var), out(out), data(data), label(label), func(func){}

    VarManager&var;
    ostream&out;
    DataSection&data;
    LabelManager&label;
	FuncManager&func;
}; */

void skip_spaces(const char*&pos, const char*end);
bool ignore(const char*&pos, const char*end, const char*what);
char unescape_character(char c);
bool read_string(const char*&pos, const char*end, string&str);
bool read_identifier(const char*&pos, const char*end, string&identifier);
bool read_number(const char*&pos, const char*end, int&n);
bool read_arg_list(const char*&pos, const char*end, vector<string>&args);
bool parse_return(FuncEnv&env, const char*&pos, const char*end);
bool parse_function_call(FuncEnv&env, const char*&pos, const char*end);
bool parse_function(FuncEnv&env, const char*&pos, const char*end);
bool parse_while(FuncEnv&env, const char*&pos, const char*end);
bool parse_if(FuncEnv&env, const char*&pos, const char*end);
bool parse_literal(FuncEnv&env, const char*&pos, const char*end);
bool parse_factor(FuncEnv&env, const char*&pos, const char*end);
bool parse_term(FuncEnv&env, const char*&pos, const char*end);
bool parse_compare_expression(FuncEnv&env, const char*&pos, const char*end);
bool parse_boolean_expression(FuncEnv&env, const char*&pos, const char*end);
bool parse_numeric_expression(FuncEnv&env, const char*&pos, const char*end);
bool parse_block(FuncEnv&env, const char*&pos, const char*end);
bool parse_print(FuncEnv&env, const char*&pos, const char*end);
bool parse_command(FuncEnv&env, const char*&pos, const char*end);
bool parse_program(FuncEnv&env, const char*&pos, const char*end);

int main() {
	ifstream in("in.txt");
    vector<char>source_code;
    copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

    ofstream out("out.s");
    out<<".text"<<endl;

    const char*pos = &source_code.front();
    const char*end = &source_code.back() + 1;

	VarManager var;
    DataSection data;
    LabelManager label;
    FuncManager func;
    FuncEnv env(var, out, data, label, func);

    if(parse_program(env, pos, end)){
        skip_spaces(pos, end);
        if(pos != end)
            cerr<<"Unexpected trailing characters at end of file"<<endl;
        else
            data.write_data_section(out);
    } 
	return EXIT_SUCCESS;
}

void skip_spaces(const char*&pos, const char*end){
    while(pos != end && isspace(*pos))
        ++pos;
}

bool ignore(const char*&pos, const char*end, const char*what){
    BacktrackGuard guard(pos);
    skip_spaces(pos, end);

    while(pos != end && *pos == *what){
        ++what;
        ++pos;
        if(*what == '\0'){
            --what;
            if(isalpha(*what))
                if(isalnum(*pos))
                    return false;
            guard.no_backtrack();
            return true;
        }
    }
    return false;
}

char unescape_character(char c){
    switch(c){
        case 'n':return '\n';
        case 't':return '\t';
        case '\\':return '\\';
        case '\"':return '\"';
    }
    cerr<<"Unknown escape sequence \\"<<c<<endl;
    return c;
}

bool read_string(const char*&pos, const char*end, string&str){
    BacktrackGuard guard(pos);
    skip_spaces(pos, end);
    if(pos != end && *pos == '"'){
        ++pos;
        str = "";
        do{
            if(*pos == '\\'){
                ++pos;
                if(pos == end){
                    cerr<<"EOF in string literal"<<endl;
                    return false;
                }
                str += unescape_character(*pos);
            }else
                str += *pos;
            ++pos;
        }while(pos != end && *pos != '\"');
        ++pos;
        guard.no_backtrack();
        return true;
    }else
        return false;
}

bool read_identifier(const char*&pos, const char*end, string&identifier){
    skip_spaces(pos, end);
    if(pos != end && (isalpha(*pos) || *pos == '_')){
        identifier = "";
        do{
            identifier += *pos;
            ++pos;
        }while(pos != end && (isalnum(*pos) || *pos == '_'));
        return true;
    }else
        return false;
}

bool read_number(const char*&pos, const char*end, int&n){
    skip_spaces(pos, end);
    if(pos != end && isdigit(*pos)){
        n = 0;
        do{
            n *= 10;
            n += *pos - '0';
            ++pos;
        }while(pos != end && isdigit(*pos));
        return true;
    }else
        return false;
}

bool read_arg_list(const char*&pos, const char*end, vector<string>&args){
    BacktrackGuard guard(pos);
    if(!ignore(pos, end, "("))
        return false;
    string arg_name;
    while(read_identifier(pos, end, arg_name)){
        args.push_back(arg_name);
        if(!ignore(pos, end, ","))
            break;
    }
    if(!ignore(pos, end, ")"))
        return false;
    guard.no_backtrack();
    return true;
}

bool parse_return(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);

    if(ignore(pos, end, "return")){
        if(parse_numeric_expression(env, pos, end)){
            env.var.simulate_pop_all_scopes(env.out);
            env.out
                <<"pop %ebp"<<endl
                <<"ret"<<endl;
            guard.no_backtrack();
            return true;
        }
    }
    return false;
}

bool parse_function_call(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);

    string func_name;
    if(!read_identifier(pos, end, func_name))
        return false;
    else{
        if(ignore(pos, end, "(")){
            unsigned parameter_count = 0;
            if(!ignore(pos, end, ")")){
                do{
                    if(!parse_numeric_expression(env, pos, end))
                        return false;
                    env.out<<"pushl %eax"<<endl;
                    ++parameter_count;
                }while(ignore(pos, end, ","));
                if(!ignore(pos, end, ")"))
                    return false;
            }

            if(!env.func.exists(func_name))
                cerr<<"Unknown function "<<func_name<<endl;
            else if(env.func.get_parameter_count(func_name) != parameter_count)
                cerr<<"Wrong number of parameters to function "<<func_name<<endl;
            else{
                env.out<<"call "<<env.func.get_label(func_name)<<endl;
                if(parameter_count != 0)
                    env.out<<"addl $"<<4*parameter_count<<", %esp"<<endl;
                guard.no_backtrack();
                return true;
            }
        }
        return false;
    }
}

bool parse_function(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    string func_name;
    if(!read_identifier(pos, end, func_name))
        return false;

    vector<string>arguments;
    if(!read_arg_list(pos, end, arguments))
        return false;

    if(env.func.exists(func_name)){
        if(env.func.get_parameter_count(func_name) != arguments.size())
            cerr<<"Function "<<func_name<<" redeclared with wrong argument number"<<endl;
    }else
        env.func.declare(func_name, static_cast<unsigned>(arguments.size()) );

    if(ignore(pos, end, ";")){
        guard.no_backtrack();
        return true;
    }

    VarManager var;

    for(unsigned i=0; i<arguments.size(); ++i)
        if(!var.add_arg(arguments[i], static_cast<unsigned>(arguments.size()-i-1) ))
            cerr<<"2 arguments with same name "<<arguments[i]<<" in function "<<func_name<<endl;

    env.out
        <<".globl "<<env.func.get_label(func_name)<<endl
        <<env.func.get_label(func_name)<<":"<<endl
        <<"push %ebp"<<endl
        <<"mov %esp, %ebp"<<endl;
    ;

    FuncEnv fenv(var, env.out, env.data, env.label, env.func);
    if(parse_block(fenv, pos, end)){
        env.out
            <<"pop %ebp"<<endl
            <<"ret"<<endl;
        guard.no_backtrack();
        return true;
    }

    return false;
}

bool parse_while(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(ignore(pos, end, "while")){
        string
            reloop_label = env.label.make_unique(),
            end_label = env.label.make_unique();
        env.out<<reloop_label<<":"<<endl;
        if(parse_boolean_expression(env, pos, end)){
            env.out
                <<"testl %eax, %eax"<<endl
                <<"jz "<<end_label<<endl;
            if(parse_block(env, pos, end)){
                env.out
                    <<"jmp "<<reloop_label<<endl
                    <<end_label<<":"<<endl;
                guard.no_backtrack();
                return true;
            }
        }
    }
    return false;
}

bool parse_if(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(ignore(pos, end, "if")){
        string false_label = env.label.make_unique();
        if(parse_boolean_expression(env, pos, end)){
            env.out
                <<"testl %eax, %eax"<<endl
                <<"jz "<<false_label<<endl;
            if(parse_block(env, pos, end)){
                if(!ignore(pos, end, "else")){
                    env.out<<false_label<<":"<<endl;
                    guard.no_backtrack();
                    return true;
                }
                string end_label = env.label.make_unique();
                env.out
                    <<"jmp "<<end_label<<endl
                    <<false_label<<":"<<endl;
                if(!parse_block(env, pos, end))
                    return false;
                env.out<<end_label<<":"<<endl;
                guard.no_backtrack();
                return true;
            }
        }
    }
    return false;
}

bool parse_literal(FuncEnv&env, const char*&pos, const char*end){
    int n;
    if(read_number(pos, end, n)){
        env.out<<"movl $"<<n<<", %eax"<<endl;
        return true;
    }
    string identifier;
    if(read_identifier(pos, end, identifier)){
        if(env.var.is_var_defined(identifier)){
            env.out<<"movl "<<env.var.get_var_address(identifier)<<", %eax"<<endl;
            return true;
        }else{
            cerr<<"Undefined variable "<<identifier<<endl;
            return false;
        }
    }

    return false;
} 

bool parse_factor(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    bool negate = false;
    if(ignore(pos, end, "-"))
        negate = true;

    if(parse_literal(env, pos, end)){

    }else if(ignore(pos, end, "(")){
        parse_numeric_expression(env, pos, end);
        if(!ignore(pos, end, ")"))
            cerr<<"Missing )"<<endl;
    }else
        return false;

    if(negate)
        env.out<<"negl %eax"<<endl;

    guard.no_backtrack();
    return true;
}

bool parse_term(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(parse_factor(env, pos, end)){
        for(;;){
            if(ignore(pos, end, "*")){
                env.out<<"push %eax"<<endl;
                if(!parse_factor(env, pos, end)){
                    cerr<<"Expected factor after *"<<endl;
                    return false;
                }
                env.out
						<<"imull (%esp), %eax"<<endl
						<<"addl $4, %esp"<<endl;
            }else if(ignore(pos, end, "/")){
                env.out<<"push %eax"<<endl;
                if(!parse_factor(env, pos, end)){
                    cerr<<"Expected factor after /"<<endl;
                    return false;
                }

                env.out
						<<"movl %eax, %ebx"<<endl
						<<"pop %eax"<<endl
						<<"movl $0, %edx"<<endl
						<<"idiv %ebx"<<endl;
            }else if(ignore(pos, end, "%")){
                env.out<<"push %eax"<<endl;
                if(!parse_factor(env, pos, end)){
                    cerr<<"Expected factor after /"<<endl;
                    return false;
                }

                env.out
						<<"movl %eax, %ebx"<<endl
						<<"pop %eax"<<endl
						<<"movl $0, %edx"<<endl
						<<"idiv %ebx"<<endl
						<<"movl %edx, %eax"<<endl;
            }else
                break;
        }
        guard.no_backtrack();
        return true;
    }else
        return false;
}

bool parse_compare_expression(FuncEnv&env, const char*&pos, const char*end){
    if(ignore(pos, end, "true")){
        env.out<<"movl $1, %eax"<<endl;
        return true;
    }else if(ignore(pos, end, "false")){
        env.out<<"movl $0, %eax"<<endl;
        return true;
    }else if(parse_numeric_expression(env, pos, end)){
        BacktrackGuard guard(pos);
        string condition_code;
        if(ignore(pos, end, "="))
            condition_code = "e";
        else if(ignore(pos, end, "!="))
            condition_code = "ne";
        else if(ignore(pos, end, "<="))
            condition_code = "be";
        else if(ignore(pos, end, ">="))
            condition_code = "ae";
        else if(ignore(pos, end, "<"))
            condition_code = "b";
        else if(ignore(pos, end, ">"))
            condition_code = "a";
        else
            cerr<<"Unknown compare operator"<<endl;
        env.out<<"pushl %eax"<<endl;
        if(parse_numeric_expression(env, pos, end)){
            env.out
                <<"cmpl %eax, (%esp)"<<endl
                <<"movl $0, %eax"<<endl
                <<"set"<<condition_code<<" %al"<<endl
                <<"addl $4, %esp"<<endl;
            guard.no_backtrack();
            return true;
        }
    }
    return false;
}

bool parse_boolean_expression(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    bool not_operation = false;
    if(ignore(pos, end, "!"))
        not_operation = true;
    if(parse_compare_expression(env, pos, end)){
        for(;;){
            string operation;
            if(ignore(pos, end, "&"))
                operation = "and";
            else if(ignore(pos, end, "|"))
                operation = "or";
            else if(ignore(pos, end, "^"))
                operation = "xor";
            else{
                if(not_operation)
                    env.out<<"notl %eax"<<endl;
                guard.no_backtrack();
                return true;
            }
            env.out<<"pushl %eax"<<endl;
            if(!parse_compare_expression(env, pos, end))
                return false;
            env.out
                <<operation<<" %eax, (%esp)"<<endl
                <<"addl $4, %esp"<<endl;
        }
    }
    return false;
}

bool parse_numeric_expression(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(parse_term(env, pos, end)){
        for(;;){
            if(ignore(pos, end, "+")){
                env.out<<"push %eax"<<endl;
                if(!parse_term(env, pos, end)){
                    cerr<<"Expected term after +"<<endl;
                    return false;
                }
                env.out
						<<"addl (%esp), %eax"<<endl
						<<"addl $4, %esp"<<endl;
            }else if(ignore(pos, end, "-")){
                env.out<<"push %eax"<<endl;
                if(!parse_term(env, pos, end)){
                    cerr<<"Expected term after -"<<endl;
                    return false;
                }
                env.out
						<<"subl %eax, (%esp)"<<endl
						<<"pop %eax"<<endl;
            }else
                break;
        }
        guard.no_backtrack();
        return true;
    }else
        return false;
}

bool parse_block(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(ignore(pos, end, "{")){
        env.var.push_scope();

        while(parse_block(env, pos, end))
            {}

        if(ignore(pos, end, "}")){
            env.var.pop_scope(env.out);
            guard.no_backtrack();
            return true;
        }else{
            cerr<<"Missing }"<<endl;
            return false;
        }
    }else{
        guard.no_backtrack();
        return parse_command(env, pos, end);
    }
}

bool parse_print(FuncEnv&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(ignore(pos, end, "print")){
        do{
            string str;
            if(read_string(pos, end, str)){
                string label = env.label.make_unique();
                env.data.add_string_data(label, str);
                env.out
                    <<"pushl $"<<label<<endl
                    <<"call _print_string"<<endl
                    <<"addl $4, %esp"<<endl;
            }else if(parse_numeric_expression(env, pos, end)){
                env.out
                    <<"pushl %eax"<<endl
                    <<"call _print_int"<<endl
                    <<"addl $4, %esp"<<endl;
            }else{
                cerr<<"Argument to print is missing"<<endl;
                return false;
            }
        }while(ignore(pos, end, ","));
        guard.no_backtrack();
        return true;
    }else
        return false; 
} 

bool parse_command(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
    if(parse_print(env, pos, end)){
        guard.no_backtrack();
        return true;
    }else if(parse_if(env, pos, end)){
        guard.no_backtrack();
        return true;
    /*}else if(ignore(pos, end, "var")){
        string identifier;
        if(read_identifier(pos, end, identifier)){
            if(env.var.create_var(identifier, env.out)){
                guard.no_backtrack();
                return true;
            }else
                cerr<<"Variable redefined"<<endl;
        }else
            cerr<<"var must be followed by a variable name"<<endl;
        return false;*/
    }else{
        string identifier;
        if(read_identifier(pos, end, identifier)){
            if(ignore(pos, end, "=")){
                if(parse_numeric_expression(env, pos, end)){
                    env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
                    guard.no_backtrack();
                    return true;
                }else
                    cerr<<"Missing right operant of ="<<endl;
            }else
                cerr<<"Missing = in assignment"<<endl;

        }
        return false;
    }
}
bool parse_program(FuncEnv&env, const char*&pos, const char*end){
    while(parse_function(env, pos, end))
		{}       
    return true;
}

[Ben04]

GPC schrieb:

Soooo... ich hab' noch mal alles gelesen und kann logisch keine Ungereimtheiten erkennen.

Danke

Und da unten ist er dann auch, abgesehen von einigen Sachen, die ich in Headern ausgelagert habe.

Folgende Änderungen meinerseits, dass er kompiliert:
+ zwei static_casts wegen Typkonvertierung eingeführt (in parse_function)

Hat der VC einen signed vector<...>::size_type ? Ansonsten kann ich mir nicht erklären wieso diese nötig wären.

+ In parse_function: arguments[i] statt arguments übergeben

Ich glaub hier hat das Forum die [i]s missinterpretiert. Ich habe es verbessert indem ich i durch j ersetzt habe

+ VarManager fehlt in main bei Konstruktion von Env.

Ich glaub du hast den Teil mit Env/FuncEnv nicht verstanden. FuncEnv soll an Funktionen übergeben werden, welche den Inhalt einer Funktion parsen (also lokaler Scope). Env an Funktionen welche sich im globalen Scope befinden.

In dem von mir angegebenen Env befindet sich kein VarManager und deswegen fehlt der auch nicht. Da er den lokalen Stack managed macht er auch nur im lokalen Kontext Sinn, das heißt in FuncEnv.

+ FuncManager::declare hab' ich mal const gemacht.

Das soll es aber nicht sein. Auf FuncManager::declare soll nur Zugriff haben wer sich im globablen Scope befindet. In Env ist der FuncManager deshalb nicht const und in FuncEnv ist er es.

+ Außerdem wird in der main zum Schluß ein normales Env konstruiert, ich jedoch habe alles auf FuncEnv umgestellt (war mir nicht sicher, ob das passt oder nicht)

In main wird immer ein Env konstruiert da man da im Programm zuerst im global Scope ist. Erst in parse_function kommt der lokal Scope ins Spiel und mit ihm FuncEnv und VarManager.

+ Beim Aufbau von parse_command war ich mir nicht sicher, wie's aussehen muss

Beim einfügen von parse_while?

bool parse_command(Env&env, const char*&pos, const char*end){
    BacktrackGuard guard(pos);
    if(parse_print(env, pos, end)){
        guard.no_backtrack();
        return true;
    }else if(parse_if(env, pos, end)){
        guard.no_backtrack();
        return true;
    }else if(parse_while(env, pos, end)){
        guard.no_backtrack();
        return true;
    }else if(ignore(pos, end, "var")){
        string identifier;
        ...
    }else{
        ...
    }
}

Die Logik ist die die ich in der Einleitung erläutert habe.

Wenn es keine Zahl ist dann wird es wohl ein String sein und wenn es dies auch nicht ist dann handelt es sich um einen Fehler im Programmcode

Wenn es kein print ist, dann wird es wohl ein if sein und wenn es dies auch nicht ist, dann wird es wohl ein while sein ansonsten könnte es noch ein var sein und wenn das auch nicht geht dann könnte es noch eine vom Benutzer definierte Funktionen sein.

Nun ja, er kompiliert, funktioniert aber nicht. Es haut mir bei der Quelldatei:

{
    var i
    i = 0
    while i<=10{
        print i, "\n"
        i = i+1
    }
}

immer "Unexpected trailing characters at end of file" an den Kopf. Und ich finde nicht raus, warum.

Die Fehlermeldungen sind wirklich nicht immer hilfreich, allerdings sind gute Fehlermeldungen eine Wissenschaft für sich.

Der Grund hier ist, dass die letzte Version des Compiler dieses Programm gar nicht übersetzen können soll. Das müsste folgendermaßen aussehen:

prog(){
    var i
    i = 0
    while i<=10{
        print i, "\n"
        i = i+1
    }
}

"int main()" vergessen.

PS: Hab auch die Links gefixt.

[GPC]

Ben04 schrieb:

Folgende Änderungen meinerseits, dass er kompiliert:
+ zwei static_casts wegen Typkonvertierung eingeführt (in parse_function)

Hat der VC einen signed vector<...>::size_type ? Ansonsten kann ich mir nicht erklären wieso diese nötig wären.

Ja, hat er.

+ VarManager fehlt in main bei Konstruktion von Env.

Ich glaub du hast den Teil mit Env/FuncEnv nicht verstanden. FuncEnv soll an Funktionen übergeben werden, welche den Inhalt einer Funktion parsen (also lokaler Scope). Env an Funktionen welche sich im globalen Scope befinden.

Okay, das hatte ich echt nicht ganz gerafft. Vllt. noch im Artikel deutlich machen, für blöde wie mich.

+ FuncManager::declare hab' ich mal const gemacht.

Das soll es aber nicht sein. Auf FuncManager::declare soll nur Zugriff haben wer sich im globablen Scope befindet. In Env ist der FuncManager deshalb nicht const und in FuncEnv ist er es.

Gut, okay, das lag dann an meiner falschen Anwendung der Environments, bisher hieß es nämlich:

f:\user files\visual studio 2005\projects\foobar\foobar\main.cpp(273) : error C2662: 'FuncManager::declare' : cannot convert 'this' pointer from 'const FuncManager' to 'FuncManager &' Conversion loses qualifiers

(Zeile 273 ist der Aufruf von FuncManager::declare in parse_function)
Aber dieses Problem hat sich dann ja schlussendlich gelöst, sobald die Envs passten... wollte nur mal gesagt haben, warum ich das geändert hab

+ Beim Aufbau von parse_command war ich mir nicht sicher, wie's aussehen muss

Beim einfügen von parse_while?

Jo, genau, daran lag's. Denkfehler meinerseits.

Der Grund hier ist, dass die letzte Version des Compiler dieses Programm gar nicht übersetzen können soll. Das müsste folgendermaßen aussehen: [...]

Gut, kompiliert den Code sauber.

Soll ich das ganze VC-Projekt mal zippen und dann hochladen? Wäre für die Leser mit Sicherheit nicht schlecht, alles gleich compilerfertig zu haben.

[Ben04]

GPC schrieb:

Ben04 schrieb:

Folgende Änderungen meinerseits, dass er kompiliert:
+ zwei static_casts wegen Typkonvertierung eingeführt (in parse_function)

Hat der VC einen signed vector<...>::size_type ? Ansonsten kann ich mir nicht erklären wieso diese nötig wären.

Ja, hat er.

Es sind aber nur Warnungen die dadurch entstehen oder? Ich finde ein static_cast da ziemlich unschön.

+ VarManager fehlt in main bei Konstruktion von Env.

Ich glaub du hast den Teil mit Env/FuncEnv nicht verstanden. FuncEnv soll an Funktionen übergeben werden, welche den Inhalt einer Funktion parsen (also lokaler Scope). Env an Funktionen welche sich im globalen Scope befinden.

Okay, das hatte ich echt nicht ganz gerafft. Vllt. noch im Artikel deutlich machen, für blöde wie mich.

Ich weiß nicht was ich viel mehr als:

In einem C Programm unterscheidet man zwischen globalen Scope und Funktionskörper. In beiden Bereichen sind unterschiedliche Sprachkonstrukte erlaubt. So kann man zum Beispiel keine Funktion innerhalb einer anderen definieren. Schleifen können sich auch nicht im globalen Scope befinden. Diesen Unterschied wollen wir nun auch in unserer Sprache einführen.

Da wir keine globalen Variablen zulassen kann man sich fragen ob ein VarManager im globalen Scope Sinn macht. Meiner Meinung nach nicht. Deswegen gibt es auch für beide Teile des Programms unterschiedliche Env Strukturen. Die eine nenne ich FuncEnv da sie nur innerhalb einer Funktion Sinn macht und die andere einfach Env. Da wir uns bis jetzt nur um den Inhalt von Funktionen gekümmert haben wird jedes alte Env in ein FuncEnc umbenannt.

schreiben soll.

Soll ich das ganze VC-Projekt mal zippen und dann hochladen? Wäre für die Leser mit Sicherheit nicht schlecht, alles gleich compilerfertig zu haben.

Ich wollte das an sich nicht tun, da die letzte Version nur noch konzeptmäßig etwas mit der ersten zu tun hat. Es wäre wahrscheinlich irreführend wenn sich jemand zuerst den Code anschaut und dann den Artikel durchließt und ich bin mir sicher, dass einige das tun würden. Desweiteren hat man den Code auch verstanden, wenn man alles richtig zusammengepastet hat. Es wäre also eine gute Möglichkeit der Selbstkontrolle.

[GPC]

Ben04 schrieb:

GPC schrieb:

Ben04 schrieb:

Folgende Änderungen meinerseits, dass er kompiliert:
+ zwei static_casts wegen Typkonvertierung eingeführt (in parse_function)

Hat der VC einen signed vector<...>::size_type ? Ansonsten kann ich mir nicht erklären wieso diese nötig wären.

Ja, hat er.

Es sind aber nur Warnungen die dadurch entstehen oder?

Ja, es sind nur Warnungen.

Ich weiß nicht was ich viel mehr als:

In einem C Programm unterscheidet man zwischen globalen Scope und Funktionskörper. In beiden Bereichen sind unterschiedliche Sprachkonstrukte erlaubt. So kann man zum Beispiel keine Funktion innerhalb einer anderen definieren. Schleifen können sich auch nicht im globalen Scope befinden. Diesen Unterschied wollen wir nun auch in unserer Sprache einführen.

Da wir keine globalen Variablen zulassen kann man sich fragen ob ein VarManager im globalen Scope Sinn macht. Meiner Meinung nach nicht. Deswegen gibt es auch für beide Teile des Programms unterschiedliche Env Strukturen. Die eine nenne ich FuncEnv da sie nur innerhalb einer Funktion Sinn macht und die andere einfach Env. Da wir uns bis jetzt nur um den Inhalt von Funktionen gekümmert haben wird jedes alte Env in ein FuncEnc umbenannt.

schreiben soll.

Okay, das muss ich wohl übersehen haben
Mea culpa.

Soll ich das ganze VC-Projekt mal zippen und dann hochladen? Wäre für die Leser mit Sicherheit nicht schlecht, alles gleich compilerfertig zu haben.

Ich wollte das an sich nicht tun, da die letzte Version nur noch konzeptmäßig etwas mit der ersten zu tun hat. Es wäre wahrscheinlich irreführend wenn sich jemand zuerst den Code anschaut und dann den Artikel durchließt und ich bin mir sicher, dass einige das tun würden. Desweiteren hat man den Code auch verstanden, wenn man alles richtig zusammengepastet hat. Es wäre also eine gute Möglichkeit der Selbstkontrolle.

k

[Ben04]

Ich hab jetzt das Inhaltsverzeichnis noch hinzugefügt. Wenn keiner mehr etwas sagt werde ich es bald auf R setzen

[michba]

Hi,
ich bin gerade im Kapitel 9 ("Hello World!") angelangt und habe ein Problem mit dem erzeugten Assemblercode. Und zwar beschwert sich gcc (4.2.1) über .def: "Error: unknown pseudo-op: `.def'".
Ich kenne mich mit Assembler nicht besonders gut aus, aber wenn ich .def mit .globl ersetze, funktioniert es.
Hast du vielleicht eine Erklärung?

[Ben04]

Ich kenne mich da auch nicht sonderlich gut aus. Die Direktiven kenne ich nur vom Code den der GCC selbst erzeugt hat und da macht der:

.globl __Z4progv
	.def	__Z4progv

Welches der Direktiven nun die wichtige ist, hab ich geraten. .def frisst er bei mir und .globl auch. Ich mir jetzt mal die Doku ein bisschen genauer durchgelesen und es scheint, dass .def für Debugsymbole ist. Wahrscheinlich implementiert der MinGW diese als ganz normale Symbole und deswegen gehen bei mir beide.

.globl ist jedenfalls das was laut Doku vorgeschlagen wird. Ich werde es ändern, danke.

[michba]

So, ich habe den Artikel jetzt zu Ende gelesen und er gefällt mir ganz gut.

Am Ende hat sich in read_int noch ein kleiner Fehler eingeschlichen, der zweite Parameter von scanf sollte &r statt %r sein.
Außerdem hätte ich noch den Vorschlag, kurz zu erwähnen, dass man in parse_factor parse_function_call vor parse_literal aufrufen muss, damit der Funktionsname nicht als Variablenbezeichner behandelt wird. An dem Problem bin ich nämlich eine ganze Weile gehangen.

[Ben04]

Ich hab den Fehler beseitig und noch einen kleinen Satz eingefügt welcher auf das Problem mit den Variablenamen hinweist.

[Ben04]

Hab den Artikel auf [R] gesetzt.

[michba]

Ben04, ist es dir wichtig, dass bei der Korrektur kor-Tags gesetzt werden?

[Ben04]

Nein, du kannst die weglassen.

[michba]

Inhaltsverzeichnis

• 1 Einleitung
• 2 Backtracking
• 3 Einfachstes Program
• 4 Immer noch einfach
• 5 Schon etwas komplizierter
• 6 Taschenrechner
• 7 Klammern
• 8 Variablen
• 9 Hello World!
• 10 If und Schleifen
• 11 Funktionen
• 12 Parser Baum
• 13 Schlussbemerkung

1 Einleitung

Programmiersprachen sind eines der zentralsten Themen, mit denen sich Programmierer auseinandersetzen müssen. Trotzdem werden sie von vielen als magische Kiste, entwickelt von Spezialisten angesehen. In der Tat ist es ganz und gar nicht einfach einen guten Compiler zu entwickeln, vor allem sobald Optimierungen ins Spiel kommen. Die Grundlagen sind jedoch gar nicht so schwer. Dieser Artikel soll eine recht praxisnahe Einführung in das Thema Compilerbau darstellen und richtet sich an jeden der C++ kann und Grundkenntnisse in x86-Assemblerprogrammierung hat. Auf theoretische Konstrukte wie Grammatiken wird vereinzelt hingewiesen, jedoch braucht man sie nicht zu kennen, um folgen zu können.

Es muss irgendein GCC installiert sein, um die Beispiele ausführen zu können. Ich werde nämlich dessen Assembler und Linker einsetzen.

2 Backtracking

Bei einem Compiler handelt es sich um ein Programm, das eine Textdatei einliest und dann übersetzt. Es sollte offensichtlich sein, dass das Einlesen der einzelnen Zeichen ein wichtiger Baustein ist. Es muss möglich sein, in der Eingabe zurückzuspulen, da ein Übersetzer oft einfach ein paar Sachen durchprobieren muss, um herauszufinden, was ein gewisser Abschnitt darstellt. Zum Beispiel könnte ein Compiler an einer Stelle eine Logik ähnlich zu folgender anwenden: Wenn es keine Zahl ist dann wird es wohl ein String sein und wenn es dies auch nicht ist, dann handelt es sich um einen Fehler im Programmcode. Wenn es aber keine Zahl ist, so müssen aber alle Zeichen die nötig waren, um festzustellen, dass es keine Zahl ist, erneut interpretiert werden, um festzustellen ob es sich vielleicht um einen String handelt. Bei einer Zahl kann man es bereits beim ersten Buchstaben feststellen, jedoch gibt es auch komplexere Beispiele wo dies nicht so einfach ist. Hier benötigt man irgendeinen Weg, zurückspulen zu können.

Es gibt viele Wege, dies nun zu realisieren. Zum Beispiel kann man Zeichenströme schreiben, welche immer nur das absolute Minimum von Zeichen im Speicher halten. Man muss ja nicht überall hin spulen können. Es reicht an ein paar bekannte Stellen zurück spulen zu können. Dies ermöglicht es selbst wahnsinnig große Quelldateien zu übersetzen und doch nur ein paar Byte Speicher zu benötigen.

In diesem Artikel wollen wir es allerdings nicht zu kompliziert machen und kopieren die Datei kurzerhand in den Speicher. Eine effiziente Implementierung eines Zeichenstroms wäre ein Thema, das in einen anderen Artikel gehört. Unser primitiver Strom wird aus zwei Zeigern bestehen. Einer zeigt auf das Zeichen, welches als nächstes verarbeitet werden soll und der andere auf das erste Zeichen nach dem Ende des Puffers. Es entspricht also einem Iteratorenpaar im Sinn der STL.

Die meisten Funktionen im Übersetzer werden der folgenden ähnlich sehen:

bool foo(..., const char*&pos, const char*end, ...){
	// Do stuff
}

Der erste Zeiger wird per Referenz übergeben, damit auch der Aufrufer weiß, bis wohin gelesen wurde. end dagegen ist immer gleich und muss deswegen nicht per Referenz übergeben werden. Der Rückgabewert gibt an, ob "es" geklappt hat. Was das nun im Detail heißt, hängt natürlich von der Funktion ab.

Da wir im Fehlerfall backtracken müssen und eine Ausnahme einen solchen Fall darstellt, werde ich Scopeguards einsetzen, um den Code ausnahmesicher und lesbar zu halten. Wir werden zwar keine Ausnahmen einsetzen, allerdings sollte man doch dafür sorgen, dass der Code ausnahmefreundlich ist.

class BacktrackGuard{
public:
	explicit BacktrackGuard(const char*&pos):
		pos(pos), start(pos){}

	~BacktrackGuard(){
		if(start)
			pos = start;
	}

	void no_backtrack(){
		start = 0;
	}

private:
	const char*&pos;
	const char*start;

	BacktrackGuard(const BacktrackGuard&);
	BacktrackGuard&operator=(const BacktrackGuard&);
};

In vielen Compilern sind diese Zeichenströme auch dafür verantwortlich, die Position in der Datei zu merken. Das heißt konkret, welche Zeile und das wie vielte Zeichen in dieser. Dies ist zum Beispiel nötig, um sinnvolle Fehlermeldungen ausgeben zu können. Wir werden es uns hier aber einfach machen und dieses Problem einfach ignorieren: Wir geben keine Positionsinformationen mit den Fehlern aus.

3 Einfachstes Program

Um anzufangen wollen wir einen Compiler schreiben, welche nur eine sehr einfache Sprache übersetzen kann, eine die so einfach ist, dass es schon an Spott grenzt, sie als Sprache zu bezeichnen. Ein Programm besteht aus einer einzigen Ziffer und diese muss eine '1' sein. Ein korrektes (und sogar das einzig korrekte) Programm wäre also:

1

Man sollte beachten, dass der Einfachheit zuliebe keine Leerzeichen erlaubt sind.

Das "1" soll bewirken, dass "1" auf der Konsole ausgegeben wird. Der Compiler hierfür sieht wie folgt aus:

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
using namespace std;

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of program"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Auch wenn dieses Programm nicht allzu kompliziert sein dürfte, reicht es aber um die Grundstruktur zu verdeutlichen. Source code wird eingelesen, dann verarbeitet und der Assemblercode wird in eine Datei namens "out.s" geschrieben. Wo etwas fehlschlagen kann und warum, sollte durch die Fehlermeldungen deutlich werden.

Um eine ausführbare Datei zu erzeugen muss "out.s" gegen eine C-Sourcecode-Datei gelinkt werden, welche folgendermaßen aussieht:

#include <stdio.h>

void prog();

int main(){
	prog();
}

void print_int(int n){
	printf("%d", n);
}

Dieser Schnipsel C-Code stellt sozusagen die Laufzeitbibliothek unserer Sprache dar. Darum nenne ich die Datei "rt.c" (steht für runtime). Übersetzen kann man das ganze recht einfach.

gcc out.s rt.c -o out.exe

Manche GCC-Inkarnationen hängen nicht automatisch einen Unterstrich vor C-Funktionsnamen. Wenn die angegebene Kommandozeile einen Linkerfehler produziert, dann wird das wahrscheinlich der Grund sein. Ändern Sie in diesem Fall die Datei "rt.c" zu:

#include <stdio.h>

void _prog();

int main(){
	_prog();
}

void _print_int(int n){
	printf("%d", n);
}

Nun sollte es keine Probleme mehr geben.

4 Immer noch einfach

Man braucht kein Hellseher zu sein, um zu bemerken, dass unsere Sprache noch nicht zu viel zu gebrauchen ist. Dies wird vorerst aber leider auch so bleiben. Zuerst arbeiten wir nämlich an der Syntax unserer Sprache.

Es wäre doch gut, wenn man mehr Freiheiten beim Setzen der Leerzeichen hätten. Hierfür schreiben wir uns eine Funktion, welche Leerzeichen überspringt.

#include <cctype>
//...
void skip_spaces(const char*&pos, const char*end){
	while(pos != end && isspace(*pos))
		++pos;
}

In einem komplexeren Compiler würde diese Funktion auch Kommentare überspringen. Der Rest des Compilers ändert sich nur leicht:

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	skip_spaces(pos, end);		// Ich bin neu (1)
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected at end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		skip_spaces(pos, end);		// Ich auch (2)
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Wozu die erste neue Zeile dient, sollte selbsterklärend sein. Die zweite sorgt dafür, dass Leerzeichen sich auch am Ende des Programms befinden können.

Als nächstes werden wir es möglich machen, die 1 in Buchstaben auszuschreiben. Dazu schreiben wir eine Funktion welche überprüft, ob wir uns vor einem Wort befinden oder nicht. Falls ja wird dieses auch gleich übersprungen.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Nun müssen wir nur noch parse_one anpassen.

void write_print_one_code(std::ostream&out){
	out
		<<"pushl $1"<<endl
		<<"call _print_int"<<endl
		<<"addl $4, %esp"<<endl;
}

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(ignore(pos, end, "1") || ignore(pos, end, "one")){
		write_print_one_code(out);
		return true;
	} else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
}

Wer genau hinschaut, bemerkt, dass sich in parse_one kein skip_spaces mehr befindet. Dadurch, dass wir in ignore einen Aufruf platziert haben, werden beinahe alle anderen überflüssig und damit ist der Code schon viel weniger fehleranfällig und lesbarer.

Und schon können wir Programme wie folgendes übersetzen.

one

Jedoch hat sich bereits der erste Bug eingeschlichen. Betrachten wir mal:

onehundred

Das Programm wird zwar wie erwünscht abgelehnt, aber nicht aus dem richtigen Grund. Der Compiler liest nur bis zum Ende von "one", übersetzt dies dann auch und das Programm wird nur abgelehnt, weil der Compiler nichts mit "hundred" hinter dem Ende des erkannten Programms anzufangen weiß. Das heißt, der Compiler reißt Wörter ohne Gewissensbisse entzwei. Es hängt natürlich von der Sprache ab, ob dies ein Fehler ist oder nicht, allerdings nimmt ein C-Compiler kein "staticintfoo" an, sondern verlangt, dass diese schön mit Leerzeichen getrennt werden. Dies hat auch seinen guten Grund, denn dadurch werden Zweideutigkeiten vermieden. Allerdings übersetzt ein C-Compiler auch "1+2" obwohl zwischen der "1" und dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Operatoren eigene Funktionen schreiben. Die eine würde zusätzlich noch überprüfen, ob sich ein Leerzeichen hinter dem Wort befindet.

Es geht allerdings auch einfach.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			--what;
			if(isalpha(*what))
				if(isalnum(*pos))
					return false;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Streng genommen ist dies zwar ein Hack, aber er macht doch vieles einfacher und angenehmer.

5 Schon etwas komplizierter

So, nun wollen wir auch mal eine Sprache verwenden, welche ansatzweise eine Verwendung hat. Ziel ist es, einen Compiler zu schreiben, der Programme wie folgendes annimmt:

print 1
print 2 print 3
print 4 print 
5

Das Programm besteht aus einer Reihe von "print" Befehlen, welche jeweils eine positive Ganzzahl ausgeben.

Als erstes ersetzen wir parse_one (und auch den Aufruf in main) durch folgende Funktion:

bool parse_program(const char*&pos, const char*end, ostream&out){
	while(parse_command(pos, end, out))
		{}
	return true;
}

Wie bereits erwähnt, besteht ein Programm aus einer Reihe von Befehlen und darum sollte die Funktion, die ein Programm liest, auch nur dies tun. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtlich und verständlich.

Um das Lesen eines Befehls kümmert sich die Funktion parse_command, welche dann wieder auf eine Reihe von Unterfunktionen zurückgreift.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		int n;
		if(read_number(pos, end, n)){
			out
				<<"pushl $"<<n<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

bool read_number(const char*&pos, const char*end, int&n){
	skip_spaces(pos, end);
	if(pos != end && isdigit(*pos)){
		n = 0;
		do{
			n *= 10;
			n += *pos - '0';
			++pos;
		}while(pos != end && isdigit(*pos));
		return true;
	}else
		return false;
}

read_number könnte man nun natürlich auch das Lesen von Hexadezimal- oder Oktalzahlen beibringen. Wir wollen uns aber mit einfachen Dezimalzahlen begnügen, um nicht den Rahmen zu sprengen.

In welche und wie viele Unterfunktionen man aufbrechen soll, hängt von der eigenen Erfahrung ab. Hier kann ich höchstens als Faustregel angeben, dass man alles auslagern soll, für was man einen passenden Funktionsnamen findet.

6 Taschenrechner

Als nächstes nehmen wir uns vor, komplexere Ausdrücke zu unterstützen. Also zum Beispiel folgendes Programm.

print 1+1
print 5*8
print 4 + 8*7

Jeder, der mit dem Überladen von Operatoren in C++ vertraut ist, der weiß, dass man Operatoren auch als Funktionsaufrufe ansehen kann. Den Code oben könnte man auch wie folgend umschreiben.

print add(1, 1)
print mul(5, 8)
print add(4, mul(8, 7))

Auf diese Weise wollen wir unsere Operatoren auch umsetzen, als inline-Minifunktionen. Wer schon einmal x86-Assembler geschrieben hat, der weiß, dass man das Register eax für Rückgabewerte nutzt. Dies wollen wir auch hier tun. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumente nacheinander aus und nutzt den Stack um Werte zwischenzuspeichern.

Allerdings, bevor wir uns um die Generierung des Assemblercodes kümmern, müssen wir zuerst dafür sorgen, dass wir den Ausdruck richtig lesen können. Hier hilft es, sich eine Reihe von Fragen zu stellen:

Woraus besteht ein Program? Aus Befehlen
Woraus besteht ein Befehl? Aus "print" gefolgt von einem Ausdruck
Woraus besteht ein Ausdruck? Aus einer Summe oder Differenz von Termen
Woraus besteht ein Term? Aus einem Produkt, Quotient oder Modulo von Faktoren
Woraus besteht ein Faktor? Aus einer Zahl mit vielleicht einem Vorzeichen

Wer sich für den theoretischen Hintergrund dieser Fragen interessiert, der kann mal nach EBNF suchen. In diesem Artikel werde ich aber nicht weiter darauf eingehen.

Nun wissen wir schon, welche Funktionen gebraucht werden. Einige der Funktionen sind bereits implementiert und darum werde ich sie nicht wiederholen.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

Diese Funktion sollte selbsterklärend sein.

bool parse_expression(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_term(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "+")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after +"<<endl;
					return false;
				}
				out
					<<"addl (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "-")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after -"<<endl;
					return false;
				}
				out
					<<"subl %eax, (%esp)"<<endl
					<<"pop %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Diese Funktion sieht auf den ersten Blick bedrohlich aus, allerdings ist sie an sich recht einfach. Die einzelnen Terme der Summe werden nacheinander ausgewertet und zusammengezählt beziehungsweise voneinander abgezogen.

Die Multiplikation wird ähnlich behandelt.

bool parse_term(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_factor(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "*")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after *"<<endl;
					return false;
				}
				out
					<<"imull (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "/")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl;
			}else if(ignore(pos, end, "%")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl
					<<"movl %edx, %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Die Funktion, um Faktoren auszuwerten, ist recht einfach, da ein Faktor nur aus einer Zahl bestehen kann.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	int n;
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

7 Klammern

Als nächstes wollen wir geklammerte Ausdrücke unterstützen. Fragen wir uns erneut, woraus ein Faktor bestehen kann. Wirklich nur aus einer Zahl? Nein, unter Umständen auch aus einem geklammerten Ausdruck. Ein Ausdruck besteht - über Umwege - aber wieder aus einem Faktor. Es mag auf den ersten Blick nicht offensichtlich sein, allerdings stellen solche rekursiven Definitionen an sich kein Problem dar. Man muss die entsprechende Funktion lediglich rekursiv aufrufen.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	int n;
	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else if(ignore(pos, end, "(")){
		parse_expression(pos, end, out);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

8 Variablen

Das nächste, was jeder Compiler beherrschen sollte, sind Variablen. Wir wollen uns hier auf lokale Variablen beschränken. Das heißt, alle werden auf den Stack gepackt und keine kommen in statischen Speicher. Um die Sache noch weiter zu vereinfachen, sind alle Variablen vom Typ int. Dies ist eine ziemlich starke Einschränkung, aber irgendwo muss ich ja streichen damit dieser Artikel nicht zu groß wird.

Das erste was benötigt wird, ist eine Datenstruktur welche die Variablen verwaltet. Hierfür definiere ich eine Klasse.

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
};

Auf die Implementierungsdetails werde ich nicht eingehen. Eine fertige Implementierung findet man hier.

Es soll möglich sein, in höheren Scopes Variablen zu definieren, welche Variablen aus den unteren Scopes verdecken. Dieses Verhalten ist natürlich sprachabhängig allerdings wollen wir uns hier einfach an die C-Regeln halten. Mit ihnen dürfte jeder Leser vertraut sein.

• create_var erzeugt eine Variable im obersten Scope mit einem gewissen Namen. Falls es bereits eine solche Variable gibt, so wird false zurückgegeben, andernfalls wird true zurückgegeben.
• Mit is_var_defined kann man ermitteln, ob es eine Variable bereits gibt oder nicht. Hier sollte darauf hingewiesen werden, dass diese Funktion nichts über die Erfolgsaussichten von create_var aussagt, da Variablen verdeckt werden können.
• get_var_address gibt die Stackadresse der Variable aus. Adressen werden von ebp aus gezählt. Wir müssen also auch die main Funktion anpassen damit ebp einen brauchbaren Wert enthält.
• push_scope sollte aufgerufen werden, wenn sich der Compiler in einen neuen Scope begibt.
• Beim Verlassen eines Scopes sollte pop_scope aufgerufen werden. Alle Variablen dieses Scopes werden zerstört.

Der out-Parameter ist der Zeichenstrom der den Assemblercode ausgibt. Methoden mit ihm können Code generieren.

Nun müssen wir noch dafür sorgen, dass VarManager überall zugänglich ist. Eine Möglichkeit wäre, eine Instanz global anzulegen oder ein Singleton zu basteln. Dies ist aber nicht wirklich die feine Art und führt zu Problemen, sobald man den Code parallelisieren möchte. Eine andere Möglichkeit ist eine Instanz in main anzulegen und dann eine Referenz auf diese von Funktion zu Funktion weiter zu geben. Diese Lösung ist viel flexibler, allerdings sind Variablen nicht das einzige, was verwaltet werden will.

Wer sich ein bisschen mit Schleifen auskennt, der weiß, dass dort Sprungadressen verwaltet werden müssen. Wenn man Variablen in Register packen will, so müssen diese auch verwaltet werden. Wenn wir jetzt auf alles eine Referenz übergeben, dann verlieren wir uns bald in endlosen Parameterlisten. Ein noch viel schlimmeres Problem ist, dass man keine neue Struktur einführen kann ohne den ganzen Code umzubauen.

Die Lösung ist recht einfach. Man baut eine Hilfsstruktur, welche diese Referenzen verwaltet. Dies sieht dann etwa folgendermaßen aus:

class Env{
public:
	explicit Env(VarManager&var):
		var(var){}

	VarManager&var;
};

Eine Referenz auf diese Klasse wird dann von Funktion zu Funktion übergeben. Wenn eine neue Verwaltungsstruktur hinzugefügt wird, so braucht man nur Env und main zu verändern. Der gewählte Name steht für Environment. Als Environment verstehe ich die Zusammenfassung aller Verwaltungsstrukturen.

Man kann die Ausgabe auch als Teil von Env ansehen.

class Env{
public:
	explicit Env(VarManager&var, ostream&out):
		var(var), out(out){}

	VarManager&var;
	ostream&out;
};

Die main-Funktion wird also wie folgend abgeändert:

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	Env env(var, out);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
	}
}

parse_command muss nun auch geändert werden, da unsere Sprache ja nun zusammengesetzte Befehle mittels Scopes unterstützt. Wir werden hier wie in C Akkoladen verwenden um Scopes zu begrenzen. Um die Funktion klein zu halten, lagere ich Teile der Funktion in eine neue Funktion namens parse_block aus.

bool parse_block(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "{")){
		env.var.push_scope();

		while(parse_block(env, pos, end))
			{}

		if(ignore(pos, end, "}")){
			env.var.pop_scope(env.out);
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Missing }"<<endl;
			return false;
		}
	}else{
		guard.no_backtrack();
		return parse_command(env, pos, end);
	}
}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

parse_program können wir dann auch abändern, da mehrere Befehle durch die Benutzung von Akkoladen möglich sind.

bool parse_program(Env&env, const char*&pos, const char*end){
	return parse_block(env, pos, end);
}

Nun ist es möglich, Programme wie folgendes zu übersetzen.

{
	print 1
	print 2
	{
		print 3
		{}
	}
	print 4
}

Die äußeren Akkoladen sind nötig.

Auch wenn das schon nicht schlecht aussieht, haben wir doch einen wesentlichen Bestandteil vergessen. Es gibt noch keine Variablen!

Zuerst brauchen wir eine Funktion, die Namen von Variablen liest.

bool read_identifier(const char*&pos, const char*end, string&identifier){
	skip_spaces(pos, end);
	if(pos != end && (isalpha(*pos) || *pos == '_')){
		identifier = "";
		do{
			identifier += *pos;
			++pos;
		}while(pos != end && (isalnum(*pos) || *pos == '_'));
		return true;
	}else
		return false;
}

Das nächste, was wir brauchen, ist ein Befehl, um Variablen zu erschaffen und einen weiteren, um ihnen etwas zuzuweisen.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Argument to print is missing"<<endl;
			return false;
		}
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;

	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Jetzt brauchen wir nur noch eine Möglichkeit, lesend auf eine Variable zuzugreifen. Dazu verändere ich parse_factor. Hier lagere ich auch wieder einen Teil der Funktion aus.

bool parse_literal(Env&env, const char*&pos, const char*end){
	int n;
	if(read_number(pos, end, n)){
		env.out<<"movl $"<<n<<", %eax"<<endl;
		return true;
	}
	string identifier;
	if(read_identifier(pos, end, identifier)){
		if(env.var.is_var_defined(identifier)){
			env.out<<"movl "<<env.var.get_var_address(identifier)<<", %eax"<<endl;
			return true;
		}else{
			cerr<<"Undefined variable "<<identifier<<endl;
			return false;
		}
	}

	return false;
}

bool parse_factor(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(parse_literal(env, pos, end)){

	}else if(ignore(pos, end, "(")){
		parse_expression(env, pos, end);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		env.out<<"negl %eax"<<endl;

	guard.no_backtrack();
	return true;
}

Langsam aber sicher entwickelt sich unsere Sprache weiter. Ein Programm sieht jetzt schon aus, als könnte es für irgendetwas zu gebrauchen sein.

{
	var a
	var b
	a = 5
	b = a + 5
	{
		a = a-1
		var c
		c = b
		print c
	}
	print a+b
}

9 Hello World!

Im vorherigen Kapitel habe ich gesagt, alle Variablen wären vom Typ int. Daran werde ich jetzt auch nichts ändern, allerdings benötigt jede Sprache wenigstens eine minimale Unterstützung für Strings. Ohne kann man noch nicht einmal ordentliche Beispielprogramme schreiben. Noch nicht einmal ein "Hello world!"-Programm ist möglich.

Ziel dieses Kapitels ist es, den print-Befehl ein wenig aufzumotzen. Er soll auch Stringliterale als Parameter übernehmen können und mehrere durch Kommas getrennte Parameter sollen auch unterstützt werden. Er wird aber einzigartig bleiben in dem Sinn, dass nur er Strings als Argument nehmen kann.

Als erstes benötigen wir eine Funktion, welche Stringliterale parsen kann.

char unescape_character(char c){
	switch(c){
		case 'n':return '\n';
		case 't':return '\t';
		case '\\':return '\\';
		case '\"':return '\"';
	}
	cerr<<"Unknown escape sequence \\"<<c<<endl;
	return c;
}

bool read_string(const char*&pos, const char*end, string&str){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);
	if(pos != end && *pos == '"'){
		++pos;
		str = "";
		do{
			if(*pos == '\\'){
				++pos;
				if(pos == end){
					cerr<<"EOF in string literal"<<endl;
					return false;
				}
				str += unescape_character(*pos);
			}else
				str += *pos;
			++pos;
		}while(pos != end && *pos != '\"');
		++pos;
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Als nächstes brauchen wir eine Möglichkeit, Zeichenketten in den Code einzufügen. Diese werden wir in einer Data-Sektion unterbringen. Wir brauchen also eine weitere Klasse, welche die Stringliterale verwaltet.

class DataSection{
public:
	void add_string_data(string label, string data);
	void write_data_section(ostream&);
};

Auch hier werde ich auf eine fertige Implementierung verweisen. Es gibt den offensichtlichen Weg, diese Klasse zu implementieren oder man kann versuchen, ein paar Bytes zu sparen, indem man versucht, die Strings so anzuordnen, dass sie sich überlappen. Dies geht natürlich nur, solange die originalen Zeichenketten in der Data-Sektion nicht verändert werden dürfen.

• Mit add_string_data kann man einen String ablegen. Es wird ein Nullbyte angefügt und Label wird so gesetzt, dass es auf das erste Byte zeigt.
• write_data_section macht das, was der Name sagt.

Da DataSection ein Label braucht, brauchen wir auch jemanden, der diese verwaltet.

class LabelManager{
public:
	string make_unique();
};

• make_unique erzeugt einen eindeutigen Labenamen und gibt diesen zurück.

Die Implementierung gibt es hier.

main und Env müssen auch angepasst werden:

class Env{
public:
	explicit Env(VarManager&var, ostream&out, DataSection&data, LabelManager&label):
		var(var), out(out), data(data), label(label){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
};

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	DataSection data;
	LabelManager label;
	Env env(var, out, data, label);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else{
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl
				<<".data"<<endl;
			data.write_data_section(out);
		}
	}
}

Schlussendlich muss auch noch "rt.c" angepasst werden, damit Zeichenketten ausgegeben werden können.

#include <string.h>

void print_string(const char*str){
	fwrite(str, 1, strlen(str), stdout);
}

printf will ich nicht benutzen, da man bei dieser Funktion auf Prozentzeichen achten muss. Durch die Benutzung von fwrite gehe ich allen möglichen Problemen aus dem Weg, selbst denen die durch Printf-Format-Erweiterungen entstehen könnten.

Da der print-Befehl komplizierter geworden ist, lagere ich ihn aus.

bool parse_print(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		do{
			string str;
			if(read_string(pos, end, str)){
				string label = env.label.make_unique();
				env.data.add_string_data(label, str);
				env.out
					<<"pushl $"<<label<<endl
					<<"call _print_string"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(parse_expression(env, pos, end)){
				env.out
					<<"pushl %eax"<<endl
					<<"call _print_int"<<endl
					<<"addl $4, %esp"<<endl;
			}else{
				cerr<<"Argument to print is missing"<<endl;
				return false;
			}
		}while(ignore(pos, end, ","));
		guard.no_backtrack();
		return true;
	}else
		return false;

}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;
	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Nun endlich können wir ein "Hello world"-Programm schreiben.

{
	print "Hello" , " world!\n"
	var a
	var b
	a = 3
	b = 5
	print a, " + ", b, " = ", a+b
}

10 If und Schleifen

Was jetzt noch fehlt, sind Abfragen und Schleifen. Diese sind auch nicht sonderlich schwer. Zuerst benötigen wir eine Funktion, um ein if einzulesen. Der Einfachheit halber werden wir nicht versuchen, die Werte im Statusregister zu halten und wenn möglich wiederzuverwenden. If nutzt einfach wie überall eax und nimmt natürlich auch ein int als Bedingung. Dies ist recht ineffizient, allerdings macht es die Sache doch wesentlich einfacher.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string label = env.label.make_unique();
		if(parse_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<label<<endl;
			if(parse_block(env, pos, end)){
				env.out<<label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

So, nun muss nur noch parse_command leicht angepasst werden.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(parse_if(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else 
		...
}

An sich war es das schon, allerdings ist ein Vergleich, ob denn nun zwei Werte gleich sind, noch ziemlich haarig.

{
	var a
	var b
	a = 4
	b = 3
	if a - b
		print "nicht gleich"
}

Deswegen muss parse_expression verändert werden. Als erste nenne ich parse_expression in parse_numeric_expression um und schreibe ein paar weitere Funktionen. Diese kümmern sich um das Einlesen der Vergleichsoperatoren und der logischen Verknüpfungen. Dadurch werden die Funktionen nicht endlos lang.

bool parse_compare_expression(Env&env, const char*&pos, const char*end){
	if(ignore(pos, end, "true")){
		env.out<<"movl $1, %eax"<<endl;
		return true;
	}else if(ignore(pos, end, "false")){
		env.out<<"movl $0, %eax"<<endl;
		return true;
	}else if(parse_numeric_expression(env, pos, end)){
		BacktrackGuard guard(pos);
		string condition_code;
		if(ignore(pos, end, "="))
			condition_code = "e";
		else if(ignore(pos, end, "!="))
			condition_code = "ne";
		else if(ignore(pos, end, "<="))
			condition_code = "be";
		else if(ignore(pos, end, ">="))
			condition_code = "ae";
		else if(ignore(pos, end, "<"))
			condition_code = "b";
		else if(ignore(pos, end, ">"))
			condition_code = "a";
		else
			cerr<<"Unknown compare operator"<<endl;
		env.out<<"pushl %eax"<<endl;
		if(parse_numeric_expression(env, pos, end)){
			env.out
				<<"cmpl %eax, (%esp)"<<endl
				<<"movl $0, %eax"<<endl
				<<"set"<<condition_code<<" %al"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

bool parse_boolean_expression(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool not_operation = false;
	if(ignore(pos, end, "!"))
		not_operation = true;
	if(parse_compare_expression(env, pos, end)){
		for(;;){
			string operation;
			if(ignore(pos, end, "&"))
				operation = "and";
			else if(ignore(pos, end, "|"))
				operation = "or";
			else if(ignore(pos, end, "^"))
				operation = "xor";
			else{
				if(not_operation)
					env.out<<"notl %eax"<<endl;
				guard.no_backtrack();
				return true;
			}
			env.out<<"pushl %eax"<<endl;
			if(!parse_compare_expression(env, pos, end))
				return false;
			env.out
				<<operation<<" %eax, (%esp)"<<endl
				<<"addl $4, %esp"<<endl;
		}
	}
	return false;
}

Man sollte beachten, dass die Reihenfolge der Abfragen in parse_compare_expression nicht egal ist. Wenn mehrere Operatoren mit dem gleichen Zeichen anfangen, so muss man zuerst auf den längsten testen, ansonsten wird der Operator entzweigerissen. Aus "<=" würde ein "<", gefolgt von einem "=" und dies würde zu einem Fehler führen.

In parse_if wird natürlich parse_boolean_expression verwendet und nicht parse_numeric_expression. Dadurch ist die doppelte Bedeutung von "=" auch nicht zweideutig. Aus dem Kontext heraus kann bestimmt werden, ob es ein Vergleich oder eine Zuweisung sein soll.

Nun fehlt nur noch ein else. Dafür müssen wir parse_if anpassen.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string false_label = env.label.make_unique();
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<false_label<<endl;
			if(parse_block(env, pos, end)){
				if(!ignore(pos, end, "else")){
					env.out<<false_label<<":"<<endl;
					guard.no_backtrack();
					return true;
				}
				string end_label = env.label.make_unique();
				env.out
					<<"jmp "<<end_label<<endl
					<<false_label<<":"<<endl;
				if(!parse_block(env, pos, end))
					return false;
				env.out<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Schleifen sind auch nicht sonderlich verschieden von einem if. Als erstes schreibe ich eine parse_while-Funktion und die wird dann in parse_command genauso wie parse_if aufgerufen.

bool parse_while(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "while")){
		string 
			reloop_label = env.label.make_unique(),
			end_label = env.label.make_unique();
		env.out<<reloop_label<<":"<<endl;
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<end_label<<endl;
			if(parse_block(env, pos, end)){
				env.out
					<<"jmp "<<reloop_label<<endl
					<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Nun ist unser Compiler schon fähig, sinnvolle Programme zu übersetzen. Folgendes Programm zählt von 0 bis 10:

{
	var i
	i = 0
	while i<=10{
		print i, "\n"
		i = i+1
	}
}

Hier ist zum Beispiel ein Programm, das alle Primzahlen bis 100 sucht:

{
	print "Between 1 and 100 the following prime numbers exist : 2"
	var p
	p = 3
	while p < 100{
		var d 
		d = 2
		var is_prime
		is_prime = 1
		while d<p{
			if p%d = 0{
				is_prime = 0
			}
			d = d+1
		}
		if is_prime != 0{
			print ", ", p
		}
		p = p+1
	}
}

Aufmerksamen Lesern fällt wahrscheinlich auf, dass ich is_prime nicht mit true initialisiere. Nun, dies liegt daran, dass dies kein numerischer Wert ist. Diese strikte Unterscheidung zwischen boolschem und numerischem Wert ermöglicht aber auch, ein einfaches Gleichzeichen sowohl für eine Zuweisung als auch für einen Vergleich zu nehmen. Es hat also sowohl Vor- wie auch Nachteile. In einer kompletten Sprache gäbe es natürlich auch einen boolschen Typ und dadurch wäre das Problem elegant gelöst.

Eine for-Schleife ist nicht signifikant anders und ihre Implementierung wird dem Leser überlassen.

11 Funktionen

Funktionen sind die Bausteine jedes komplexeren Programms. Darum will ich sie auch in diesem Artikel nicht auslassen. Mit Funktionen kann man sich, was die Komplexität angeht, beliebig nach oben steigern. Templatefunktionen sind ein gutes Beispiel dafür. Hier will ich mich aber auf recht einfache Funktionen beschränken. Für jede Funktion speichern wir den Namen und die Anzahl der Parameter. Da es nur int als Variablentyp gibt, brauchen wir keine Informationen über die Typen der Parameter zu speichern. Der Rückgabewert ist auch immer ein int. Funktionen ohne Rückgabetyp machen natürlich Sinn, aber das machen Templatefunktionen auch. Als Kompromiss zwischen Sinn und Einfachheit lassen wir es zu, dass ein Rückgabewert nicht initialisiert ist. Das heißt er enthält Schrott.

Funktionen müssen wie in C im Voraus deklariert werden und können mehrfach gleich deklariert werden. Sie können nicht überladen werden. Als Aufrufskonvention werden wir eine verwenden, die der des GCCs ähnlich ist. Dadurch können wir auch ohne weiteres gegen C-Code linken. Der Unterschied besteht darin, dass Argumente von links nach rechts auf den Stack gepackt werden. Beim GCC werden die Parameter von rechts nach links auf den Stack gepackt. Der Grund hierfür ist, dass es so für uns einfacher ist. Der Aufrufer ist dafür verantwortlich, die Argumente wieder vom Stack zu nehmen. Eine Funktion darf ihre Parameter verändern. Der Aufrufer darf also keine Argumente recyceln. Der Rückgabewert befindet sich in eax.

Als erstes brauchen wir eine Klasse, um die Informationen zu verwalten. Ich werde wieder einmal nur auf die Klassenschnittstelle eingehen und auf eine Implementierung verweisen.

class FuncManager{
public:
	bool declare(string name, unsigned parameter_count);
	bool exists(string name)const;
	string get_label(string name)const;
	unsigned get_parameter_count(string name)const;
};

• declare macht eine Funktion bekannt.
• exists überprüft, ob eine Funktion bekannt gemacht wurde.
• get_label gibt das Label des Funktionskörper zurück.
• Mit get_parameter_count findet man heraus, wie viele Parameter eine Funktion braucht.

Um auf Argumente zurückgreifen zu können und Werte zurückgeben zu können, müssen wir auch VarManager verändern. Konkret werden ein paar Methoden hinzugefügt und die Klasse sieht nun folgendermaßen aus:

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool add_arg(string name, unsigned pos);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
	void simulate_pop_all_scopes(ostream&out)const;
};

• add_arg gibt einem Parameter einen Namen. pos gibt an, um das wie vielte Argument von links es sich handelt. Das erste Argument hat den Index 0. Der Rückgabewert gibt an, ob es bereits einen solchen Parameter gab oder nicht. Argumente werden in ihrem eigenen Scope angelegt und darum können sie mit gleichnamigen lokalen Variablen koexistieren. Sie werden jedoch von denen verdeckt.
• simulate_pop_all_scopes generiert Code, um alle Scopes zu löschen, ohne dies jedoch zu tun. Dies wird benötigt, um ein return wie in C zu realisieren. Für andere Formen von Sprüngen, wie zum Beispiel break, würde man einen ähnlichen Mechanismus benötigen.

Eine Implementierung gibt es hier.

In einem C-Programm unterscheidet man zwischen globalem Scope und Funktionskörper. In beiden Bereichen sind unterschiedliche Sprachkonstrukte erlaubt. So kann man zum Beispiel keine Funktion innerhalb einer anderen definieren. Schleifen können sich auch nicht im globalen Scope befinden. Diesen Unterschied wollen wir nun auch in unserer Sprache einführen.

Da wir keine globalen Variablen zulassen, kann man sich fragen, ob ein VarManager im globalen Scope Sinn macht. Meiner Meinung nach nicht. Deswegen gibt es auch für beide Teile des Programms unterschiedliche Env-Strukturen. Die eine nenne ich FuncEnv, da sie nur innerhalb einer Funktion Sinn macht und die andere einfach Env. Da wir uns bis jetzt nur um den Inhalt von Funktionen gekümmert haben, wird jedes alte Env in ein FuncEnv umbenannt.

struct FuncEnv{
	explicit FuncEnv(VarManager&var, ostream&out, DataSection&data, LabelManager&label, const FuncManager&func):
		var(var), out(out), data(data), label(label), func(func){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
	const FuncManager&func;
};

struct Env{
	explicit Env(ostream&out, DataSection&data, LabelManager&label, FuncManager&func):
		out(out), data(data), label(label), func(func){}

	ostream&out;
	DataSection&data;
	LabelManager&label;
	FuncManager&func;
};

Der FuncManager in FuncEnv ist konstant, da man keine Funktion innerhalb einer anderen erschaffen kann. In main wird eine Instanz von FuncManager angelegt wie wir es bereits für die meisten anderen Verwaltungsstrukturen gemacht haben.

Als nächstes brauchen wir eine Funktion zum Einlesen von Funktionsdefinitionen und Deklarationen.

bool read_arg_list(const char*&pos, const char*end, vector<string>&args){
	BacktrackGuard guard(pos);
	if(!ignore(pos, end, "("))
		return false;
	string arg_name;
	while(read_identifier(pos, end, arg_name)){
		args.push_back(arg_name);
		if(!ignore(pos, end, ","))
			break;
	}
	if(!ignore(pos, end, ")"))
		return false;
	guard.no_backtrack();
	return true;
}

bool parse_function(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;

	vector<string>arguments;
	if(!read_arg_list(pos, end, arguments))
		return false;

	if(env.func.exists(func_name)){
		if(env.func.get_parameter_count(func_name) != arguments.size())
			cerr<<"Function "<<func_name<<" redeclared with wrong argument number"<<endl;
	}else
		env.func.declare(func_name, arguments.size());

	if(ignore(pos, end, ";")){
		guard.no_backtrack();
		return true;
	}

	VarManager var;

	for(unsigned j=0; j<arguments.size(); ++j)
		if(!var.add_arg(arguments[j], arguments.size()-j-1))
			cerr<<"2 arguments with same name "<<arguments[j]<<" in function "<<func_name<<endl;

	env.out
		<<".globl "<<env.func.get_label(func_name)<<endl
		<<env.func.get_label(func_name)<<":"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;
	;

	FuncEnv fenv(var, env.out, env.data, env.label, env.func);
	if(parse_block(fenv, pos, end)){
		env.out
			<<"pop %ebp"<<endl
			<<"ret"<<endl;
		guard.no_backtrack();
		return true;
	}

	return false;
}

Als nächstes sorgen wir dafür, dass eine Funktion auch aufgerufen werden kann. Dafür schreiben wir uns als erstes eine Funktion, die einen Aufruf einliest.

bool parse_function_call(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;
	else{
		if(ignore(pos, end, "(")){
			unsigned parameter_count = 0;
			if(!ignore(pos, end, ")")){
				do{
					if(!parse_numeric_expression(env, pos, end))
						return false;
					env.out<<"pushl %eax"<<endl;
					++parameter_count;
				}while(ignore(pos, end, ","));
				if(!ignore(pos, end, ")"))
					return false;
			}

			if(!env.func.exists(func_name))
				cerr<<"Unknown function "<<func_name<<endl;
			else if(env.func.get_parameter_count(func_name) != parameter_count)
				cerr<<"Wrong number of parameters to function "<<func_name<<endl;
			else{
				env.out<<"call "<<env.func.get_label(func_name)<<endl;
				if(parameter_count != 0)
					env.out<<"addl $"<<4*parameter_count<<", %esp"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
		return false;
	}
}

Eine Funktion kann innerhalb eines Ausdrucks und eines Befehls aufgerufen. Es müssen also parse_factor und parse_command verändert werden. In parse_factor muss man parse_function_call vor parse_literal aufrufen, da ansonsten der Funktionsname als Variable interpretiert wird.

Nun fehlt nur noch die Möglichkeit, einen Wert zurückzugeben. Die Funktion, die sich darum kümmert, sollte nicht zu kompliziert sein, wenn man es geschafft hat, bis hier zu folgen.

bool parse_return(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	if(ignore(pos, end, "return")){
		if(parse_numeric_expression(env, pos, end)){
			env.var.simulate_pop_all_scopes(env.out);
			env.out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Diese Funktion wird nun noch in parse_command aufgerufen und schon können wir Funktionen übersetzen.

Nun müssen wir nur noch parse_program und main anpassen.

bool parse_program(Env&env, const char*&pos, const char*end){
	while(parse_function(env, pos, end))
	{}

	return true;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out<<".text"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	DataSection data;
	LabelManager label;
	FuncManager func;
	Env env(out, data, label, func);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			data.write_data_section(out);
	}
}

Ein "Hello World"-Programm sieht nun wie folgend aus:

prog(){
	print "Hello World!"
}

Selbst rekursive Funktionen sind kein Problem. Folgendes Programm berechnet die Fakultät einer Zahl rekursiv:

fact(n){
	if n = 0
		return 1
	else
		return n*fact(n-1)
}

prog(){
	print fact(9)
}

Wir können aber nun auch gegen C-Funktionen linken. Zum Beispiel kann man so etwas von der Konsole einlesen.

int read_int(){
	int r = -1;
	scanf("%d", &r);
	return r;
}

read_int();

prog(){
	var a
	print "a = "
	a = read_int()
	var b
	print "b = "
	b = read_int()
	print "a + b = ", a+b
	print "a - b = ", a-b
	print "a * b = ", a*b
	print "a / b = ", a/b
	print "a % b = ", a%b

}

Man muss nur beachten, dass die Parameter in C eine andere Reihenfolge haben werden. Die Funktion test(a,b,c) würde der C-Funktion test(c,b,a) entsprechen.

12 Parserbaum

Wer schon einmal vorher mit der Materie in Kontakt gekommen ist, wird sich wahrscheinlich wundern, warum ich ihn bis jetzt noch nicht erwähnt habe, ja vielleicht sogar wundern, wie wir überhaupt so weit ohne ihn gekommen sind. Die Rede ist vom Parserbaum.

Die Idee ist es, das Interpretieren der Eingangszeichenkette und das Generieren der Assemblercodes zu trennen. Diese Trennung bietet viele Vorteile, wobei die Möglichkeit, elegant mehrere Prozessoren zu unterstützen nur die offensichtlichste ist.

Der Parser liest den Code und generiert einen Baum, welcher alle wichtigen Informationen enthält. Der Generator nimmt diesen Baum dann und generiert den entsprechenden Code. Dies macht Arbeitsteilung im Entwicklerteam viel einfacher, da beide Teile nun unabhängig voneinander sind.

Ein weiterer großer Vorteil ist, dass es möglich wird, Funktionen zu inlinen und auch andere Optimierungen durchzuführen. Ich wüsste nicht, wie man dem Compiler, so wie er hier vorgestellt wurde, beibringen soll, Funktionsaufrufe zu ersetzen. Wenn man den Code allerdings als Baum vorliegen hat, so muss man nur einen Ast des Baums kopieren und noch ein paar Umformungen bezüglich der Variabelnamen durchführen. In einem Baum ist es auch leicht, Informationen über Unterausdrücke einzuholen. Zum Beispiel, ob ein Ausdruck noch etwas anderes tut außer den Rückgabewert zu berechnen. Dies ist wichtig um zum Beispiel 0*x durch 0 zu ersetzen.

In diesem Artikel wollen wir aber keinen Parserbaum mehr entwickeln. Es würde einfach den Rahmen sprengen.

13 Schlussbemerkung

Ziel dieses Artikels war es, den Leser in das Gebiet des Compilerbaus einzuführen und zwar ohne ihn mit Theorie zu bombardieren. Ich hoffe, Sie haben jetzt einen Überblick über die Materie und können sich vorstellen, wo man die Aussagen der Theorie praktisch einsetzen kann. Wer sich für das Thema interessiert, dem sei gesagt, dass es sich hier nur um die Spitze des Eisbergs handelt. Es gibt noch sehr viel, was in diesem Artikel noch nicht einmal mit einem Wort erwähnt wurde.

Ob es von meiner Seite einen weiteren Artikel zu diesem Thema geben wird, ist ungewiss. Es fällt mir schwer, einzuschätzen, ob ich in Zukunft noch genug Zeit und Motivation aufbringen kann. Natürlich hängt es auch davon ab, wie viele Leute sich dafür interessieren.

[Ben04]

Inhaltsverzeichnis

• 1 Einleitung
• 2 Backtracking
• 3 Einfachstes Program
• 4 Immer noch einfach
• 5 Schon etwas komplizierter
• 6 Taschenrechner
• 7 Klammern
• 8 Variablen
• 9 Hello World!
• 10 If und Schleifen
• 11 Funktionen
• 12 Parser Baum
• 13 Schlussbemerkung

1 Einleitung

Programmiersprachen sind eines der zentralsten Themen, mit denen sich Programmierer auseinandersetzen müssen. Trotzdem werden sie von vielen als magische Kiste, entwickelt von Spezialisten angesehen. In der Tat ist es ganz und gar nicht einfach einen guten Compiler zu entwickeln, vor allem sobald Optimierungen ins Spiel kommen. Die Grundlagen sind jedoch gar nicht so schwer. Dieser Artikel soll eine recht praxisnahe Einführung in das Thema Compilerbau darstellen und richtet sich an jeden der C++ kann und Grundkenntnisse in x86-Assemblerprogrammierung hat. Auf theoretische Konstrukte wie Grammatiken wird vereinzelt hingewiesen, jedoch braucht man sie nicht zu kennen, um folgen zu können.

Es muss irgendein GCC installiert sein, um die Beispiele ausführen zu können. Ich werde nämlich dessen Assembler und Linker einsetzen.

2 Backtracking

Bei einem Compiler handelt es sich um ein Programm, das eine Textdatei einliest und dann übersetzt. Es sollte offensichtlich sein, dass das Einlesen der einzelnen Zeichen ein wichtiger Baustein ist. Es muss möglich sein, in der Eingabe zurückzuspulen, da ein Übersetzer oft einfach ein paar Sachen durchprobieren muss, um herauszufinden, was ein gewisser Abschnitt darstellt. Zum Beispiel könnte ein Compiler an einer Stelle eine Logik ähnlich zu folgender anwenden: Wenn es keine Zahl ist dann wird es wohl ein String sein und wenn es dies auch nicht ist, dann handelt es sich um einen Fehler im Programmcode. Wenn es aber keine Zahl ist, so müssen aber alle Zeichen die nötig waren, um festzustellen, dass es keine Zahl ist, erneut interpretiert werden, um festzustellen ob es sich vielleicht um einen String handelt. Bei einer Zahl kann man es bereits beim ersten Buchstaben feststellen, jedoch gibt es auch komplexere Beispiele wo dies nicht so einfach ist. Hier benötigt man irgendeinen Weg, zurückspulen zu können.

Es gibt viele Wege, dies nun zu realisieren. Zum Beispiel kann man Zeichenströme schreiben, welche immer nur das absolute Minimum von Zeichen im Speicher halten. Man muss ja nicht überall hin spulen können. Es reicht an ein paar bekannte Stellen zurück spulen zu können. Dies ermöglicht es selbst wahnsinnig große Quelldateien zu übersetzen und doch nur ein paar Byte Speicher zu benötigen.

In diesem Artikel wollen wir es allerdings nicht zu kompliziert machen und kopieren die Datei kurzerhand in den Speicher. Eine effiziente Implementierung eines Zeichenstroms wäre ein Thema, das in einen anderen Artikel gehört. Unser primitiver Strom wird aus zwei Zeigern bestehen. Einer zeigt auf das Zeichen, welches als nächstes verarbeitet werden soll und der andere auf das erste Zeichen nach dem Ende des Puffers. Es entspricht also einem Iteratorenpaar im Sinn der STL.

Die meisten Funktionen im Übersetzer werden der folgenden ähnlich sehen:

bool foo(..., const char*&pos, const char*end, ...){
	// Do stuff
}

Der erste Zeiger wird per Referenz übergeben, damit auch der Aufrufer weiß, bis wohin gelesen wurde. end dagegen ist immer gleich und muss deswegen nicht per Referenz übergeben werden. Der Rückgabewert gibt an, ob "es" geklappt hat. Was das nun im Detail heißt, hängt natürlich von der Funktion ab.

Da wir im Fehlerfall backtracken müssen und eine Ausnahme einen solchen Fall darstellt, werde ich Scopeguards einsetzen, um den Code ausnahmesicher und lesbar zu halten. Wir werden zwar keine Ausnahmen einsetzen, allerdings sollte man doch dafür sorgen, dass der Code ausnahmefreundlich ist.

class BacktrackGuard{
public:
	explicit BacktrackGuard(const char*&pos):
		pos(pos), start(pos){}

	~BacktrackGuard(){
		if(start)
			pos = start;
	}

	void no_backtrack(){
		start = 0;
	}

private:
	const char*&pos;
	const char*start;

	BacktrackGuard(const BacktrackGuard&);
	BacktrackGuard&operator=(const BacktrackGuard&);
};

In vielen Compilern sind diese Zeichenströme auch dafür verantwortlich, die Position in der Datei zu merken. Das heißt konkret, welche Zeile und das wie vielte Zeichen in dieser. Dies ist zum Beispiel nötig, um sinnvolle Fehlermeldungen ausgeben zu können. Wir werden es uns hier aber einfach machen und dieses Problem einfach ignorieren: Wir geben keine Positionsinformationen mit den Fehlern aus.

3 Einfachstes Program

Um anzufangen wollen wir einen Compiler schreiben, welche nur eine sehr einfache Sprache übersetzen kann, eine die so einfach ist, dass es schon an Spott grenzt, sie als Sprache zu bezeichnen. Ein Programm besteht aus einer einzigen Ziffer und diese muss eine '1' sein. Ein korrektes (und sogar das einzig korrekte) Programm wäre also:

1

Man sollte beachten, dass der Einfachheit zuliebe keine Leerzeichen erlaubt sind.

Das "1" soll bewirken, dass "1" auf der Konsole ausgegeben wird. Der Compiler hierfür sieht wie folgt aus:

#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
using namespace std;

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of program"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Auch wenn dieses Programm nicht allzu kompliziert sein dürfte, reicht es aber um die Grundstruktur zu verdeutlichen. Source code wird eingelesen, dann verarbeitet und der Assemblercode wird in eine Datei namens "out.s" geschrieben. Wo etwas fehlschlagen kann und warum, sollte durch die Fehlermeldungen deutlich werden.

Um eine ausführbare Datei zu erzeugen muss "out.s" gegen eine C-Sourcecode-Datei gelinkt werden, welche folgendermaßen aussieht:

#include <stdio.h>

void prog();

int main(){
	prog();
}

void print_int(int n){
	printf("%d", n);
}

Dieser Schnipsel C-Code stellt sozusagen die Laufzeitbibliothek unserer Sprache dar. Darum nenne ich die Datei "rt.c" (steht für runtime). Übersetzen kann man das ganze recht einfach.

gcc out.s rt.c -o out.exe

Manche GCC-Inkarnationen hängen nicht automatisch einen Unterstrich vor C-Funktionsnamen. Wenn die angegebene Kommandozeile einen Linkerfehler produziert, dann wird das wahrscheinlich der Grund sein. Ändern Sie in diesem Fall die Datei "rt.c" zu:

#include <stdio.h>

void _prog();

int main(){
	_prog();
}

void _print_int(int n){
	printf("%d", n);
}

Nun sollte es keine Probleme mehr geben.

4 Immer noch einfach

Man braucht kein Hellseher zu sein, um zu bemerken, dass unsere Sprache noch nicht zu viel zu gebrauchen ist. Dies wird vorerst aber leider auch so bleiben. Zuerst arbeiten wir nämlich an der Syntax unserer Sprache.

Es wäre doch gut, wenn man mehr Freiheiten beim Setzen der Leerzeichen hätten. Hierfür schreiben wir uns eine Funktion, welche Leerzeichen überspringt.

#include <cctype>
//...
void skip_spaces(const char*&pos, const char*end){
	while(pos != end && isspace(*pos))
		++pos;
}

In einem komplexeren Compiler würde diese Funktion auch Kommentare überspringen. Der Rest des Compilers ändert sich nur leicht:

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	skip_spaces(pos, end);		// Ich bin neu (1)
	if(pos != end){
		if(*pos == '1'){
			++pos;
			out
				<<"pushl $1"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			return true;
		}else
			cerr<<"Unknown command"<<endl;
	}else
		cerr<<"Unexpected at end of file"<<endl;
	return false;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out	
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	if(parse_one(pos, end, out)){
		skip_spaces(pos, end);		// Ich auch (2)
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Wozu die erste neue Zeile dient, sollte selbsterklärend sein. Die zweite sorgt dafür, dass Leerzeichen sich auch am Ende des Programms befinden können.

Als nächstes werden wir es möglich machen, die 1 in Buchstaben auszuschreiben. Dazu schreiben wir eine Funktion welche überprüft, ob wir uns vor einem Wort befinden oder nicht. Falls ja wird dieses auch gleich übersprungen.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Nun müssen wir nur noch parse_one anpassen.

void write_print_one_code(std::ostream&out){
	out
		<<"pushl $1"<<endl
		<<"call _print_int"<<endl
		<<"addl $4, %esp"<<endl;
}

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(ignore(pos, end, "1") || ignore(pos, end, "one")){
		write_print_one_code(out);
		return true;
	} else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
}

Wer genau hinschaut, bemerkt, dass sich in parse_one kein skip_spaces mehr befindet. Dadurch, dass wir in ignore einen Aufruf platziert haben, werden beinahe alle anderen überflüssig und damit ist der Code schon viel weniger fehleranfällig und lesbarer.

Und schon können wir Programme wie folgendes übersetzen.

one

Jedoch hat sich bereits der erste Bug eingeschlichen. Betrachten wir mal:

onehundred

Das Programm wird zwar wie erwünscht abgelehnt, aber nicht aus dem richtigen Grund. Der Compiler liest nur bis zum Ende von "one", übersetzt dies dann auch und das Programm wird nur abgelehnt, weil der Compiler nichts mit "hundred" hinter dem Ende des erkannten Programms anzufangen weiß. Das heißt, der Compiler reißt Wörter ohne Gewissensbisse entzwei. Es hängt natürlich von der Sprache ab, ob dies ein Fehler ist oder nicht, allerdings nimmt ein C-Compiler kein "staticintfoo" an, sondern verlangt, dass diese schön mit Leerzeichen getrennt werden. Dies hat auch seinen guten Grund, denn dadurch werden Zweideutigkeiten vermieden. Allerdings übersetzt ein C-Compiler auch "1+2" obwohl zwischen der "1" und dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Operatoren eigene Funktionen schreiben. Die eine würde zusätzlich noch überprüfen, ob sich ein Leerzeichen hinter dem Wort befindet.

Es geht allerdings auch einfach.

bool ignore(const char*&pos, const char*end, const char*what){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);

	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			--what;
			if(isalpha(*what))
				if(isalnum(*pos))
					return false;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Streng genommen ist dies zwar ein Hack, aber er macht doch vieles einfacher und angenehmer.

5 Schon etwas komplizierter

So, nun wollen wir auch mal eine Sprache verwenden, welche ansatzweise eine Verwendung hat. Ziel ist es, einen Compiler zu schreiben, der Programme wie folgendes annimmt:

print 1
print 2 print 3
print 4 print 
5

Das Programm besteht aus einer Reihe von "print" Befehlen, welche jeweils eine positive Ganzzahl ausgeben.

Als erstes ersetzen wir parse_one (und auch den Aufruf in main) durch folgende Funktion:

bool parse_program(const char*&pos, const char*end, ostream&out){
	while(parse_command(pos, end, out))
		{}
	return true;
}

Wie bereits erwähnt, besteht ein Programm aus einer Reihe von Befehlen und darum sollte die Funktion, die ein Programm liest, auch nur dies tun. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtlich und verständlich.

Um das Lesen eines Befehls kümmert sich die Funktion parse_command, welche dann wieder auf eine Reihe von Unterfunktionen zurückgreift.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		int n;
		if(read_number(pos, end, n)){
			out
				<<"pushl $"<<n<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

bool read_number(const char*&pos, const char*end, int&n){
	skip_spaces(pos, end);
	if(pos != end && isdigit(*pos)){
		n = 0;
		do{
			n *= 10;
			n += *pos - '0';
			++pos;
		}while(pos != end && isdigit(*pos));
		return true;
	}else
		return false;
}

read_number könnte man nun natürlich auch das Lesen von Hexadezimal- oder Oktalzahlen beibringen. Wir wollen uns aber mit einfachen Dezimalzahlen begnügen, um nicht den Rahmen zu sprengen.

In welche und wie viele Unterfunktionen man aufbrechen soll, hängt von der eigenen Erfahrung ab. Hier kann ich höchstens als Faustregel angeben, dass man alles auslagern soll, für was man einen passenden Funktionsnamen findet.

6 Taschenrechner

Als nächstes nehmen wir uns vor, komplexere Ausdrücke zu unterstützen. Also zum Beispiel folgendes Programm.

print 1+1
print 5*8
print 4 + 8*7

Jeder, der mit dem Überladen von Operatoren in C++ vertraut ist, der weiß, dass man Operatoren auch als Funktionsaufrufe ansehen kann. Den Code oben könnte man auch wie folgend umschreiben.

print add(1, 1)
print mul(5, 8)
print add(4, mul(8, 7))

Auf diese Weise wollen wir unsere Operatoren auch umsetzen, als inline-Minifunktionen. Wer schon einmal x86-Assembler geschrieben hat, der weiß, dass man das Register eax für Rückgabewerte nutzt. Dies wollen wir auch hier tun. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumente nacheinander aus und nutzt den Stack um Werte zwischenzuspeichern.

Allerdings, bevor wir uns um die Generierung des Assemblercodes kümmern, müssen wir zuerst dafür sorgen, dass wir den Ausdruck richtig lesen können. Hier hilft es, sich eine Reihe von Fragen zu stellen:

Woraus besteht ein Program? Aus Befehlen
Woraus besteht ein Befehl? Aus "print" gefolgt von einem Ausdruck
Woraus besteht ein Ausdruck? Aus einer Summe oder Differenz von Termen
Woraus besteht ein Term? Aus einem Produkt, Quotient oder Modulo von Faktoren
Woraus besteht ein Faktor? Aus einer Zahl mit vielleicht einem Vorzeichen

Wer sich für den theoretischen Hintergrund dieser Fragen interessiert, der kann mal nach EBNF suchen. In diesem Artikel werde ich aber nicht weiter darauf eingehen.

Nun wissen wir schon, welche Funktionen gebraucht werden. Einige der Funktionen sind bereits implementiert und darum werde ich sie nicht wiederholen.

bool parse_command(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

Diese Funktion sollte selbsterklärend sein.

bool parse_expression(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_term(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "+")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after +"<<endl;
					return false;
				}
				out
					<<"addl (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "-")){
				out<<"push %eax"<<endl;
				if(!parse_term(pos, end, out)){
					cerr<<"Expected term after -"<<endl;
					return false;
				}
				out
					<<"subl %eax, (%esp)"<<endl
					<<"pop %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Diese Funktion sieht auf den ersten Blick bedrohlich aus, allerdings ist sie an sich recht einfach. Die einzelnen Terme der Summe werden nacheinander ausgewertet und zusammengezählt beziehungsweise voneinander abgezogen.

Die Multiplikation wird ähnlich behandelt.

bool parse_term(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	if(parse_factor(pos, end, out)){
		for(;;){
			if(ignore(pos, end, "*")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after *"<<endl;
					return false;
				}
				out
					<<"imull (%esp), %eax"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(ignore(pos, end, "/")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl;
			}else if(ignore(pos, end, "%")){
				out<<"push %eax"<<endl;
				if(!parse_factor(pos, end, out)){
					cerr<<"Expected factor after /"<<endl;
					return false;
				}

				out
					<<"movl %eax, %ebx"<<endl
					<<"pop %eax"<<endl
					<<"movl $0, %edx"<<endl
					<<"idiv %ebx"<<endl
					<<"movl %edx, %eax"<<endl;
			}else
				break;
		}
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Die Funktion, um Faktoren auszuwerten, ist recht einfach, da ein Faktor nur aus einer Zahl bestehen kann.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	int n;
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

7 Klammern

Als nächstes wollen wir geklammerte Ausdrücke unterstützen. Fragen wir uns erneut, woraus ein Faktor bestehen kann. Wirklich nur aus einer Zahl? Nein, unter Umständen auch aus einem geklammerten Ausdruck. Ein Ausdruck besteht - über Umwege - aber wieder aus einem Faktor. Es mag auf den ersten Blick nicht offensichtlich sein, allerdings stellen solche rekursiven Definitionen an sich kein Problem dar. Man muss die entsprechende Funktion lediglich rekursiv aufrufen.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	int n;
	if(read_number(pos, end, n))
		out<<"movl $"<<n<<", %eax"<<endl;
	else if(ignore(pos, end, "(")){
		parse_expression(pos, end, out);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		out<<"negl %eax"<<endl;
	guard.no_backtrack();
	return true;
}

8 Variablen

Das nächste, was jeder Compiler beherrschen sollte, sind Variablen. Wir wollen uns hier auf lokale Variablen beschränken. Das heißt, alle werden auf den Stack gepackt und keine kommen in statischen Speicher. Um die Sache noch weiter zu vereinfachen, sind alle Variablen vom Typ int. Dies ist eine ziemlich starke Einschränkung, aber irgendwo muss ich ja streichen damit dieser Artikel nicht zu groß wird.

Das erste was benötigt wird, ist eine Datenstruktur welche die Variablen verwaltet. Hierfür definiere ich eine Klasse.

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
};

Auf die Implementierungsdetails werde ich nicht eingehen. Eine fertige Implementierung findet man hier.

Es soll möglich sein, in höheren Scopes Variablen zu definieren, welche Variablen aus den unteren Scopes verdecken. Dieses Verhalten ist natürlich sprachabhängig allerdings wollen wir uns hier einfach an die C-Regeln halten. Mit ihnen dürfte jeder Leser vertraut sein.

• create_var erzeugt eine Variable im obersten Scope mit einem gewissen Namen. Falls es bereits eine solche Variable gibt, so wird false zurückgegeben, andernfalls wird true zurückgegeben.
• Mit is_var_defined kann man ermitteln, ob es eine Variable bereits gibt oder nicht. Hier sollte darauf hingewiesen werden, dass diese Funktion nichts über die Erfolgsaussichten von create_var aussagt, da Variablen verdeckt werden können.
• get_var_address gibt die Stackadresse der Variable aus. Adressen werden von ebp aus gezählt. Wir müssen also auch die main Funktion anpassen damit ebp einen brauchbaren Wert enthält.
• push_scope sollte aufgerufen werden, wenn sich der Compiler in einen neuen Scope begibt.
• Beim Verlassen eines Scopes sollte pop_scope aufgerufen werden. Alle Variablen dieses Scopes werden zerstört.

Der out-Parameter ist der Zeichenstrom der den Assemblercode ausgibt. Methoden mit ihm können Code generieren.

Nun müssen wir noch dafür sorgen, dass VarManager überall zugänglich ist. Eine Möglichkeit wäre, eine Instanz global anzulegen oder ein Singleton zu basteln. Dies ist aber nicht wirklich die feine Art und führt zu Problemen, sobald man den Code parallelisieren möchte. Eine andere Möglichkeit ist eine Instanz in main anzulegen und dann eine Referenz auf diese von Funktion zu Funktion weiter zu geben. Diese Lösung ist viel flexibler, allerdings sind Variablen nicht das einzige, was verwaltet werden will.

Wer sich ein bisschen mit Schleifen auskennt, der weiß, dass dort Sprungadressen verwaltet werden müssen. Wenn man Variablen in Register packen will, so müssen diese auch verwaltet werden. Wenn wir jetzt auf alles eine Referenz übergeben, dann verlieren wir uns bald in endlosen Parameterlisten. Ein noch viel schlimmeres Problem ist, dass man keine neue Struktur einführen kann ohne den ganzen Code umzubauen.

Die Lösung ist recht einfach. Man baut eine Hilfsstruktur, welche diese Referenzen verwaltet. Dies sieht dann etwa folgendermaßen aus:

class Env{
public:
	explicit Env(VarManager&var):
		var(var){}

	VarManager&var;
};

Eine Referenz auf diese Klasse wird dann von Funktion zu Funktion übergeben. Wenn eine neue Verwaltungsstruktur hinzugefügt wird, so braucht man nur Env und main zu verändern. Der gewählte Name steht für Environment. Als Environment verstehe ich die Zusammenfassung aller Verwaltungsstrukturen.

Man kann die Ausgabe auch als Teil von Env ansehen.

class Env{
public:
	explicit Env(VarManager&var, ostream&out):
		var(var), out(out){}

	VarManager&var;
	ostream&out;
};

Die main-Funktion wird also wie folgend abgeändert:

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	Env env(var, out);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
	}
}

parse_command muss nun auch geändert werden, da unsere Sprache ja nun zusammengesetzte Befehle mittels Scopes unterstützt. Wir werden hier wie in C Akkoladen verwenden um Scopes zu begrenzen. Um die Funktion klein zu halten, lagere ich Teile der Funktion in eine neue Funktion namens parse_block aus.

bool parse_block(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "{")){
		env.var.push_scope();

		while(parse_block(env, pos, end))
			{}

		if(ignore(pos, end, "}")){
			env.var.pop_scope(env.out);
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Missing }"<<endl;
			return false;
		}
	}else{
		guard.no_backtrack();
		return parse_command(env, pos, end);
	}
}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else
			cerr<<"Argument to print is missing"<<endl;
	}
	return false;
}

parse_program können wir dann auch abändern, da mehrere Befehle durch die Benutzung von Akkoladen möglich sind.

bool parse_program(Env&env, const char*&pos, const char*end){
	return parse_block(env, pos, end);
}

Nun ist es möglich, Programme wie folgendes zu übersetzen.

{
	print 1
	print 2
	{
		print 3
		{}
	}
	print 4
}

Die äußeren Akkoladen sind nötig.

Auch wenn das schon nicht schlecht aussieht, haben wir doch einen wesentlichen Bestandteil vergessen. Es gibt noch keine Variablen!

Zuerst brauchen wir eine Funktion, die Namen von Variablen liest.

bool read_identifier(const char*&pos, const char*end, string&identifier){
	skip_spaces(pos, end);
	if(pos != end && (isalpha(*pos) || *pos == '_')){
		identifier = "";
		do{
			identifier += *pos;
			++pos;
		}while(pos != end && (isalnum(*pos) || *pos == '_'));
		return true;
	}else
		return false;
}

Das nächste, was wir brauchen, ist ein Befehl, um Variablen zu erschaffen und einen weiteren, um ihnen etwas zuzuweisen.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}else{
			cerr<<"Argument to print is missing"<<endl;
			return false;
		}
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;

	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Jetzt brauchen wir nur noch eine Möglichkeit, lesend auf eine Variable zuzugreifen. Dazu verändere ich parse_factor. Hier lagere ich auch wieder einen Teil der Funktion aus.

bool parse_literal(Env&env, const char*&pos, const char*end){
	int n;
	if(read_number(pos, end, n)){
		env.out<<"movl $"<<n<<", %eax"<<endl;
		return true;
	}
	string identifier;
	if(read_identifier(pos, end, identifier)){
		if(env.var.is_var_defined(identifier)){
			env.out<<"movl "<<env.var.get_var_address(identifier)<<", %eax"<<endl;
			return true;
		}else{
			cerr<<"Undefined variable "<<identifier<<endl;
			return false;
		}
	}

	return false;
}

bool parse_factor(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool negate = false;
	if(ignore(pos, end, "-"))
		negate = true;

	if(parse_literal(env, pos, end)){

	}else if(ignore(pos, end, "(")){
		parse_expression(env, pos, end);
		if(!ignore(pos, end, ")"))
			cerr<<"Missing )"<<endl;
	}else
		return false;

	if(negate)
		env.out<<"negl %eax"<<endl;

	guard.no_backtrack();
	return true;
}

Langsam aber sicher entwickelt sich unsere Sprache weiter. Ein Programm sieht jetzt schon aus, als könnte es für irgendetwas zu gebrauchen sein.

{
	var a
	var b
	a = 5
	b = a + 5
	{
		a = a-1
		var c
		c = b
		print c
	}
	print a+b
}

9 Hello World!

Im vorherigen Kapitel habe ich gesagt, alle Variablen wären vom Typ int. Daran werde ich jetzt auch nichts ändern, allerdings benötigt jede Sprache wenigstens eine minimale Unterstützung für Strings. Ohne kann man noch nicht einmal ordentliche Beispielprogramme schreiben. Noch nicht einmal ein "Hello world!"-Programm ist möglich.

Ziel dieses Kapitels ist es, den print-Befehl ein wenig aufzumotzen. Er soll auch Stringliterale als Parameter übernehmen können und mehrere durch Kommas getrennte Parameter sollen auch unterstützt werden. Er wird aber einzigartig bleiben in dem Sinn, dass nur er Strings als Argument nehmen kann.

Als erstes benötigen wir eine Funktion, welche Stringliterale parsen kann.

char unescape_character(char c){
	switch(c){
		case 'n':return '\n';
		case 't':return '\t';
		case '\\':return '\\';
		case '\"':return '\"';
	}
	cerr<<"Unknown escape sequence \\"<<c<<endl;
	return c;
}

bool read_string(const char*&pos, const char*end, string&str){
	BacktrackGuard guard(pos);
	skip_spaces(pos, end);
	if(pos != end && *pos == '"'){
		++pos;
		str = "";
		do{
			if(*pos == '\\'){
				++pos;
				if(pos == end){
					cerr<<"EOF in string literal"<<endl;
					return false;
				}
				str += unescape_character(*pos);
			}else
				str += *pos;
			++pos;
		}while(pos != end && *pos != '\"');
		++pos;
		guard.no_backtrack();
		return true;
	}else
		return false;
}

Als nächstes brauchen wir eine Möglichkeit, Zeichenketten in den Code einzufügen. Diese werden wir in einer Data-Sektion unterbringen. Wir brauchen also eine weitere Klasse, welche die Stringliterale verwaltet.

class DataSection{
public:
	void add_string_data(string label, string data);
	void write_data_section(ostream&);
};

Auch hier werde ich auf eine fertige Implementierung verweisen. Es gibt den offensichtlichen Weg, diese Klasse zu implementieren oder man kann versuchen, ein paar Bytes zu sparen, indem man versucht, die Strings so anzuordnen, dass sie sich überlappen. Dies geht natürlich nur, solange die originalen Zeichenketten in der Data-Sektion nicht verändert werden dürfen.

• Mit add_string_data kann man einen String ablegen. Es wird ein Nullbyte angefügt und Label wird so gesetzt, dass es auf das erste Byte zeigt.
• write_data_section macht das, was der Name sagt.

Da DataSection ein Label braucht, brauchen wir auch jemanden, der diese verwaltet.

class LabelManager{
public:
	string make_unique();
};

• make_unique erzeugt einen eindeutigen Labenamen und gibt diesen zurück.

Die Implementierung gibt es hier.

main und Env müssen auch angepasst werden:

class Env{
public:
	explicit Env(VarManager&var, ostream&out, DataSection&data, LabelManager&label):
		var(var), out(out), data(data), label(label){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
};

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out
		<<".text"<<endl
		<<".globl _prog"<<endl
		<<"_prog:"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	VarManager var;
	DataSection data;
	LabelManager label;
	Env env(var, out, data, label);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else{
			out
				<<"pop %ebp"<<endl
				<<"ret"<<endl
				<<".data"<<endl;
			data.write_data_section(out);
		}
	}
}

Schlussendlich muss auch noch "rt.c" angepasst werden, damit Zeichenketten ausgegeben werden können.

#include <string.h>

void print_string(const char*str){
	fwrite(str, 1, strlen(str), stdout);
}

printf will ich nicht benutzen, da man bei dieser Funktion auf Prozentzeichen achten muss. Durch die Benutzung von fwrite gehe ich allen möglichen Problemen aus dem Weg, selbst denen die durch Printf-Format-Erweiterungen entstehen könnten.

Da der print-Befehl komplizierter geworden ist, lagere ich ihn aus.

bool parse_print(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "print")){
		do{
			string str;
			if(read_string(pos, end, str)){
				string label = env.label.make_unique();
				env.data.add_string_data(label, str);
				env.out
					<<"pushl $"<<label<<endl
					<<"call _print_string"<<endl
					<<"addl $4, %esp"<<endl;
			}else if(parse_expression(env, pos, end)){
				env.out
					<<"pushl %eax"<<endl
					<<"call _print_int"<<endl
					<<"addl $4, %esp"<<endl;
			}else{
				cerr<<"Argument to print is missing"<<endl;
				return false;
			}
		}while(ignore(pos, end, ","));
		guard.no_backtrack();
		return true;
	}else
		return false;

}

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out)){
				guard.no_backtrack();
				return true;
			}else
				cerr<<"Variable redefined"<<endl;
		}else
			cerr<<"var must be followed by a variable name"<<endl;
		return false;
	}else{
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(ignore(pos, end, "=")){
				if(parse_expression(env, pos, end)){
					env.out<<"movl %eax, "<<env.var.get_var_address(identifier)<<endl;
					guard.no_backtrack();
					return true;
				}else
					cerr<<"Missing right operant of ="<<endl;
			}else
				cerr<<"Missing = in assignment"<<endl;

		}
		return false;
	}
}

Nun endlich können wir ein "Hello world"-Programm schreiben.

{
	print "Hello" , " world!\n"
	var a
	var b
	a = 3
	b = 5
	print a, " + ", b, " = ", a+b
}

10 If und Schleifen

Was jetzt noch fehlt, sind Abfragen und Schleifen. Diese sind auch nicht sonderlich schwer. Zuerst benötigen wir eine Funktion, um ein if einzulesen. Der Einfachheit halber werden wir nicht versuchen, die Werte im Statusregister zu halten und wenn möglich wiederzuverwenden. If nutzt einfach wie überall eax und nimmt natürlich auch ein int als Bedingung. Dies ist recht ineffizient, allerdings macht es die Sache doch wesentlich einfacher.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string label = env.label.make_unique();
		if(parse_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<label<<endl;
			if(parse_block(env, pos, end)){
				env.out<<label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

So, nun muss nur noch parse_command leicht angepasst werden.

bool parse_command(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(parse_print(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else if(parse_if(env, pos, end)){
		guard.no_backtrack();
		return true;
	}else 
		...
}

An sich war es das schon, allerdings ist ein Vergleich, ob denn nun zwei Werte gleich sind, noch ziemlich haarig.

{
	var a
	var b
	a = 4
	b = 3
	if a - b
		print "nicht gleich"
}

Deswegen muss parse_expression verändert werden. Als erste nenne ich parse_expression in parse_numeric_expression um und schreibe ein paar weitere Funktionen. Diese kümmern sich um das Einlesen der Vergleichsoperatoren und der logischen Verknüpfungen. Dadurch werden die Funktionen nicht endlos lang.

bool parse_compare_expression(Env&env, const char*&pos, const char*end){
	if(ignore(pos, end, "true")){
		env.out<<"movl $1, %eax"<<endl;
		return true;
	}else if(ignore(pos, end, "false")){
		env.out<<"movl $0, %eax"<<endl;
		return true;
	}else if(parse_numeric_expression(env, pos, end)){
		BacktrackGuard guard(pos);
		string condition_code;
		if(ignore(pos, end, "="))
			condition_code = "e";
		else if(ignore(pos, end, "!="))
			condition_code = "ne";
		else if(ignore(pos, end, "<="))
			condition_code = "be";
		else if(ignore(pos, end, ">="))
			condition_code = "ae";
		else if(ignore(pos, end, "<"))
			condition_code = "b";
		else if(ignore(pos, end, ">"))
			condition_code = "a";
		else
			cerr<<"Unknown compare operator"<<endl;
		env.out<<"pushl %eax"<<endl;
		if(parse_numeric_expression(env, pos, end)){
			env.out
				<<"cmpl %eax, (%esp)"<<endl
				<<"movl $0, %eax"<<endl
				<<"set"<<condition_code<<" %al"<<endl
				<<"addl $4, %esp"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

bool parse_boolean_expression(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	bool not_operation = false;
	if(ignore(pos, end, "!"))
		not_operation = true;
	if(parse_compare_expression(env, pos, end)){
		for(;;){
			string operation;
			if(ignore(pos, end, "&"))
				operation = "and";
			else if(ignore(pos, end, "|"))
				operation = "or";
			else if(ignore(pos, end, "^"))
				operation = "xor";
			else{
				if(not_operation)
					env.out<<"notl %eax"<<endl;
				guard.no_backtrack();
				return true;
			}
			env.out<<"pushl %eax"<<endl;
			if(!parse_compare_expression(env, pos, end))
				return false;
			env.out
				<<operation<<" %eax, (%esp)"<<endl
				<<"addl $4, %esp"<<endl;
		}
	}
	return false;
}

Man sollte beachten, dass die Reihenfolge der Abfragen in parse_compare_expression nicht egal ist. Wenn mehrere Operatoren mit dem gleichen Zeichen anfangen, so muss man zuerst auf den längsten testen, ansonsten wird der Operator entzweigerissen. Aus "<=" würde ein "<", gefolgt von einem "=" und dies würde zu einem Fehler führen.

In parse_if wird natürlich parse_boolean_expression verwendet und nicht parse_numeric_expression. Dadurch ist die doppelte Bedeutung von "=" auch nicht zweideutig. Aus dem Kontext heraus kann bestimmt werden, ob es ein Vergleich oder eine Zuweisung sein soll.

Nun fehlt nur noch ein else. Dafür müssen wir parse_if anpassen.

bool parse_if(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "if")){
		string false_label = env.label.make_unique();
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<false_label<<endl;
			if(parse_block(env, pos, end)){
				if(!ignore(pos, end, "else")){
					env.out<<false_label<<":"<<endl;
					guard.no_backtrack();
					return true;
				}
				string end_label = env.label.make_unique();
				env.out
					<<"jmp "<<end_label<<endl
					<<false_label<<":"<<endl;
				if(!parse_block(env, pos, end))
					return false;
				env.out<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Schleifen sind auch nicht sonderlich verschieden von einem if. Als erstes schreibe ich eine parse_while-Funktion und die wird dann in parse_command genauso wie parse_if aufgerufen.

bool parse_while(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	if(ignore(pos, end, "while")){
		string 
			reloop_label = env.label.make_unique(),
			end_label = env.label.make_unique();
		env.out<<reloop_label<<":"<<endl;
		if(parse_boolean_expression(env, pos, end)){
			env.out
				<<"testl %eax, %eax"<<endl
				<<"jz "<<end_label<<endl;
			if(parse_block(env, pos, end)){
				env.out
					<<"jmp "<<reloop_label<<endl
					<<end_label<<":"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
	}
	return false;
}

Nun ist unser Compiler schon fähig, sinnvolle Programme zu übersetzen. Folgendes Programm zählt von 0 bis 10:

{
	var i
	i = 0
	while i<=10{
		print i, "\n"
		i = i+1
	}
}

Hier ist zum Beispiel ein Programm, das alle Primzahlen bis 100 sucht:

{
	print "Between 1 and 100 the following prime numbers exist : 2"
	var p
	p = 3
	while p < 100{
		var d 
		d = 2
		var is_prime
		is_prime = 1
		while d<p{
			if p%d = 0{
				is_prime = 0
			}
			d = d+1
		}
		if is_prime != 0{
			print ", ", p
		}
		p = p+1
	}
}

Aufmerksamen Lesern fällt wahrscheinlich auf, dass ich is_prime nicht mit true initialisiere. Nun, dies liegt daran, dass dies kein numerischer Wert ist. Diese strikte Unterscheidung zwischen boolschem und numerischem Wert ermöglicht aber auch, ein einfaches Gleichzeichen sowohl für eine Zuweisung als auch für einen Vergleich zu nehmen. Es hat also sowohl Vor- wie auch Nachteile. In einer kompletten Sprache gäbe es natürlich auch einen boolschen Typ und dadurch wäre das Problem elegant gelöst.

Eine for-Schleife ist nicht signifikant anders und ihre Implementierung wird dem Leser überlassen.

11 Funktionen

Funktionen sind die Bausteine jedes komplexeren Programms. Darum will ich sie auch in diesem Artikel nicht auslassen. Mit Funktionen kann man sich, was die Komplexität angeht, beliebig nach oben steigern. Templatefunktionen sind ein gutes Beispiel dafür. Hier will ich mich aber auf recht einfache Funktionen beschränken. Für jede Funktion speichern wir den Namen und die Anzahl der Parameter. Da es nur int als Variablentyp gibt, brauchen wir keine Informationen über die Typen der Parameter zu speichern. Der Rückgabewert ist auch immer ein int. Funktionen ohne Rückgabetyp machen natürlich Sinn, aber das machen Templatefunktionen auch. Als Kompromiss zwischen Sinn und Einfachheit lassen wir es zu, dass ein Rückgabewert nicht initialisiert ist. Das heißt er enthält Schrott.

Funktionen müssen wie in C im Voraus deklariert werden und können mehrfach gleich deklariert werden. Sie können nicht überladen werden. Als Aufrufskonvention werden wir eine verwenden, die der des GCCs ähnlich ist. Dadurch können wir auch ohne weiteres gegen C-Code linken. Der Unterschied besteht darin, dass Argumente von links nach rechts auf den Stack gepackt werden. Beim GCC werden die Parameter von rechts nach links auf den Stack gepackt. Der Grund hierfür ist, dass es so für uns einfacher ist. Der Aufrufer ist dafür verantwortlich, die Argumente wieder vom Stack zu nehmen. Eine Funktion darf ihre Parameter verändern. Der Aufrufer darf also keine Argumente recyceln. Der Rückgabewert befindet sich in eax.

Als erstes brauchen wir eine Klasse, um die Informationen zu verwalten. Ich werde wieder einmal nur auf die Klassenschnittstelle eingehen und auf eine Implementierung verweisen.

class FuncManager{
public:
	bool declare(string name, unsigned parameter_count);
	bool exists(string name)const;
	string get_label(string name)const;
	unsigned get_parameter_count(string name)const;
};

• declare macht eine Funktion bekannt.
• exists überprüft, ob eine Funktion bekannt gemacht wurde.
• get_label gibt das Label des Funktionskörper zurück.
• Mit get_parameter_count findet man heraus, wie viele Parameter eine Funktion braucht.

Um auf Argumente zurückgreifen zu können und Werte zurückgeben zu können, müssen wir auch VarManager verändern. Konkret werden ein paar Methoden hinzugefügt und die Klasse sieht nun folgendermaßen aus:

class VarManager{
public:
	bool create_var(string name, ostream&out);
	bool add_arg(string name, unsigned pos);
	bool is_var_defined(string name)const;
	string get_var_address(string name)const;
	void push_scope();
	void pop_scope(ostream&out);
	void simulate_pop_all_scopes(ostream&out)const;
};

• add_arg gibt einem Parameter einen Namen. pos gibt an, um das wie vielte Argument von links es sich handelt. Das erste Argument hat den Index 0. Der Rückgabewert gibt an, ob es bereits einen solchen Parameter gab oder nicht. Argumente werden in ihrem eigenen Scope angelegt und darum können sie mit gleichnamigen lokalen Variablen koexistieren. Sie werden jedoch von denen verdeckt.
• simulate_pop_all_scopes generiert Code, um alle Scopes zu löschen, ohne dies jedoch zu tun. Dies wird benötigt, um ein return wie in C zu realisieren. Für andere Formen von Sprüngen, wie zum Beispiel break, würde man einen ähnlichen Mechanismus benötigen.

Eine Implementierung gibt es hier.

In einem C-Programm unterscheidet man zwischen globalem Scope und Funktionskörper. In beiden Bereichen sind unterschiedliche Sprachkonstrukte erlaubt. So kann man zum Beispiel keine Funktion innerhalb einer anderen definieren. Schleifen können sich auch nicht im globalen Scope befinden. Diesen Unterschied wollen wir nun auch in unserer Sprache einführen.

Da wir keine globalen Variablen zulassen, kann man sich fragen, ob ein VarManager im globalen Scope Sinn macht. Meiner Meinung nach nicht. Deswegen gibt es auch für beide Teile des Programms unterschiedliche Env-Strukturen. Die eine nenne ich FuncEnv, da sie nur innerhalb einer Funktion Sinn macht und die andere einfach Env. Da wir uns bis jetzt nur um den Inhalt von Funktionen gekümmert haben, wird jedes alte Env in ein FuncEnv umbenannt.

struct FuncEnv{
	explicit FuncEnv(VarManager&var, ostream&out, DataSection&data, LabelManager&label, const FuncManager&func):
		var(var), out(out), data(data), label(label), func(func){}

	VarManager&var;
	ostream&out;
	DataSection&data;
	LabelManager&label;
	const FuncManager&func;
};

struct Env{
	explicit Env(ostream&out, DataSection&data, LabelManager&label, FuncManager&func):
		out(out), data(data), label(label), func(func){}

	ostream&out;
	DataSection&data;
	LabelManager&label;
	FuncManager&func;
};

Der FuncManager in FuncEnv ist konstant, da man keine Funktion innerhalb einer anderen erschaffen kann. In main wird eine Instanz von FuncManager angelegt wie wir es bereits für die meisten anderen Verwaltungsstrukturen gemacht haben.

Als nächstes brauchen wir eine Funktion zum Einlesen von Funktionsdefinitionen und Deklarationen.

bool read_arg_list(const char*&pos, const char*end, vector<string>&args){
	BacktrackGuard guard(pos);
	if(!ignore(pos, end, "("))
		return false;
	string arg_name;
	while(read_identifier(pos, end, arg_name)){
		args.push_back(arg_name);
		if(!ignore(pos, end, ","))
			break;
	}
	if(!ignore(pos, end, ")"))
		return false;
	guard.no_backtrack();
	return true;
}

bool parse_function(Env&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);
	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;

	vector<string>arguments;
	if(!read_arg_list(pos, end, arguments))
		return false;

	if(env.func.exists(func_name)){
		if(env.func.get_parameter_count(func_name) != arguments.size())
			cerr<<"Function "<<func_name<<" redeclared with wrong argument number"<<endl;
	}else
		env.func.declare(func_name, arguments.size());

	if(ignore(pos, end, ";")){
		guard.no_backtrack();
		return true;
	}

	VarManager var;

	for(unsigned j=0; j<arguments.size(); ++j)
		if(!var.add_arg(arguments[j], arguments.size()-j-1))
			cerr<<"2 arguments with same name "<<arguments[j]<<" in function "<<func_name<<endl;

	env.out
		<<".globl "<<env.func.get_label(func_name)<<endl
		<<env.func.get_label(func_name)<<":"<<endl
		<<"push %ebp"<<endl
		<<"mov %esp, %ebp"<<endl;
	;

	FuncEnv fenv(var, env.out, env.data, env.label, env.func);
	if(parse_block(fenv, pos, end)){
		env.out
			<<"pop %ebp"<<endl
			<<"ret"<<endl;
		guard.no_backtrack();
		return true;
	}

	return false;
}

Als nächstes sorgen wir dafür, dass eine Funktion auch aufgerufen werden kann. Dafür schreiben wir uns als erstes eine Funktion, die einen Aufruf einliest.

bool parse_function_call(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;
	else{
		if(ignore(pos, end, "(")){
			unsigned parameter_count = 0;
			if(!ignore(pos, end, ")")){
				do{
					if(!parse_numeric_expression(env, pos, end))
						return false;
					env.out<<"pushl %eax"<<endl;
					++parameter_count;
				}while(ignore(pos, end, ","));
				if(!ignore(pos, end, ")"))
					return false;
			}

			if(!env.func.exists(func_name))
				cerr<<"Unknown function "<<func_name<<endl;
			else if(env.func.get_parameter_count(func_name) != parameter_count)
				cerr<<"Wrong number of parameters to function "<<func_name<<endl;
			else{
				env.out<<"call "<<env.func.get_label(func_name)<<endl;
				if(parameter_count != 0)
					env.out<<"addl $"<<4*parameter_count<<", %esp"<<endl;
				guard.no_backtrack();
				return true;
			}
		}
		return false;
	}
}

Eine Funktion kann innerhalb eines Ausdrucks und eines Befehls aufgerufen. Es müssen also parse_factor und parse_command verändert werden. In parse_factor muss man parse_function_call vor parse_literal aufrufen, da ansonsten der Funktionsname als Variable interpretiert wird.

Nun fehlt nur noch die Möglichkeit, einen Wert zurückzugeben. Die Funktion, die sich darum kümmert, sollte nicht zu kompliziert sein, wenn man es geschafft hat, bis hier zu folgen.

bool parse_return(FuncEnv&env, const char*&pos, const char*end){
	BacktrackGuard guard(pos);

	if(ignore(pos, end, "return")){
		if(parse_numeric_expression(env, pos, end)){
			env.var.simulate_pop_all_scopes(env.out);
			env.out
				<<"pop %ebp"<<endl
				<<"ret"<<endl;
			guard.no_backtrack();
			return true;
		}
	}
	return false;
}

Diese Funktion wird nun noch in parse_command aufgerufen und schon können wir Funktionen übersetzen.

Nun müssen wir nur noch parse_program und main anpassen.

bool parse_program(Env&env, const char*&pos, const char*end){
	while(parse_function(env, pos, end))
	{}

	return true;
}

int main(){
	ifstream in("in.txt");
	vector<char>source_code;
	copy(istreambuf_iterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

	ofstream out("out.s");
	out<<".text"<<endl;

	const char*pos = &source_code.front();
	const char*end = &source_code.back() + 1;

	DataSection data;
	LabelManager label;
	FuncManager func;
	Env env(out, data, label, func);

	if(parse_program(env, pos, end)){
		skip_spaces(pos, end);
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<endl;
		else
			data.write_data_section(out);
	}
}

Ein "Hello World"-Programm sieht nun wie folgend aus:

prog(){
	print "Hello World!"
}

Selbst rekursive Funktionen sind kein Problem. Folgendes Programm berechnet die Fakultät einer Zahl rekursiv:

fact(n){
	if n = 0
		return 1
	else
		return n*fact(n-1)
}

prog(){
	print fact(9)
}

Wir können aber nun auch gegen C-Funktionen linken. Zum Beispiel kann man so etwas von der Konsole einlesen.

int read_int(){
	int r = -1;
	scanf("%d", &r);
	return r;
}

read_int();

prog(){
	var a
	print "a = "
	a = read_int()
	var b
	print "b = "
	b = read_int()
	print "a + b = ", a+b
	print "a - b = ", a-b
	print "a * b = ", a*b
	print "a / b = ", a/b
	print "a % b = ", a%b

}

Man muss nur beachten, dass die Parameter in C eine andere Reihenfolge haben werden. Die Funktion test(a,b,c) würde der C-Funktion test(c,b,a) entsprechen.

12 Parserbaum

Wer schon einmal vorher mit der Materie in Kontakt gekommen ist, wird sich wahrscheinlich wundern, warum ich ihn bis jetzt noch nicht erwähnt habe, ja vielleicht sogar wundern, wie wir überhaupt so weit ohne ihn gekommen sind. Die Rede ist vom Parserbaum.

Die Idee ist es, das Interpretieren der Eingangszeichenkette und das Generieren der Assemblercodes zu trennen. Diese Trennung bietet viele Vorteile, wobei die Möglichkeit, elegant mehrere Prozessoren zu unterstützen nur die offensichtlichste ist.

Der Parser liest den Code und generiert einen Baum, welcher alle wichtigen Informationen enthält. Der Generator nimmt diesen Baum dann und generiert den entsprechenden Code. Dies macht Arbeitsteilung im Entwicklerteam viel einfacher, da beide Teile nun unabhängig voneinander sind.

Ein weiterer großer Vorteil ist, dass es möglich wird, Funktionen zu inlinen und auch andere Optimierungen durchzuführen. Ich wüsste nicht, wie man dem Compiler, so wie er hier vorgestellt wurde, beibringen soll, Funktionsaufrufe zu ersetzen. Wenn man den Code allerdings als Baum vorliegen hat, so muss man nur einen Ast des Baums kopieren und noch ein paar Umformungen bezüglich der Variabelnamen durchführen. In einem Baum ist es auch leicht, Informationen über Unterausdrücke einzuholen. Zum Beispiel, ob ein Ausdruck noch etwas anderes tut außer den Rückgabewert zu berechnen. Dies ist wichtig um zum Beispiel 0*x durch 0 zu ersetzen.

In diesem Artikel wollen wir aber keinen Parserbaum mehr entwickeln. Es würde einfach den Rahmen sprengen.

13 Schlussbemerkung

Ziel dieses Artikels war es, den Leser in das Gebiet des Compilerbaus einzuführen und zwar ohne ihn mit Theorie zu bombardieren. Ich hoffe, Sie haben jetzt einen Überblick über die Materie und können sich vorstellen, wo man die Aussagen der Theorie praktisch einsetzen kann. Wer sich für das Thema interessiert, dem sei gesagt, dass es sich hier nur um die Spitze des Eisbergs handelt. Es gibt noch sehr viel, was in diesem Artikel noch nicht einmal mit einem Wort erwähnt wurde.

Ob es von meiner Seite einen weiteren Artikel zu diesem Thema geben wird, ist ungewiss. Es fällt mir schwer, einzuschätzen, ob ich in Zukunft noch genug Zeit und Motivation aufbringen kann. Natürlich hängt es auch davon ab, wie viele Leute sich dafür interessieren.