[X] Compiler

[Ben04]

Nachdem Zweimer ja spurlos verschwunden ist habe ich mal selbst etwas zu diesem Thema geschrieben.

Im ersten Teil des Artikel wird Stück für Stück einen nicht optimierender Compiler entwickeln für eine C-ähnlich Sprache. Rein sollen if, Schleifen, Variablen und Funktionen. Dabei wird nur Wissen über x86 Assembler mit AT&T Syntax und Standard C++ voraus gesetzt. Auf Compiler Theorie wie zum Beispiel Grammatiken wollte ich nicht eingehen um die Größe des Artikels nicht erneut zu sprengen und um zu verhindern, dass es zu trocken wird.

Im zweiten Teil wollte ich dann Parser und ASM Generator trennen und zeigen wie man einen highlevel Optimizer bauen könnte (nur einige groben Ideen). Eventuell einen billigen Inliner in den vorher gebauten Compiler einbauen um als Beispiel zu dienen.

Wie findet ihr was ich bis jetzt habe?

Ob ich ihn zu Ende schreibe weiß ich noch nicht. Hängt von meiner Zeit ab und was ihr von dem haltet was ich bis jetzt habe.

==============

Einfachstes Programm

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 dieser muss eine '1' sein. Ein korrektes (und sogar das einzig korrekte) Programm wäre also:

1

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

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

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	if(start != end){
		if(*start == '1'){
			out<<"pushl $1"<<endl;
			out<<"call print_int"<<endl;
			out<<"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;
	out<<"prog:"<<endl;

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

	if(parser_one(pos, end, out)){
		if(pos != end)
			cerr<<"Unexpected trailing characters at end of file"<<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:

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

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 überspringt.

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

In einem komplexerem Compiler würde diese Funktion auch Kommentare überspringen.

Der Rest des Compiler ändert nur leicht:

bool parse_one(const char*&pos, const char*end, std::ostream&out){
	skip_spaces(pos, end);		// Ich bin neu (1)
	if(start != end){
		if(*start == '1'){
			out<<"pushl $1"<<endl;
			out<<"call print_int"<<endl;
			out<<"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_isterator<char>(in.rdbuf()), istreambuf_iterator<char>(), back_inserter(source_code));

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

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

	if(parser_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 aus zuschreiben, allerdings nur wenn man will. 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){
	skip_spaces(pos, end);
	const char*start = pos;
	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0')
			return true;
	}
	pos = start;
	return false;
}

Nun müssen wir nur noch parse_one anpassen.

void write_print_one_code(std::ostream&out){
	out<<"pushl $1"<<endl;
	out<<"call print_int"<<endl;
	out<<"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);
	else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
	return true;
}

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 schon können wir Programme wie folgendes übersetzen.

one

Jedoch hat sich bereits der erste Bug eingeschlichen. Betrachtet mal:

onehundred

Das Program wird zwar wie erwünscht abgelehnt aber nicht aus dem richtigem Grund. Der Compiler ließ nur bis zum Ende von "one", übersetzt dies dann auch und das Program wird nur abgelehnt weil der Compiler nix mit "hundred" hinter dem Ende des erkannten Programs anzufangen weiß. 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 dies schön mit Leerzeichen getrennt wird. Dies hat auch seinen guten Grund denn dadurch werden Zweideutigkeiten ausgeräumt. Allerdings übersetzt ein C-Compiler auch "1+2" onwohl zwischen der "1" un dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Wörter eigene Funktionen schreiben allerdings geht es auch einfacher:

bool ignore(const char*&pos, const char*end, const char*what){
	skip_spaces(pos, end);
	const char*start = pos;
	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			--what;
			if(isalpha(*what))
				return !isalnum(*pos);
			else
				return true;
		}
	}
	pos = start;
	return false;
}

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 Program 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 Program aus einer Reihe von Befehlen und darum sollte die Funktion die ein Program liest auch nur dies tuen. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtilich 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){
	if(ignore(pos, end, "print")){
		int n;
		if(read_number(pos, end, n)){
			out<<"pushl $"<<n<<endl;
			out<<"call print_int"<<endl;
			out<<"addl $4, %esp"<<endl;
			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 Hexadecimal oder Octal Zahlen beibringen. Wir wollen uns aber mit einfachen decimal Zahlen begnügen.

In welche und wie viele Unterfunktionen und welche 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 passendend Funktionsnamen kennt.

Taschenrechner

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

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 tuen. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumentet 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

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

bool parse_command(const char*&pos, const char*end, ostream&out){
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out<<"pushl %eax"<<endl;
			out<<"call print_int"<<endl;
			out<<"addl $4, %esp"<<endl;
			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){
	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;
				out<<"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;
				out<<"pop %eax"<<endl;
			}else
				break;
		}
		return true;
	}else
		return false;
}

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

Die Multiplikation wird ähnlich behandelt.

bool parse_term(const char*&pos, const char*end, ostream&out){
	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;
				out<<"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;
		}
		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){
	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;
	return true;
}

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 evident sein allerdings solche rekursiven Definitionen stellen an sich kein Problem dar. Man muss die entsprechende Funktion legentlich rekusiv aufrufen.

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

	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;
	return true;
}

