Die eigene Programmiersprache

12. Oktober 2014

Viele Programmierer werden wahrscheinlich schon einmal bemerkt haben, dass die bisher verwendeten Programmiersprachen immer in irgendeiner Hinsicht ein wenig unzureichend waren.
Im fortgeschrittenen Zustand kommen dann einige Programmierer auf die Idee, eine eigene Sprache zu entwerfen. Aber das gestaltet sich als schwierig, denn es gibt so viele Möglichkeiten und meistens liegen keinerlei Vorerfahrungen vor.
Eine wirkliche umfangreiche und komplexe Programmiersprache ist natürlich das Werk von Jahren und in der Regel auch von mehreren Personen. Aber eine kleine Sprache, um ein wenig Übung zu bekommen, ist leicht gemacht.

Wie schon angesprochen liegen uns dafür mehrere Möglichkeiten vor:

  1. Unsere Sprache in C/C++ übersetzen und dann den Rest dem jeweiligen Compiler überlassen
  2. Wir benutzen etwas wie LLVM und übersetzen unsere Sprache in ein entsprechendes Vor-Kompilat, dass wir dann dem LLVM Framework übergeben
  3. Wir übersetzen unsere Sprache selbst in Assembler

Der Aufbau unseres Assembler-Backends

Wir benutzen dabei den Assembler-Dialekt GAS (GNU Assembler).

Beinahe jeder Befehl in Assembler nimmt ein bis zwei Operanden entgegen, dieser Operand kann ein Register, eine Zahl, eine Adresse oder sogar ein Zeiger sein.
Dafür verwenden wir die Struktur Operand:

	struct Operand {
		virtual std::string toString() const = 0;
	};

Da Zahlen in GAS das Prefix $ haben, um sie eindeutig zu identifizieren, benutzen wir die Struktur Numeric, die sich von Operand ableitet:

	struct Numeric : public Operand {
		int value;

		explicit Numeric(int val);
		virtual std::string toString() const override;
	};

Für die angesprochenen Register schreiben wir die gleichnamige Struktur Register. Dabei vordefinieren wir die regulären 32 Bit Register %eax, %ebx, %ecx, %edx bzw. die 64 Bit Register %rax, %rbx, %rcx, %rdx mit AX, BX, CX, DX:

	struct Register {
		static const Register AX;
		static const Register BX;
		static const Register CX;
		static const Register DX;

		const std::string id;

		explicit Register(const std::string&);
	};

Und zu guter letzt noch die Struktur für die Zeiger/Adressen, wie der für den Stack, den Basis Zeiger und dem Index Zeiger:

	struct Pointer {
		static const Pointer Stack;
		static const Pointer Index;
		static const Pointer Base;

		const std::string id;

		explicit Pointer(const std::string&);
	};

Da wir auf Zeiger, wie auch auf Register, ein Offset rechnen können, legen wir dazu noch eine weitere Struktur an, AddrOf:

	struct AddrOf : public Operand {
		std::string id;
		int offset = -1;

		explicit AddrOf(const Register&, int the_offset);
		explicit AddrOf(const Pointer&, int the_offset);

		virtual std::string toString() const override;
	};

Zudem benutzen wir die folgenden Assembler-Befehle:

Außerdem wäre es nützlich, wenn wir sogenannte Labels handhaben könnten. Labels sind etwa Adressen, zu denen „gesprungen“ werden kann. Dazu benötigen wir also eine Möglichkeit, Labels hinzuzufügen und zu diesen zu springen. Außerdem können Sprünge eine Bedingung haben, wie „Springe nur, wenn … / wenn nicht … „. Dazu benötigen wir also auch noch eine geeignete Struktur:

	struct Jump {
		static const Jump Immediate;
		static const Jump IfZero;
		static const Jump IfEqual;
		static const Jump IfNotEqual;
		static const Jump IfGreater;
		static const Jump IfGraterEqual;
		static const Jump IfLess;
		static const Jump IfLessEqual;
		static const Jump IfAbove;
		static const Jump IfBelow;

		const std::string id;

		explicit Jump(const std::string& id);
	};