Variablen

If und Schleifen

Funktionen

Trennung von Parser und Code Generator : Code Baum

Optimizer

[GPC]

Okay, ich habe keine Ahnung von Compilerbau und nur normale Kenntnisse bzgl. Parserbau, aber mir gefällt's bis jetzt sehr gut! In der Artikelverteilung hab ich den Artikel mal auf "In Arbeit" gesetzt.

[CStoll]

Ich will dich ja nicht in deinem Tatendrang bremsen, aber bei sowas stellen sich mir instinktiv die Haare hoch:

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

Wenn du schon mit vector<>en arbeitest, dann nimm doch bitte auch die Iteratoren dazu - alternativ könntest du auch mit std::string hantieren, der bietet eingebauten Zugriff auf char*.

Btw, sind die Programmschnipsel nur hingeschrieben oder tatsächlich getestet?

[Ben04]

CStoll schrieb:

[/cpp]Wenn du schon mit vector<>en arbeitest, dann nimm doch bitte auch die Iteratoren dazu - alternativ könntest du auch mit std::string hantieren, der bietet eingebauten Zugriff auf char*.

std::string bietet kein push_back und somit auch keinen back_inserter. vector ist der einzige Container mit dem das geht. Mittels getline und EOF als Zeilenumbruchsbuchstaben könnte es auch mit getline und string gehen. Würden dir dann die Haare nicht zu Berg stehen?

Iteratoren will ich keine nutzen da sie nur umständlich wären und nicht wirklich etwas bringen würden außer unleserlichen Fehlermeldungen.

CStoll schrieb:

Btw, sind die Programmschnipsel nur hingeschrieben oder tatsächlich getestet?

Teils teils. Den Compiler habe ich bereits übersetzt (zu mindest manche Versionen) und ich hab angeschaut ob der ASM Code stimmt. Durch den Assembler habe ich aber noch nichts gejagt. Hast du einen Fehler erblickst?

PS: Weiß jemand wie man dem MinGW beibringen kann keine '_' vor die C Funktionsnamen zu packen? Oder alternative der Linux Version dies auch zu tun?

[CStoll]

Ben04 schrieb:

CStoll schrieb:

[/cpp]Wenn du schon mit vector<>en arbeitest, dann nimm doch bitte auch die Iteratoren dazu - alternativ könntest du auch mit std::string hantieren, der bietet eingebauten Zugriff auf char*.

std::string bietet kein push_back und somit auch keinen back_inserter. vector ist der einzige Container mit dem das geht. Mittels getline und EOF als Zeilenumbruchsbuchstaben könnte es auch mit getline und string gehen. Würden dir dann die Haare nicht zu Berg stehen?

Klar bietet std::string eine Methode push_back().

CStoll schrieb:

Btw, sind die Programmschnipsel nur hingeschrieben oder tatsächlich getestet?

Teils teils. Den Compiler habe ich bereits übersetzt (zu mindest manche Versionen) und ich hab angeschaut ob der ASM Code stimmt. Durch den Assembler habe ich aber noch nichts gejagt. Hast du einen Fehler erblickst?

Ich habe mir nicht alles angesehen, aber bei der allerersten Compiler-Version bin ich über einen unbekannten Bezeichner 'start' gestolpert - und technisch dürfte der auch nichts erkennen, weil 'pos' (bzw. start) nicht weitergeschoben wird.

[Ben04]

CStoll schrieb:

Klar bietet std::string eine Methode

Kapitel "21.3 Template class basic_string" des ISO Standards ist da anderer Meinung. Falls es ein push_back gibt handelt es sich um eine Compilererweiterung.

CStoll schrieb:

Ich habe mir nicht alles angesehen, aber bei der allerersten Compiler-Version bin ich über einen unbekannten Bezeichner 'start' gestolpert - und technisch dürfte der auch nichts erkennen, weil 'pos' (bzw. start) nicht weitergeschoben wird.

Danke werde ich verbessern.

[CStoll]

Ben04 schrieb:

CStoll schrieb:

Klar bietet std::string eine Methode

Kapitel "21.3 Template class basic_string" des ISO Standards ist da anderer Meinung. Falls es ein push_back gibt handelt es sich um eine Compilererweiterung.

Hmm, den Standard habe ich leider nicht griffbereit - aber daß push_back() keine Standardmethode sein sollte, habe ich noch nie gehört

extra im Standard Draft nachgesehen hat:
21.2.2

The template class basic_string conforms to the requirements of a
Sequence, as specified in (_lib.sequence.reqmts_). Additionally,
because the iterators supported by basic_string are random access
iterators (_lib.random.access.iterators_), basic_string conforms to
the the requirements of a Reversible Container, as specified in
(_lib.container.requirements_).

(und unter _lib.sequence.reqmts_ wird auch push_back() aufgezählt)

Edit: Aber letztlich liegt der Schwerpunkt auch nicht auf dem drunterliegenden Container - und die Art, wie die Datei eingelesen werden soll, ist eher zweitrangig. Und nach dem Einlesen wird push_back() auch nicht mehr benötigt.

[Ben04]

http://www.ishiboo.com/~nirva/c++/C++STANDARD-ISOIEC14882-1998.pdf
(Wenn dies auch hier im versteckten Magazin Teil verboten ist, dann schau dir den Link an und editiere ihn dann weg.)

string ist auch der einzige Container der kein push_back hat. Der von dir zitierte Abschnitt sagt auch nichts darüber aus. Da steht nur, dass es begin, end, rbegin und rend gibt und, dass die Iteratoren random access sind und falls es ein push_back gibt, dass dieses in constanter Zeit laufen muss.

In 23.1.1/12 steht es noch deutlicher. Da sind die Container aufgelistet welche ein push_back haben : deque, vector und list. basic_string ist nicht aufgelistet. Wie bereits gesagt ist in 21.3 push_back auch nicht als Methode von basic_string aufgelistet.

Leider ist dies auch nicht nur ein Papiertiger sondern libstdc++ bot in einigen Versionen kein push_back an. Die neuste Version hat aber ein push_back.

[CStoll]

Ben04 schrieb:

http://www.ishiboo.com/~nirva/c++/C++STANDARD-ISOIEC14882-1998.pdf
(Wenn dies auch hier im versteckten Magazin Teil verboten ist, dann schau dir den Link an und editiere ihn dann weg.)

string ist auch der einzige Container der kein push_back hat. Der von dir zitierte Abschnitt sagt auch nichts darüber aus. Da steht nur, dass es begin, end, rbegin und rend gibt und, dass die Iteratoren random access sind und falls es ein push_back gibt, dass dieses in constanter Zeit laufen muss.

In 23.1.1/12 steht es noch deutlicher. Da sind die Container aufgelistet welche ein push_back haben : deque, vector und list. basic_string ist nicht aufgelistet. Wie bereits gesagt ist in 21.3 push_back auch nicht als Methode von basic_string aufgelistet.

Also jetzt hast du es endgültig geschafft, mich zu verwirren - in der Auflistung der String-Elemente ich push_back() enthalten (ganz unten auf Seite 385), bei der Erklärung der String-Methoden wird's nicht erwähnt, genausowenig taucht wird der Erklärung der Containermethoden basic_string erwähnt.

(und bei Jossutis wurde push_back() auch für Strings erklärt)

[Ben04]

Beziehst du dich auf den von mir geposteten Link? Das ist die original C++98 Version. Vielleicht hast du ja die von 2003 und da wurde dies vielleicht verbessert.

Auf Seite 385 finde ich jedenfalls nichts.

EDIT2: Quatsch, ich kann nicht lesen. Hab ihn auch Seite 385 tatsächlich übersehen. Allerdings In der Aufzählung bei den Containern fehlt basic_string in beiden Versionen.

Schlussfolgerung : string::push_back nicht benutzen. Irgendwer wird ein Problem damit haben.

[Ben04]

Bis zu den ifs wurde debugt. Wer da noch ein Problem mit dem Code findet bitte melden. Am Text werde ich noch arbeiten allerdings wenn hier wer eine gute Idee hat nur her damit. Unklare Stellen bitte melden.