Nun haben wir alle benötigten Strukturen und können unsere Assembler Klasse erstellen:

	struct Assembly {
		std::ostream& _output;

		Assembly(std::ostream&, const std::string&);
		virtual ~Assembly();

		void add(std::unique_ptr<Operand> o1, std::unique_ptr<Operand> o2) const;
		void sub(std::unique_ptr<Operand> o1, std::unique_ptr<Operand> o2) const;

		void inc(std::unique_ptr<Operand> o1) const;
		void dec(std::unique_ptr<Operand> o1) const;

		void ret() const;
		void jump(const Jump&, const std::string&) const;
		void label(const std::string&) const;

		void compare(std::unique_ptr<Operand> o1, std::unique_ptr<Operand> o2) const;
		void lea(std::unique_ptr<Operand> o1, std::unique_ptr<Operand> o2) const;
		void move(std::unique_ptr<Operand> o1, std::unique_ptr<Operand> o2) const;

		void push(std::unique_ptr<Operand> o1) const;
		void pop(std::unique_ptr<Operand> o1) const;
		void pop() const;

		void call(const std::string&) const;
	};

Nun haben wir also diesen Header:

Die op_code Funktionen sind dabei Vereinfachungen um eine Zahl, ein Register, einen Zeiger oder eine Adresse auf letztere zu erstellen.

Und wir haben diesen Source:

Zeit für einen ersten Test

Wir wollen ein erstes Programm per Hand zusammen stellen, wie das folgende:

a = 42
b = a

c -> a
d <- c

print a
print b
print c
print d

Das ist unsere spätere Syntax, die jetzt aber noch soweit außen vor gelassen werden kann. Es geht nur um die Logik dahinter:

  1. Wir setzen die Variable a auf den Wert 42
  2. Wir setzen die Variable b auf den Wert von Variable a
  3. Unsere Variable c zeigt auf die Variable a
  4. Die Variable d dereferenziert den Zeiger c, erhält also den Wert von Variable a
  5. Wir geben die Werte von a, b, c und d aus

Dazu brauchen wir zunächst weitere Grund Strukturen

  1. Für Variablen
  2. Für Zeiger / Referenzen
  3. Für Dereferenzierungen

Wir legen zunächst wieder eine Oberklasse an, die wir Element nennen:

struct Element {
	int offset;
	static int Offset;

	inline static int IncOffset(int size = 4) {
		const int addr = Offset;
		Offset += size;

		return addr;
	}

	virtual void build(const gas::Assembly&) const = 0;
};

Und dann noch die restlichen Strukturen, die von Element erben:

struct Var : public Element {
	int value;

	explicit Var(int va);
	explicit Var(const Var*);

	virtual void build(const gas::Assembly&) const override;
};

struct Ref : public Element {
	const Var* var;

	explicit Ref(const Var*);

	virtual void build(const gas::Assembly&) const override;
};

struct DeRef : public Element {
	const Ref* ref;

	explicit DeRef(const Ref*);

	virtual void build(const gas::Assembly&) const override;
};

Insgesamt sieht unsere builder.hpp also so aus:

Alle besitzen also ein Offset, das ist die Adresse, an der diese Variablen gespeichert werden. Das Offset ist vom Stack Pointer aus zu betrachten.

Und die zugehörige builder.cpp:

Jetzt geht’s richtig los

Nun können wir endlich unser erstes Programm simulieren:

#include "builder.hpp"
#include "asm.hpp"

int main() {
	gas::Assembly asmbly(std::cout, "_prog");
	asmbly.sub(gas::op_code(16), gas::op_code(gas::Pointer::Stack)); // Zeile 6

	// a = 42
	Var a(42);
	a.build(asmbly);

	// b = a
	Var b(&a);
	b.build(asmbly);

	// c -> a
	Ref c(&a);
	c.build(asmbly);

	// d <- c
	DeRef d(&c);
	d.build(asmbly);

	// print a # 42
	asmbly.push(gas::op_code(gas::Pointer::Stack, a.offset));
	asmbly.call("_print");
	asmbly.pop();

	// print b # 42
	asmbly.push(gas::op_code(gas::Pointer::Stack, b.offset));
	asmbly.call("_print");
	asmbly.pop();

	// print c # ?
	asmbly.push(gas::op_code(gas::Pointer::Stack, c.offset));
	asmbly.call("_print");
	asmbly.pop();

	// print d # 42
	asmbly.push(gas::op_code(gas::Pointer::Stack, d.offset));
	asmbly.call("_print");
	asmbly.pop();

	asmbly.add(gas::op_code(16), gas::op_code(gas::Pointer::Stack)); // Zeile 44
}