Dann bleibt noch das Underscoreproblem des MinGW. Im Moment hab ich vor für rt.c eine Linux Version zu machen wo die Namen auch mit einem Underscore anfangen. Ist aber nicht sonderlich schön.

===

Einfachstes Program

Um anzufannen 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 Program besteht aus einer einzigen Ziffer und dieser muss eine '1' sein. Ein korrektes (und sogar das einzig korrekte) Program wäre also:

1

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 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
		<<".def _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 file"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Auch wenn dieses Program 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 fogendermaß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

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 überspringt.

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

In einem komplexerem Compiler würde diese Funktion auch Kommentare überspringen.

Der Rest des Compiler ändert 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
		<<".def _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 Programs befinden können.

Als nächstes werden wir es möglich machen, die 1 auszuschreiben, allerdings nur wenn man will. 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){
	skip_spaces(pos, end);
	const char*start = pos;
	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0')
			return true;
	}
	pos = start;
	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);
	else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
	return true;
}

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

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

one

Jedoch hat sich bereits der erste Bug eingeschlichen. Betrachtet mal:

onehundred

Das Program wird zwar wie erwünscht abgelehnt aber nicht aus dem richtigem Grund. Der Compiler ließ nur bis zum Ende von "one", übersetzt dies dann auch und das Program wird nur abgelehnt weil der Compiler nix mit "hundred" hinter dem Ende des erkannten Programs anzufangen weiß. 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 dies schön mit Leerzeichen getrennt wird. Dies hat auch seinen guten Grund denn dadurch werden Zweideutigkeiten ausgeräumt. Allerdings übersetzt ein C-Compiler auch "1+2" onwohl zwischen der "1" un dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Wörter eigene Funktionen schreiben allerdings geht es auch einfacher:

bool ignore(const char*&pos, const char*end, const char*what){
	skip_spaces(pos, end);
	const char*start = pos;
	while(pos != end && *pos == *what){
		++what;
		++pos;
		if(*what == '\0'){
			--what;
			if(isalpha(*what))
				return !isalnum(*pos);
			else
				return true;
		}
	}
	pos = start;
	return false;
}

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 Program 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 Program aus einer Reihe von Befehlen und darum sollte die Funktion die ein Program liest auch nur dies tuen. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtilich 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){
	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;
			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 Hexadecimal oder Octal Zahlen beibringen. Wir wollen uns aber mit einfachen decimal Zahlen begnügen.

In welche und wie viele Unterfunktionen und welche 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 passendend Funktionsnamen kennt.

Taschenrechner

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

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 tuen. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumentet 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

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

bool parse_command(const char*&pos, const char*end, ostream&out){
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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){
	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;
		}
		return true;
	}else
		return false;
}

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

Die Multiplikation wird ähnlich behandelt.

bool parse_term(const char*&pos, const char*end, ostream&out){
	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;
		}
		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){
	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;
	return true;
}

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 evident sein allerdings solche rekursiven Definitionen stellen an sich kein Problem dar. Man muss die entsprechende Funktion legentlich rekusiv aufrufen.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	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;
	return true;
}

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 sich auf dem Stack gepackt und keine kommen in statischen Speicher. Um die Sache noch weiter zu vereinfachen sind alle Variablen vom Typ int. Dies ist eine zimlich starke Einschränkung aber irgendwie muss man 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 ist möglich 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ück gegeben 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 Erfolgsasusichten von create_var aussagt da Variablen verdeckt werden können.
• get_var_address gibt die Stackaddresse der Variable aus. Addressen 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 Stream 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 bischen mit Schleifen auskennt der weiß, dass da Sprungaddressen 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 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 Summe 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 Funtktion 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
		<<".def _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 Akoladen 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){
	if(ignore(pos, end, "{")){
		env.var.push_scope();

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

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

bool parse_command(Env&env, const char*&pos, const char*end){
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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 Akoladen 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
}

Auch wenn das schon nicht schlecht aussieht haben wir doch einen wesentlichen Bestantheil 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){
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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))
				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;
					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 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){
	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;
	return true;
}

Langsam aber sicher entwickelt sich unsere Sprache weiter. Ein Program 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
}

Strings Home Edition

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 Kaptiels 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.

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){
	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;
		return true;
	}else
		return false;
}

Als nächstes brauchen wir eine Möglichkeit Zeichenketten in den Code einzufügen. Diese werden 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 nicht auf die Implementation angeben. Es gibt den offensischttlichen Weg diese Klasse zu implementieren man kann aber auch versuchen ein paar Bytes zu sparen indem man versucht die Strings so anzuordnen, dass sie sich überlappen. Dies geht natürlich nur solange die original 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.

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
		<<".def _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.

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

bool parse_print(Env&env, const char*&pos, const char*end){
	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, ","));
		return true;
	}else
		return false;

}

bool parse_command(Env&env, const char*&pos, const char*end){
	if(parse_print(env, pos, end)){
		return true;
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out))
				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;
					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
}

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.

bool parse_if(Env&env, const char*&pos, const char*end){
	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;
				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){
	if(parse_print(env, pos, end)){
		return true;
	}else if(parse_if(env, pos, end)){
		returnt true;
	}else 
		...
}

An sich wars das schon allerdings ist ein Vergleich ob denn nun zwei Werte gleich sind noch zimlich 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.

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)){
		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;
			return true;
		}
	}
	return false;
}

bool parse_boolean_expression(Env&env, const char*&pos, const char*end){
	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;
				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;
}

In parse_if wird natürlich parse_boolean_expression verwendet und nicht parse_numeric_expression. 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){
	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;
					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;
			}
		}
	}
	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 aufgerufen.

bool parse_while(Env&env, const char*&pos, const char*end){
	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;
				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 : \n"
	var p
	p = 2
	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, " is prime \n"
		}
		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 nemmen. Es hat also sowohl Vor- wie auch Nachteile.

Funktionen

FuncManager

Env <-> FuncEnv

parse_program

Trennung von Parser und Code Generator : Code Baum

Optimizer

[phlox81]

Sehr guter Artikel, aber kleine Anregung: Wie wärs wenn du 2 draus machst?
Der Artikel ist jetzt schon sehr lang (auf dieser Seite befinden sich bis hier nur dein Artikel, und meine drei Zeilen ;))
Ansonsten eine super Sache

[Jester]

Noch ne kleine Idee zur Einleitung.

"Man kann sich einen Compiler vorstellen, der einfach für jeden Code die passende Übersetzung abgespeichert hat. Wenn also ne Eingabe kommt muß der sich nur noch aus ner großen Tabelle die passende Übersetzung raussuchen und ausgeben.

Natürlich ist jedem klar, dass sowas nicht funktionieren kann, weil a) die Programmgröße beschränkt wäre und b) ein immenser Speicherbedarf da wäre.

Lustigerweise funktioniert das Prinzip aber trotzdem im Kleinen: Für kleine Codestücke die richtige Übersetzung abspeichern. Jetzt die Eingabe lesen und immer wenn man ein passendes Codestück gefunden hat die korrekte Übersetzung in der Tabelle nachschlagen. :)"

Mir gefällt diese Art der Sichtweise auf den Compilerbau. Vielleicht hilft es dem ein oder anderen direkt zu Anfang ne Idee zu bekommen, wie ein Compiler in etwa funktioniert. Die Anführungszeichen dienen nur zur Abgrenzung vom restlichen Text dieses Postings... das hier soll ein inhaltlicher Vorschlag sein, die Formulierung kann man sicherlich verbessern.

[Ben04]

Ich will den Teil mit dem konkreten Code nicht trennen da der nur in einem Teil Sinn macht. Der Funktionsteil kommt also noch sicher.

Die Trennung Parser <-> Baum <-> Generator muss man IMHO auch an einem Beispiel machen da es sonst zu abstrakt wird und es gibt auch ganz konkret ein paar Sachen die man wirklich falsch machen kann. So sollte man den Baum nicht mit einfacher Vererbung erstellen sondern das Visitor-Pattern ist ein muss und zwar nicht das einfache sondern ein boost.variant ähnliches. Boost.variant selbst kann man leider nicht einsetzen da das die Compilezeit sprengt und auch schon bei einfachen Sachen Compiler zerbrechen lässt.

Beim Optimizer wollte ich nur die großen Ideen erklären und vielleicht eine etwas konkreter.

Ich könnte also nach dem Funktionsteil trennen. Ob der zweite Teil dann geschrieben wird hängt dann vom Feedback ab. Beim AVL Baum hatte ich irgendwie das Gefühl gehabt keiner hätte den zweiten Teil gelesen, höchstens gebookmarkt.

[Fake oder Echt]