Zu beachten sind die Zeilen 6 und 44: Um auf dem Stack Dinge anzulegen, muss man in Assembler notieren, wie viel Speicher auf dem Stack angelegt werden soll. Da wir 4 Variablen haben und jede eine Größe von 4 hat (und damit dieselbe Größe wie ein int32) müssen wir 4 * 4 = 16 Byte reservieren.

Wenn wir dieses Programm nun kompilieren:
g++ -o asm_test.exe asm_test.cpp builder.cpp asm.cpp -std=c++0x -Wall -O3

und ausführen, erhalten wir die folgende Assembler-Ausgabe:

.text
.globl  _prog

_prog:
        pushl   %ebp
        movl    %esp, %ebp

        subl    $16, %esp
        movl    $42, 0(%esp)
        movl    $42, 4(%esp)
        leal    0(%esp), %eax
        movl    %eax, 8(%esp)
        movl    8(%esp), %eax
        movl    0(%eax), %eax
        movl    %eax, 12(%esp)
        pushl   0(%esp)
        call    _print
        addl    $4, %esp
        pushl   4(%esp)
        call    _print
        addl    $4, %esp
        pushl   8(%esp)
        call    _print
        addl    $4, %esp
        pushl   12(%esp)
        call    _print
        addl    $4, %esp
        addl    $16, %esp

        popl    %ebp
ret

Und jetzt?

Nun haben wir zwar Assembler, aber was machen wir damit? Und was sind _prog und _print?
_prog und _print sind (externe) Funktionen. _prog definieren wir in Zeile 4 selbst, das ist also wohl unsere Startfunktion.
_print ist unsere Funktion für die Ausgabe (wen wundert’s) und wird in einer anderen Datei deklariert, nämlich in unserer Runtime, kurz rt.

Und so sieht unsere rt.c aus:

#include <stdio.h>

void print(int num) {
	printf("%d\n", num);
}

extern void prog();

int main() {
	prog();
}

Kurz und knackig.
Wie zu sehen ist, haben die Funktionen in Assembler ein _ als Prefix. Dies dient der Identifizierung der externen Funktionen und muss verwendet werden.

Nun können wir unser Programm kompilieren und ausführen

Dazu kopieren wir die Ausgabe in eine entsprechende Datei mit der Endung .s, was für Assembler Code steht. Wir nennen die Datei mal test.s.
Und jetzt kompilieren wir die Datei zusammen mit unserer rt.c:
gcc -o test.exe rt.c test.s

Bei der Ausführung sollten wir nun folgende Ausgabe erhalten:

42
42
2686680
42

Wobei Zeile 3 variieren wird.

Wie geht’s weiter?

Das nächste Ziel ist die Syntax unserer Sprache vollautomatisch zu parsen und umzuwandeln.

Zunächst erweitern wir unser Code-Snippet:

a = 42
b = a

c -> a
d <- c

print a
print b
print c
print d

c -> nil

print 23

Wir fügen also unsere bisherigen Liste von Schlüsselwörtern (lediglich print) noch nil hinzu. nil ist gleichbedeutend mit null oder nullptr wie man es aus anderen Sprachen kennt und meint den Verweis auf einen ungültigen Zeiger.

Wir benötigen zunächst eine Struktur die unsere Lokalität wiederspiegelt. Also unsere momentane Position, das Ende der Datei und in welcher Zeilennummer wir uns befinden. Alternativ könnte man, neben der Zeilennummer, auch noch hinzufügen, in welcher Spalte man sich befindet, sprich an welchem Zeichen in der momentanen Zeile. Doch das lassen wir außen vor.

struct Loc {
	char* pos;
	const char* const end;
	unsigned int lineNr = 1;

	explicit Loc(char* the_pos, const char* const the_end);

	bool eof() const {
		return this->pos == (this->end - 1);
	}
};

Die Position und das Ende der Datei realisieren wir durch einen char Pointer, so können wir auch jederzeit auf das aktuelle Zeichen zugreifen.

Als nächstes benötigen wir für unser print eine weitere Struktur, die die Ausgabe behandelt:

struct Print : public Element {
	int value = -1;

	explicit Print(const Element*);
	explicit Print(int num);

	virtual void build(const gas::Assembly&) const override;
};

Der print Befehl kann jedes Element entgegen nehmen (Variablen, Referenzen, Referenzierungen und auch Zahlen).