Ich weiß, dass meine Frage nicht wirklich hier rein passt, aber hat jmd. von euch einen Link zu einem Tutorial in dem das Programmieren eines Compilers beschrieben wird? (bevorzugt: Deutsch und in C/C++)

[phlox81]

BitWax schrieb:

Ich weiß, dass meine Frage nicht wirklich hier rein passt, aber hat jmd. von euch einen Link zu einem Tutorial in dem das Programmieren eines Compilers beschrieben wird? (bevorzugt: Deutsch und in C/C++)

Bist du jetzt komplett merkbefreit?

[Fake oder Echt]

phlox81 schrieb:

BitWax schrieb:

Ich weiß, dass meine Frage nicht wirklich hier rein passt, aber hat jmd. von euch einen Link zu einem Tutorial in dem das Programmieren eines Compilers beschrieben wird? (bevorzugt: Deutsch und in C/C++)

Bist du jetzt komplett merkbefreit?

Nein, aber da der Artikel noch nicht fertig ist, wollte ich einfach mal wissen, ob da jmd. ne Quelle hat.

[Ben04]

Vom Inhalt her sollte diese Version nun ziemlich komplett sein. Ich werde sicherlich noch einige Formulierungen ändern und hier und da ein paar Sachen verdeutlichen. Der Code muss noch getestet werden und vervollständigt werden. Eine Einleitung muss auch noch her.

Sollte irgendwo einen ernsthaften Inhaltsfehler sein oder irgendwo etwas ganz wichtiges fehlen meldet euch bitte jetzt. Da ich den Artikel eh noch ein-, zweimal durchgehen muss kann ich dafür sorgen, dass der Faden des Artikels konsistent bleibt.

====================================

Inhaltsverzeichnis

Einleitung

Backtracking

Bei einem Übersetzer handelt es sich um ein Programm das eine Textdatei einließt und dann übersetzt. Es sollte offensichtlich sein, dass das Einlesen der einzeln Zeichen ein wichtiger Baustein ist. Es muss möglich sein in der Datei zurück zu spulen da ein Compiler oft einfach ein paar Sachen durchprobiert 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 das auch nicht klappt 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. Es gibt 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 Stream schreiben welche immer nur den absoluten Minimum im Speicher halten der vielleicht benötigt wird. Man muss ja nicht überall hin spulen können. Es reicht an ein paar paar Stellen spulen zu können. Dies ermöglich 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 die Datei kurzerhand einfach in den Speicher kopieren. Eine effiziente Implementierung eines Stroms wäre ein Thema das in einen anderen Artikel gehört. Unser primitiver Stream wird aus zwei Zeigern bestehen. Einer zeigt auf das Zeichen welches als nächstes verarbeitet werden wird und der andere auf das erste Zeichen nach dem Puffer. 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 Übersetzern sind diese Eingabestrings 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.

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 dieser 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 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
		<<".def _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 file"<<endl;
		else
			out<<"ret"<<endl;
	}
}

Auch wenn dieses Program 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 fogendermaß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 -fleading-underscore out.s rt.c -o out.exe

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 überspringt.

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

In einem komplexerem Compiler würde diese Funktion auch Kommentare überspringen. Der Rest des Compiler ändert 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
		<<".def _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 Programs befinden können.

Als nächstes werden wir es möglich machen die 1 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);
	else {
		cerr<<"Unknown command"<<endl;
		return false;
	}
	return true;
}

Wer genau hinschaut bemerkt, dass sich in parse_one kein skip_spaces mehr befindet. Dadurch, dass wir in ignore einen Aufruf plaziert 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. Betrachtet mal:

onehundred

Das Program wird zwar wie erwünscht abgelehnt aber nicht aus dem richtigem Grund. Der Compiler ließ nur bis zum Ende von "one", übersetzt dies dann auch und das Program wird nur abgelehnt weil der Compiler nichts mit "hundred" hinter dem Ende des erkannten Programs anzufangen weiß. 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 dies schön mit Leerzeichen getrennt wird. Dies hat auch seinen guten Grund denn dadurch werden Zweideutigkeiten vermieden. Allerdings übersetzt ein C-Compiler auch "1+2" onwohl zwischen der "1" un dem "+" kein Leerzeichen ist. Man könnte nun für Zahlen und Wörter eigene Funktionen schreiben. Die eine würde auch 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.

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 Program 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 Program aus einer Reihe von Befehlen und darum sollte die Funktion die ein Program liest auch nur dies tuen. parse_program gehen die Details eines Befehls nichts an. Dadurch halten wir die Funktionen klein und den Compiler übersichtilich 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){
	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;
			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 Hexadecimal oder Octal Zahlen beibringen. Wir wollen uns aber mit einfachen decimal Zahlen begnügen.

In welche und wie viele Unterfunktionen und welche 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 passendend Funktionsnamen kennt.

Taschenrechner

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

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 tuen. Jede Minifunktion schreibt den Rückgabewert in eax. Eine Funktion mit mehreren Argumenten wertet die Argumentet 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 [url="http://de.wikipedia.org/wiki/Erweiterte_Backus-Naur-Form"]EBNF[/url] suchen. In diesem Artikel werde ich aber nicht weiter darauf eingehen.

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

bool parse_command(const char*&pos, const char*end, ostream&out){
	if(ignore(pos, end, "print")){
		if(parse_expression(pos, end, out)){
			out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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){
	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;
		}
		return true;
	}else
		return false;
}

Diese Funktion sieht auf den ersten Blick bedrohlich aus allerdings ist sie an sich recht einfach. Die einzelne Terme der Summe werden nacheinnander 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){
	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;
		}
		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){
	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;
	return true;
}

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 evident sein allerdings solche rekursiven Definitionen stellen an sich kein Problem dar. Man muss die entsprechende Funktion legentlich rekusiv aufrufen.

bool parse_factor(const char*&pos, const char*end, ostream&out){
	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;
	return true;
}

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 sich auf dem Stack gepackt und keine kommen in statischen Speicher. Um die Sache noch weiter zu vereinfachen sind alle Variablen vom Typ int. Dies ist eine zimlich 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 ist möglich 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ück gegeben 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 Erfolgsasusichten von create_var aussagt da Variablen verdeckt werden können.
• get_var_address gibt die Stackaddresse der Variable aus. Addressen 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 Stream 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 bischen mit Schleifen auskennt der weiß, dass da Sprungaddressen 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 Summe 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 Funtktion 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
		<<".def _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 Akoladen 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){
	if(ignore(pos, end, "{")){
		env.var.push_scope();

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

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

bool parse_command(Env&env, const char*&pos, const char*end){
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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 Akoladen 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
}

Auch wenn das schon nicht schlecht aussieht haben wir doch einen wesentlichen Bestantheil 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){
	if(ignore(pos, end, "print")){
		if(parse_expression(env, pos, end)){
			env.out
				<<"pushl %eax"<<endl
				<<"call _print_int"<<endl
				<<"addl $4, %esp"<<endl;
			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))
				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;
					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){
	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;
	return true;
}

Langsam aber sicher entwickelt sich unsere Sprache weiter. Ein Program 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
}

Strings Home Edition

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 Kaptiels 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.

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){
	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;
		return true;
	}else
		return false;
}

Als nächstes brauchen wir eine Möglichkeit Zeichenketten in den Code einzufügen. Diese werden 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 nicht auf die Implementation angeben. Es gibt den offensischttlichen Weg diese Klasse zu implementieren man kann aber auch versuchen ein paar Bytes zu sparen indem man versucht die Strings so anzuordnen, dass sie sich überlappen. Dies geht natürlich nur solange die original 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.

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
		<<".def _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.

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

bool parse_print(Env&env, const char*&pos, const char*end){
	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, ","));
		return true;
	}else
		return false;

}

bool parse_command(Env&env, const char*&pos, const char*end){
	if(parse_print(env, pos, end)){
		return true;
	}else if(ignore(pos, end, "var")){
		string identifier;
		if(read_identifier(pos, end, identifier)){
			if(env.var.create_var(identifier, env.out))
				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;
					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
}

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 wieder zu verwenden. If nutzt einfach wie überall eax und nimmt natürlich auch ein int als Bedingung.

bool parse_if(Env&env, const char*&pos, const char*end){
	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;
				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){
	if(parse_print(env, pos, end)){
		return true;
	}else if(parse_if(env, pos, end)){
		returnt true;
	}else 
		...
}

An sich wars das schon allerdings ist ein Vergleich ob denn nun zwei Werte gleich sind noch zimlich 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)){
		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;
			return true;
		}
	}
	return false;
}

bool parse_boolean_expression(Env&env, const char*&pos, const char*end){
	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;
				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;
}