Nun können wir uns an die Parser Struktur machen:

class Parser {
private:
	const std::string PRINT = "print";
	const std::string NIL = "nil";

	Loc _loc;

	std::vector<std::unique_ptr<const Element>> _elems;

	std::map<const std::string, const Var*> _vars;
	std::map<const std::string, const Ref*> _refs;
	std::map<const std::string, const DeRef*> _derefs;

	bool _isNext(char c);
	bool _isNext(const std::string&);

	void _skip_spaces();

	bool _identify_num(int&);
	bool _identify_id(std::string&);

	bool _parse_ref(Ref**, std::string&);
	bool _parse_deref(DeRef**, std::string&);
	bool _parse_var(Var**, std::string&);

	bool _parse_print();

public:
	explicit Parser(char*, const char* const the_end);
	virtual ~Parser() { }

	void parse();
	void build(const gas::Assembly&) const;
};

Die beiden Konstanten PRINT und NIL spiegeln unsere Schlüsselwörter wieder, während alle geparsten und zu übersetzenden Elemente in _elems gespeichert werden. Die HashMap’s _vars, _refs und _derefs sind für das einfache Auffinden von den jeweiligen Bestandteilen.
Die Funktion _isNext prüft (wie man sich denken), ob das nächste /die nächsten Zeichen als nächstes vorkommt.
_skip_spaces entfernt überflüssige Leerzeichen, so das wir diese getrost ignorieren können während _identify_num und _identify_id Zahlen bzw. Identifier (Bezeichner) zusammensetzt.
Anschließend folgenden die vier _parse_* Funktionen, die genau das tun was ihr Name ankündigt: sie parsen Variablen, Referenzen etc. und setzen sie entsprechend zusammen.
Die public parse Funktion ruft nacheinander alle _parse_* Funktionen auf und die build Funktion durchläuft _elems und ruft deren build Methoden auf. So wird der Assembler Code automatisch erstellt und ausgegeben.

Zur Vollständigkeit noch die parser.hpp

die parser.cpp

und die compiler.cpp mit der main Funktion:

Nach der erfolgreichen Kompilierung mittels
g++ -o compiler.exe compiler.cpp parser.cpp builder.cpp asm.cpp -std=c++0x -O3 -Wall
Sollten wir den folgenden Assembler-Code erhalten:

.text
.globl  _prog

_prog:
        pushl   %ebp
        movl    %esp, %ebp

        subl    $20, %esp
        movl    $42, 0(%esp)
        movl    $42, 4(%esp)
        leal    0(%esp), %eax
        movl    %eax, 8(%esp)
        movl    8(%esp), %eax
        movl    0(%eax), %eax
        movl    %eax, 12(%esp)
        pushl   0(%esp)
        call    _print
        addl    $4, %esp
        pushl   4(%esp)
        call    _print
        addl    $4, %esp
        pushl   8(%esp)
        call    _print
        addl    $4, %esp
        pushl   12(%esp)
        call    _print
        addl    $4, %esp
        pushl   $23
        call    _print
        addl    $4, %esp
        addl    $20, %esp

        popl    %ebp
ret

Dieser Assembler-Code wird wieder in eine Datei geschrieben und, wie schon beschrieben, kompiliert.
Noch einmal zur Wiederholung:

Dazu kopieren wir die Ausgabe in eine entsprechende Datei mit der Endung .s, was für Assembler Code steht. Wir nennen die Datei mal test.s.
Und jetzt kompilieren wir die Datei zusammen mit unserer rt.c:
gcc -o test.exe rt.c test.s

Und auch nochmal die rt.c:

#include <stdio.h>

void print(int num) {
	printf("%d\n", num);
}

extern void prog();

int main() {
	prog();
}

Bei der Ausführung sollten wir jetzt folgende Ausgabe erhalten:

42
42
2686680
42
23

Wobei Zeile 3 (wie zuvor) variieren wird.

Endlich geschafft!

Das war es schon. 😉
Unsere Sprache ist soweit fertig, aber ihre Funktionalität ist wirklich überschaubar. 😀 Variablen hoch- oder runterzählen fehlt, ganz zu schweigen von komplexeren Berechnungen. Außerdem wären Bedingungen, Schleifen, Strings, Arrays und Funktionen auch nicht zu verachten. Doch die grundlegende Funktionalität ist vorhanden.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.


*