In parse_if wird natürlich parse_boolean_expression verwendet und nicht parse_numeric_expression. Dadurch ist die doppelte Bedeutung von "=" auch nicht zwiedeutig. In einer Bedingung ist es ein Vergleich und sonst eine Zuweisung.

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){
	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;
					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;
			}
		}
	}
	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 aufgerufen.

bool parse_while(Env&env, const char*&pos, const char*end){
	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;
				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 : \n"
	var p
	p = 2
	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, " is prime \n"
		}
		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 nemmen. 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.

Funktionen

Funktion sind die Bausteine jedes complexeren Programms. Darum will ich sie auch in diesem Artikel nicht auslassen. Mit Funktionen kann man an sich was die Complexitä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 Einfacheit 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 declariert werden. Sie können nicht überladen werden. Als Aufrufskonvention werden wir eine verwenden die des GCCs verwenden. Dadurch können wir auch ohne weiteres gegen C Code linken. Der Unterschied darin, dass 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 recyclen. Der Rückgabewert befindet sich in eax.

Als erstes brauchen wir eine Funktion um die Informationen zu verwalten. Ich werde wieder einmal nur auf die Klassenschnittstelle eingehen und auf eine Implementierung [url="foobar"]verweisen.[/url]

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 Argumente 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 Mecanismus benötigen.

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 userer 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 Env(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.

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){
	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;
	return false;
}

bool parse_function(Env&env, const char*&pos, const char*end){
	string func_name;
	if(!read_identifier(pos, end, func_name))
		return false;
	if(!ignore(pos, end, "("))
		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, ";")){
		VarManager var;

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

		env.out
			<<".def "<<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);
		return parse_block(fenv, pos, end);
	}
}

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 einließt.

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(env, pos, ")"))
				do{
					if(!parse_numeric_expression(env, pos, end))
					return false;
					env.out<<"pushl %eax"<<endl;
				}while(ignore(env, pos, ","));

			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;
				guard.no_backtrack();
				return true;
			}
		}
		return false;
	}
}

Diese Funktion muss nun mit zwei anderen verschraubt werden. Eine Funktion kann nämlich innerhalb eines Ausdrucks aufgerufen werden aber auch als Befehl. Es müssen also [i]parse_factor* und parse_command verändert werden.

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 lesen.

bool parse_return(Env&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 %esp"<<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.

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 von 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 welche die gleichen Informationen enthält. Der Generator nimmt diesen Baum dann und generiert den entsprechenden Code. Dies macht Arbeitsteilung 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 Optimisierungen durch zu führen. Ich wüßte nicht wie man dem Übersetzer so wie er hier vorgestellt wurde bei bringen 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 berrechen. 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.

Schlussbemerkung

Ziel dieses Artikels war es den Leser in das Gebiet des Übersetzerbaus 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 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]

Wow, da kam ja jetzt echt einiges an Material zusammen

Also ich kann dem Inhalt des Artikels gut folgen, obwohl ich Null Ahnung vom Compilerbau habe. Von dem her gesehen gefällt mir der Artikel gut. Allerdings kann ich durch meine Unwissenheit auch keine echte Kritik anbringen

Den Code habe ich bisher nur überflogen. Wenn dir partout keine Einleitung einfällt, kann ich dir dabei dann noch helfen.

Was hältst du eigentlich davon, den Artikel in zwei Teile aufzusplitten? So bei "Strings Home Edition" wäre imo eine gute Möglichkeit.

[Artchi]

[Ben04]

GPC schrieb:

Also ich kann dem Inhalt des Artikels gut folgen, obwohl ich Null Ahnung vom Compilerbau habe. Von dem her gesehen gefällt mir der Artikel gut. Allerdings kann ich durch meine Unwissenheit auch keine echte Kritik anbringen

Danke

GPC schrieb:

Den Code habe ich bisher nur überflogen. Wenn dir partout keine Einleitung einfällt, kann ich dir dabei dann noch helfen.

Falls du einen guten Vorschlag hast nur raus damit. Jesters wäre gut wenn es um die formale Theorie ginge. Da dies aber an der Zielgruppe vorbei geht würde diese Einleitung einen falschen Eindruck erwecken.

GPC schrieb:

Was hältst du eigentlich davon, den Artikel in zwei Teile aufzusplitten? So bei "Strings Home Edition" wäre imo eine gute Möglichkeit.

Wie schon gesagt, der sollte ursprünglich noch länger werden. Ich werde ihn nicht in zwei schneiden da es IMHO keine Stelle gibt an der man sinnvoll trennen könnte.