Die eigene Programmiersprache – Teil 1

Im letzten Beitrag habe ich gezeigt, wie man selbst eine einfache Sprache entwickeln kann. Allerdings (wie man auch zum Schluss sah) war diese Sprache in ihrer Funktionalität stark begrenzt.
In den folgenden Beiträgen (diesen eingeschlossen) möchte ich, nachdem der erste Beitrag hoffentlich einen kleinen Einstieg gegeben hat, Step by Step eine relativ umfangreiche Sprache gestalten.

Sobald unsere Sprache fertig ist, soll sie die folgenden Dinge beherrschen:

1. Variablen
2. Arrays
3. Mathematische Terme
4. Ein- und Ausgabe auf der Konsole
5. If-else Bedingungen
6. Schleifen
7. Funktionen
8. C Kompatibilität

In diesem ersten Teil beginnen wir mit dem Aufbau unseres Frameworks, welches wir in den nächsten Tutorials weiter verwenden und ausbauen werden. Unsere Sprache wird am Ende dieses Beitrags folgendes können:

• Funktionen (vorerst ohne Parameter), jedoch keine Funktionsaufrufe. Nur unsere main Funktion wird (automatisch) aufgerufen
• Variablen, allerdings nur by value (Referenzen / Zeiger werden später eingeführt)
• Keine (statische) Typisierung: Wir benutzen dynamisches Typisierung. Dies wird zudem sehr simpel gehalten: Unsere Variablen sind immer Integer
• Eine Möglichkeit, Text auf der Konsole auszugeben
• Mathematische Terme à la (1 + 2) * 3

Übersicht

Zunächst eine kleine Übersicht über unsere zukünftige Sprache, deren Syntax und der Übersetzung. Im weiteren Verlauf nennen wir die Sprache auch beim Namen: Ich habe sie Alpha getauft.

Syntax

Fangen wir damit an, die Syntax unserer Sprache zu definieren. Als Schreiber dieses Tutorials werde ich die Syntax vorgeben, allerdings so, dass leicht Änderungen vorgenommen werden können.

Übersetzung

Unsere Sprache wird direkt in Assembler übersetzt und anschließend (zusammen mit unserer Runtime) vom GNU Compiler gcc in Maschinencode übersetzt.

Der Runtime Code ist ein wenig anders als der, der im letzten Beitrag verwendet wurde:

#include <stdio.h>

extern void alpha_main();

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

void print_str(const char* str) {
    fputs(str, stdout);
}

void print_ln() {
    putchar('\n');
}

int main() {
    alpha_main();
}

Assembler

Der verwendete Assembler-Dialekt ist derselbe, den auch der GNU Compiler generiert: GNU Assembler oder kurz GAS. Außerdem wird in diesem Tutorial nur 32 Bit Assembler generiert. Solltet ihr über einen 64 Bit Compiler verfügen, generiert dieser Standardmäßig 64 Bit Assembler und die Beispiele werden nicht kompilieren. Für eine fehlerfreie Ausführung benötigt ihr also entweder einen 32 Bit Compiler, oder dem 64 Bit Compiler muss bei der Kompilierung das Compiler-Flag -m32 übergeben werden.
32 Bit Assembler ist in vielerlei Hinsicht deutlich einfacher zu handhaben und zu verstehen, als 64 Bit Assembler. Alleine das Mangling unter 64 Bit dürfte Einsteiger etwas verwirren.

Assembler ist gemeinhin relativ komplex, nicht schön anzusehen und die meisten werden sich ohnehin nicht (gut) damit auskennen. Deswegen benutzen wir eine Reihe von Funktionen, die den entsprechenden Assembler Code mithilfe der von uns übergebenen Parameter generieren.
Für die, die sich den Code dazu ansehen wollen, verweise ich auf die asm.hpp und die asm.cpp auf Github. Wer will, kann sich auch direkt den vollständigen Code für dieses Projekt herunterladen.

Übersicht der Assembler-Funktionen

Ab Zeile ~146 beginnen die eigentlichen Assembler-Funktionen, deren Aufgabe es ist, unsere übergebenen Argumente in valides Assembler zu übersetzen. Davor sind u.a. diverse enum zu finden, die Register-, Index- und Pointer-Bezeichner gleichwohl als Index definieren (für die ebenfalls dort vorzufindenden C-Arrays).
Im Folgenden werde ich alle Assembler-Funktionen aufzählen und jeweils eine kurze Erklärung dazu schreiben.

Expressions

Kommen wir zur ersten Komponente: Expressions. Oder auf gut deutsch: Ausdrücke.

Die Expr Klasse

class Expr {
public:
	virtual ~Expr() { }

	// Compile Time Evaluation
	virtual bool cte(i32_t*) const {
		return false;
	}

	// Compile Time Evaluation
	virtual bool cte(std::string*) const {
		return false;
	}

	// Normal Evaluation
	virtual void eval(std::ostream&) const = 0;
};

Wir brauchen des Weiteren noch Expressions für Numerische Werte, für Strings, für Variablen und für die Operationen der Grundrechenarten: Addition, Subtraktion, Multiplikation, Division und Modulo.
Eine Übersicht über alle Expressions findet sich in den zugehörigen Dateien Expr.hpp und Expr.cpp. Erwähnenswert wäre zudem noch, dass sich jede der folgenden Expressions wie ein RValue verhält.

Ich werde im Folgenden nur den jeweiligen Header zeigen und eine kurz Erklärung dazu schreiben. Die konkrete Implementierung findet sich in der jeweils gleichnamigen Source-Datei.
Beginnen wir mit der NumExpr:

NumExpr

class NumExpr : public Expr {
private:
	i32_t _value;

public:
	explicit NumExpr(i32_t val);

	// Compile Time Evaluation
	virtual bool cte(i32_t* num) const override {
		*num = _value;
		return true;
	}

	virtual void eval(std::ostream&) const override;
};

Es folgt die NegExpr:

NegExpr

class NegExpr : public Expr {
private:
	std::unique_ptr<const Expr> _expr;

public:
	explicit NegExpr(const Expr*);

	virtual void eval(std::ostream&) const override;
};

StringExpr

class StringExpr : public Expr {
private:
	std::string _label;

public:
	explicit StringExpr(const std::string&);

	// Compile Time Evaluation
	virtual bool cte(std::string* str) const override {
		*str = _label;
		return true;
	}

	virtual void eval(std::ostream&) const override;
};

Als nächstes benötigen wir noch eine Expression für Variablen.

VarExpr

class VarDecl;

class VarExpr : public Expr {
protected:
    const VarDecl* _var;

public:
    explicit VarExpr(const VarDecl*);

    virtual void eval(std::ostream&) const override;
};

Diese Expression hat keine CTE Methode. Unter anderem deshalb, weil das Offset (also die Adresse) einer Variable nicht einem anderen Offset einer (anderen) Variable zugewiesen werden kann. Dies ist schlicht nicht möglich in Assembler.

Bei der Evaluierung wird der Wert der Variable (abgerufen durch die Stack-Adresse) in das eax-Register geschoben und kann von dort aus weiter verwendet werden.
Hier beantwortet sich dann auch gleichermaßen die Frage, die eventuell den ein oder anderen in den Kopf kam: Warum eine Expression für Variablen, wenn Variablen ohnehin eine eigene Klasse sind? Ist das nicht redundant?
Ja und Nein. Durch die Abgrenzung Expression <-> Variable lässt sich vielerlei vereinfachen und simpler halten. Eine Variable hat eine Adresse und hält eine Expression, wobei der Wert der Expression nach der Evaluierung (in der Regel mittels des eax-Registers) an eben diese Adresse geschrieben wird.
Eine Var-Expression hält zwar eine valide Instanz auf eine bestehende Variable, schreibt aber dessen Wert in das eax-Register.
Man könnte allerdings behaupten, dass man die bereits existierende Expression der Variable benutzen könnte. Das stimmt, das könnte man tun. Ich verzichte hier allerdings ganz bewusst darauf, denn ich möchte später im Assembler Code sehen und hervorheben, dass es sich hierbei um eine Variable handelt.

Was jetzt noch fehlt sind die grundlegenden Grundrechenarten. Dafür legen wir zunächst wiederum eine Oberklasse BinaryExpr an.

BinaryExpr

struct BinaryExpr : public Expr {
	std::unique_ptr<const Expr> lhs;
	std::unique_ptr<const Expr> rhs;

	explicit BinaryExpr(const Expr*, const Expr*);

	virtual ~BinaryExpr() { }
};

new AddExpr(new NumExpr(1), new NumExpr(2));

Es folgenden die fehlenden Operationen bzw. Binäre Expressions für Addition, Subtraktion, Multiplikation, Division und Modulo:

struct AddExpr : public BinaryExpr {
	explicit AddExpr(const Expr*, const Expr*);

	virtual void eval(std::ostream&) const override;
};

struct SubExpr : public BinaryExpr {
	explicit SubExpr(const Expr*, const Expr*);

	virtual void eval(std::ostream&) const override;
};

struct MulExpr : public BinaryExpr {
	explicit MulExpr(const Expr*, const Expr*);

	virtual void eval(std::ostream&) const override;
};

struct DivExpr : public BinaryExpr {
	explicit DivExpr(const Expr*, const Expr*);

	virtual void eval(std::ostream&) const override;
};

struct ModExpr : public DivExpr {
	explicit ModExpr(const Expr*, const Expr*);

	virtual void eval(std::ostream&) const override;
};

Labels

Wie schon angesprochen, beinhaltet die StringExpr keinen direkten Inhalt. Der wirkliche String steht an einer ganz anderen Stelle und die Eigenschaft _label aus StringExpr „zeigt“ auf diesen. Ähnlich wie es in SQL mit einem Foreign Key (Fremdschlüssel) gehandhabt wird.
Das Ganze hat den Grund, dass (genau wie in C) unsere Strings direkt im Assembler in ihrem jeweils eigenen Label gespeichert werden. Diese Labels werden erst am Ende des Assemblers deklariert. Deswegen haben wir für diesen Vorgang eine eigenen Klasse Labels:

#ifndef ALPHA_LABEL_HPP
#define ALPHA_LABEL_HPP

#include <ostream>
#include <string>
#include <map>

class Labels {
private:
	std::map<std::string, std::string> _labels;

public:
	std::string addStr(const std::string&, const std::string& = "");
	void eval(std::ostream&) const;
};

#endif

In der Eigenschaft _labels werden unsere Labels und deren zugeordneten konkreten Strings durch einen Aufruf der Funktion addStr gespeichert. Die eval Methode wird am Ende des Übersetzungsvorgangs aufgerufen und schreibt alle vorhandenen Labels mitsamt ihrer Strings in den generierten Assembler.
Ein Beispiel für ein solches String-Label in Assembler wäre:

LC0:
        .ascii "Hello, world!\12\0"

Quelle
Eine Erklärung für die .ascii Direktive ist hier zu finden.
Die Source Datei findet man, wie gehabt, auf Github.

Deklarationen

Deklarationen sind Programmausschnitte wie Variablen

x = 42

oder Befehlsaufrufe

print x

Also Dinge, die einen direkten Einfluss auf das Programmverhalten ausüben.
Wie bei der Übersicht zu Expressions erwähnt wurde, verhalten sich diese wie RValues. Ihr Pondon sind de facto LValues. Ein Beispiel für LValues wären Variablen-Deklarationen: Auf der Linken Seite steht die Variable und auf der Rechten Seite eine Expression. In Pseudo-EBNF ausgedrückt:

<VAR> = <EXPR> <-> <L_VALUE> = <R_VALUE>

Ein LValue macht also (in der Regel) ein RValue erst gültig.

PrintDecl

Betrachten wir unsere Möglichkeit zur Textausgabe genauer: den print Befehl.
Mittels

print "Hallo, Welt!"

bekämen wir die standardmäßige Ausgabe für eine neue Programmiersprache auf der Konsole ausgegeben. Der print Befehl besteht aus dem Schlüsselwort print gefolgt von mindestens einem Leerzeichen und einer Folge von Expressions, wobei mindestens eine Expression anzugeben ist (ansonsten gibt es eine entsprechende Fehlermeldung). Multiple Expressions müssen mittels eines Kommata separiert werden. Genau so, wie wir es in unserer Syntax-Übersicht definiert haben. Ich vermeide dabei extra den Begriff CommaExpr (die es bislang nicht gibt), denn hierbei soll es möglichen Anwendern (also euch) freigestellt sein, ob Kommata, Pluszeichen oder etwas völlig anderes verwendet wird.

Ein Beispiel mit multiplen Expressions:

print "Hallo, ich bin ", 27, " Jahre jung."

Die drei (separierten) Expressions wären in diesem Beispiel die StringExpr "Hallo, ich bin ", die NumExpr 27 sowie die StringExpr " Jahre jung."

Der Aufruf würde schließlich

Hallo, ich bin 27 Jahre jung.

auf der Konsole ausgeben.

Für den print Befehl existiert natürlich eine eigene Klasse in der Datei Decl.hpp:

class PrintDecl : public Decl {
private:
	std::vector<std::unique_ptr<const Expr>> _exprs;

public:
	PrintDecl() = default;
	explicit PrintDecl(const Expr*);
	void addExpr(const Expr*);

	virtual void eval(std::ostream&) const override;
};

VarDecl

Kommen wir jetzt zum Thema Variablen. In diesem Teil begnügen wir uns mit reinen Value-Typen und heben uns Zeiger und deren Dereferenzierung für ein späteres Tutorial auf.
Will heißen, wir betrachten nur Variablen der Form:

x = 42
y = x
z = (x * 3) + y / 2

etc.

Wie schon angesprochen, ist eine Variable ebenso eine Deklaration, aber eine spezielle. Schauen wir uns zunächst einmal der Code aus der Datei VarDecl.hpp an:

#ifndef ALPHA_VAR_DECL_HPP
#define ALPHA_VAR_DECL_HPP

#include <memory>
#include "Decl.hpp"
#include "types.hpp"

#include "Expr.hpp"

enum class BitSize : u16_t {
	B_8 = 8,
	B_16 = 16,
	B_32 = 32,
	B_64 = 64,
	B_128 = 128
};

class VarDecl : public Decl {
private:
	const u16_t _bit_size;

	u32_t _stack_offset;
	i32_t _base_offset;

	bool _mut;

	std::unique_ptr<const Expr> _expr;

public:
	explicit VarDecl(const Expr*, bool mut = true, BitSize size = BitSize::B_32);
	virtual ~VarDecl() { }

	bool isMutable() const {
		return _mut;
	}

	u16_t sizeInBit() const {
		return _bit_size;
	}

	void setStackOffset(u32_t offset) {
		_stack_offset = offset;
	}

	void setBaseOffset(u32_t offset) {
		_base_offset = offset;
	}

	u32_t getStackOffset() const {
		return _stack_offset;
	}

	u32_t getBaseOffset() const {
		return _base_offset;
	}

	virtual void eval(std::ostream&) const override;
};

#endif

mov    $42, 0(%esp)
mov    $23, 4(%esp)

4(%esp)

4(%esp)

%esp + 4

Funktionen

Funktionen werden in diesem Teil nur in einer eingeschränkten Form beschrieben: Es fehlen Parameter, Rückgabewerte (return) und Funktionsaufrufe.
Wir werden daher nur eine Funktion betrachten: die main Funktion, von der aus unser Programm startet.
Deren Aufbau sieht wie folgt aus:

main() {
    ...
}

Wobei ... für beliebigen Code steht. Da Alpha eine typlose bzw. dynamische typisierte Sprache ist, fällt die Angabe des Return-Typs weg.
Eine Funktion besitzt die folgende interne Struktur, die in der Datei Func.hpp zu finden ist:

#ifndef ALPHA_FUNC_HPP
#define ALPHA_FUNC_HPP

#include <ostream>
#include <string>
#include <memory>
#include "Scope.hpp"

class Func {
private:
	std::string _name;
	std::unique_ptr<Scope> _scope;

public:
	explicit Func(const std::string&, Scope*);
	virtual ~Func() { }

	const std::string& getName() const {
		return _name;
	}

	Scope* getScope() {
		return _scope.get();
	}

	virtual void eval(std::ostream&) const;
};

#endif

_alpha_main:

Man beachte den Präfix und das folgende alpha_. Letzteres wurde gewählt, um Konflikte mit der main Funktion aus unserer Runtime zu umgehen. Zudem erwartet unsere Runtime eine alpha_main Funktion als globalen Einstiegspunkt (in unserer Runtime definieren wir eine externe alpha_main Methode, die wir in der Runtime-Main aufrufen).

Als nächstes wird der Basis-Pointer gepusht

push   %ebp

und anschließend der Stack-Pointer in den Speicherplatz des ursprünglichen Basis-Pointer abgelegt

mov    %esp, %ebp

Nun folgt die Evaluierung des internen Scopes, den wir uns im nächsten Kapitel näher ansehen werden.
Abschließend wird der Basis-Pointer wieder vom Stack genommen (ge-popt)

pop    %ebp

und die Funktion (bzw. das Label) durch den Befehl

ret

wieder verlassen.
Bei Unklarheiten bezüglich der Assembler-Befehle sollte nochmal die Übersicht der Assembler-Funktionen angesehen werden.

Scope

Kommen wir zu dem bereits angesprochenen Scope’s. Ein Scope ist ein Gültigkeitsbereich von Variablen und Deklarationen, welche nur in einen solchen überhaupt angelegt & verwendet werden können. Hierbei sei anzumerken, dass Alpha (bisher) über keinen globalen Scope verfügt.
Nun da wir wissen, was ein Scope ist, schauen wir uns an, wie er implementiert ist (zu finden in der Datei Scope.hpp):

#ifndef ALPHA_SCOPE_HPP
#define ALPHA_SCOPE_HPP

#include <ostream>
#include <string>
#include <memory>
#include <map>
#include <vector>

#include "types.hpp"
#include "Decl.hpp"

class VarDecl;

class Scope {
private:
    const u32_t _prev_used_storage;

    std::map<std::string, std::vector<VarDecl*>> _existing_vars;
    std::vector<std::unique_ptr<const Decl>> _decls;

public:
    Scope* predecessor;

    explicit Scope(Scope*);
    virtual ~Scope() { }

    u32_t usedStorage() const;

    void addVarDecl(const std::string&, VarDecl*);
    const VarDecl* getVarDecl(const std::string&) const;

    void addDecl(const Decl*);
    void prepare();

    virtual void eval(std::ostream&) const;
};

const VarDecl* seekingDown(const std::string&, const Scope*);

#endif

_existingVars sind Raw-Pointer auf die Eigenschaft _decls und vereinfachen das Auffinden von existierenden Variablen.
_decls sind alle bisherigen Deklarationen im Scope.
Zu guter Letzt wäre die public Eigenschaft predecessor zu erwähnen. Dies ist ein Zeiger auf den vorherigen Scope und heißt wörtlich übersetzt „Vorgänger“. Durch diesen kann jederzeit „der Weg zurück“ gefunden werden:
Sagen wir, wir befinden uns im direkten Scope einer Funktion und entdecken eine If-Bedingung. Diese If-Bedingung eröffnet einen neuen Scope und hält einen Zeiger auf den bisherigen. Nach Abschluss der If-Bedingung kann dann, durch den Vorgänger-Zeiger, der ursprüngliche Scope wiederhergestellt werden. Der direkte Scope einer Funktion hat (wie schon erwähnt) keinen Vorgänger, da in Alpha (bislang) kein globaler Scope existiert.

Bis auf prepare und der freien Funktion seekingDown sollten die restlichen Methoden für sich sprechen, wobei wir die eval Methode gleich noch etwas näher betrachten werden.
prepare bereitet den Scope sozusagen vor, das heißt konkret, dass diese Methode den relativen und absoluten Offset (Stack und Base) für alle im Scope existierenden Variablen vergibt. Wie das genau geschieht, kann in der Source Datei leicht ermittelt werden.
seekingDown gestattet eine Tiefensuche nach einer bestimmten Variable bzw. nach einem bestimmten Variablen-Namen. Dabei ist ein Start-Scope (meist der aktuelle) anzugeben. Anschließend wird dann von diesen ausgehend (sofern kein Treffer erzielt wird) in den Vorgänger-Scopes gesucht. Ein weiterer Grund für die Eigenschaft predecessor und für die Existenz von _existingVars.

Bei der Evaluierung eines Scopes spielt die Anzahl der verwendeten Variablen eine wichtige Rolle, denn jeder Scope ist selbst dafür verantwortlich, genügend Speicher für seine Variablen bereit zu stellen. An dieser Stelle mag sich der eine oder andere die Frage stellen: was genau ist mit Speicher gemeint?
Für jede Variable, die in einem Scope existiert, muss Speicherplatz angefordert (allokiert) werden. Dieses Verhalten sollte aus Sprachen wie C/C++ bekannt sein.
Um dies zu tun, muss die Anzahl an Bytes vom Stack-Pointer subtrahiert werden (wir gehen derzeit von 4 Byte pro Variable aus. Siehe auch die _byte_size Eigenschaft der Variablen-Deklaration).
Ein Beispiel:

sub    $12, %esp

In diesem Beispiel werden 12 Byte subtrahiert, also Platz für drei Variablen (12 / 4 = 3).
Beim Verlassen des Scopes muss dieser Speicher dann wieder freigegeben (deallokiert) werden. Dies geschieht durch eine Addition:

add    $12, %esp

Zwischenstand

Ich habe mir Mühe gegeben, die bisherigen Komponenten (soweit es im Rahmen dieses Tutorials möglich war) ausführlich zu erklären und hoffe, dass es verständlich war. Sollte es mir, eurer Meinung nach, an irgendeiner Stelle nicht gelungen sein, würde ich mich über eine Anmerkung freuen. 🙂

Ansonsten haben wir nun alle erforderlichen Komponenten zusammen und können mit dem Parsen unseres Quellcodes beginnen. 🙂

Der Parser

Bevor ich den eigentlichen Parser zeige, möchte ich zuvor noch zwei Konstrukte vorstellen, die den Parse-Vorgang bequemer gestalten. Diese beiden Sub-Komponenten befinden sich in den Dateien Loc.hpp und Env.hpp.

Loc

Loc, kurz für Location, ist eine Struktur, mit deren Hilfe sich leicht überprüfen lässt, ob wir am Ende unserer Datei angelangt sind, welches aktuelle Zeichen gerade gelesen wird und in welcher Zeile wir uns aktuell befinden.

#ifndef ALPHA_LOC_HPP
#define ALPHA_LOC_HPP

#include "types.hpp"
#include <fstream>

struct Loc {
    u32_t lineNr = 1;
    std::ifstream* input_file = nullptr;
    
    Loc() = default;
    explicit Loc(std::ifstream&);

    char current() const {
        return input_file->peek();
    }

    void next() {
        input_file->ignore();
    }

    bool eof() const {
        return input_file->eof();
    }
};

#endif

In der Methode current wird die Methode peek der std::ifstream Instanz aufgerufen. Diese liefert uns das aktuelle Zeichen der Datei, ohne es zu extrahieren. Somit würde auch ein erneuter Aufruf von current das gleiche Zeichen zurückgeben.
Durch Aufruf der Methode next wird das aktuelle Zeichen verworfen (mittels der std::ifstream Methode ignore) und ein Aufruf der Methode current würde anschließend das nächste Zeichen zurückgeben.
Zu guter Letzt überprüft die Methode eof, ob das Ende der Datei erreicht wurde (eof ist ein weit verbreitetes Akronym für End Of File). Dazu wird die gleichnamige std::ifstream Methode eof benutzt.

Env

Env, Kurzform von Enviroment, ist unsere Umgebung. In dieser Umgebung speichern wir u.a. alle Funktionen.

#ifndef ALPHA_ENV_HPP
#define ALPHA_ENV_HPP

#include <ostream>
#include <vector>
#include <memory>
#include "Labels.hpp"
#include "Func.hpp"

class Env {
private:
    std::vector<std::unique_ptr<const Func>> _funcs;

public:
	Labels labels;

	void addFunc(const Func*);
	void eval(std::ostream&) const;
};

#endif

Parsen & Übersetzen

Nun aber zum wesentlichen: Der Analyse & dem Parsen von Quellcode.
Schauen wir uns dazu zunächst einmal die Parser.hpp an:

#ifndef ALPHA_PARSER_HPP
#define ALPHA_PARSER_HPP

#include <iostream>

#include "types.hpp"
#include "Loc.hpp"
#include "Env.hpp"

class Expr;
class StringExpr;
class Scope;

class Parser {
private:
    Loc _loc;
    Scope* _cur_scope = nullptr;
    bool _errors = false;

    Env _env;

public:
    void error(const char*);
 
    template <typename T, typename... Args>
    void error(const char*, const T&, Args&& ...args);

    void skip_spaces();

    bool accept(char);
    bool accept(const std::string&);
    bool expect(char);
    bool expect(const std::string&);

    bool read_identifier(std::string&);
    bool read_number(i32_t&);

    Env* parse(const std::string&);
    
    void parseFunc();
    void parseScope();

    void parsePrintDecl();
    bool parseVarDecl(const std::string&);

    StringExpr* parseStringExpr();

    Expr* parseExpr();
    Expr* parseTerm();
    Expr* parseFactor();
};

#endif

Das ist schon etwas mehr als die sonstigen Code-Beispiele.
Was sehen wir? Zunächst die Eigenschaften _loc, _cur_scope, _errors und _env.
_loc und _env sind Instanzen der komfortablen Sub-Komponenten Location und Enviroment, die wir gerade besprochen haben.
Auch _cur_scope sollte auf Grund der vorangegangenen Erklärung und des Namens soweit verständlich sein: Es ist der momentan verwendete Scope.
_errors jedoch mag auf den ersten Blick nicht ganz selbsterklärend sein: Mit dieser Hilfs-Eigenschaft merken wir uns, ob bereits Fehler aufgetreten sind. Doch dazu später mehr.

Wenden wir uns der Source-Datei zu. Zunächst sehen wir (nach den includes) diese zwei namespaces:

namespace Tok {
    const std::string Print = "print";
    const std::string L_Arrow = "<-";
    const std::string R_Arrow = "->";
}

namespace Lbl {
    const std::string Str = "STR";
}

Sie dienen dazu, wichtige Schlüsselwörter oder Label-Präfixe an einer zentralen Stelle zu definieren, um sie somit leicht (für euch) austauschbar zu machen.

Als nächstes kommen wir zu den lang ersehnten Methoden:

• error gibt es in zwei Ausführungen. Zum einen mit nur einem Argument (einem C-String) und zum anderen mit einem C-String, einem weiteren Argument beliebigen Typs (da Template) sowie einer variablen Anzahl weiterer Argumente. Diese „variable Anzahl“ kann auch 0 betragen und das passende C++11-Stichwort ist Variadic Templates. Die Methode error agiert also wie printf.
  Doch was macht diese Methode? Wie hier und hier zu sehen ist, wird die Meldung (jeweils das erste Argument) formatiert* (vergleichbar mit printf) und anschließend auf der Konsole ausgegeben.
  Außerdem wird die Eigenschaft _errors auf true gesetzt. Es folgt allerdings (entgegen mancher Erwartung wie ich vermuten möchte) kein direkter Abbruch. Dieser erfolgt erst zum nächst möglichen Zeitpunkt.
  Jetzt mag die Frage aufkommen, warum nicht sofort?
  Zum einen bin ich kein Freund von Methoden wie exit (die wir an dieser Stelle dann bräuchten), zum anderen könnte der Fehler allein nicht ausreichend für eine genaue Identifizierung der Fehlerursache sein. Vielmehr könnten weitere Fehlermeldungen die Fehlerursache besser eingrenzen. Deswegen wird der Abbruch der Analyse dem restlichen Programm überlassen. Dieses Verhalten ist in einigen while-Schleifen der parse* Funktionen, die gleich noch betrachtet werden, zu sehen.

  * Dies geschieht, indem der C-String durchlaufen wird und jede Formatierungsanweisung mit dem jeweils nächsten Parameter ersetzt wird. Deswegen wird an dieser Stelle auch ein C-String anstelle eines std::string benutzt, denn das durchlaufen und „Slicen“ des String ist mit ersterem wesentlich einfacher.

• skip_spaces skippt (ignoriert/verwirft) alle aufeinanderfolgenden Leerzeichen, Tabulatoren oder Zeilenumbrüche. Finden wir einen Zeilenumbruch, wird zusätzlich noch die Zeilennummer _loc.lineNr erhöht.
• Als nächstes folgen die Methoden accept und expect. Sie tun genau das, was ihre Namen vermuten lassen: Sie akzeptieren bzw. erwarten etwas.
  Die Methode accept durchläuft den übergebenen string tok Zeichen für Zeichen und vergleichen ihn mit dem aktuellen Zeichen aus _loc.current(). Sobald ein Unterschied festgestellt wird, wird abgebrochen. In diesem Fall wird die aktuelle Location auf die Location vor Durchgang der Schleife gesetzt* und es wird false zurückgegeben. Andernfalls wird mit true geantwortet. expect ruft ihrerseits accept auf und reagiert im Fehlerfall (da etwas erwartet wurde) mit einer entsprechenden Fehlermeldung.
  Beide Methoden besitzen jeweils eine Variante, die nur ein einzelnes Zeichen (char) entgegen nimmt, um nur dieses mit _loc.current() zu vergleichen.

  * Dies geschieht, damit kein Zeichen verloren geht. Würde _loc nicht auf den Wert vor der Schleife gesetzt werden, würden die bis zum Fehlerfall bereits gelesenen Zeichen nicht mehr betrachtet werden.

• Die Methoden read_identifier und read_number sind Hilfsmethoden, welche einen string bzw. eine Ganzzahl lesen und das Gelesene in dem Referenzparameter ident bzw. num speichern. Solange das aktuelle Zeichen aus _loc.current() ein Alpha-nummerisches Zeichen oder ein Unterstrich ist, wird ein sogenannter Bezeichner (engl. Identifier) in der Methode read_identifier identifiziert. In read_number wird hingegen das aktuelle Zeichen solange gelesen, wie es eine Dezimale-Zahl darstellt, welche anschließend an die bisherigen Zahlen „aneinandergereiht“ wird.
  Für die Prüfung der Daten auf Validität sorgt jeweils eine Lambda Funktion mit dem Namen isValid.
• Kommen wir nun zu den eigentlichen parse* Funktionen:
  parse ist die Hauptfunktion von der alle anderen parse* Funktionen aufgerufen werden.
  Nach Einlesen der Datei und setzen der _loc Eigenschaften läuft solange eine while-Schleife, bis ein Fehler auftritt (_errors ist true) oder das Ende der Datei erreicht wurde (_loc.eof() ist true). In dieser Schleife wird einzig und allein parseFunc aufgerufen (da Funktionen unsere größten Einheiten bilden).
• Die Methode parseFunc parst, wie ihr Name vermittelt, Funktionen. Zunächst wird geprüft, ob wir einen Funktions-Namen finden. Ist dies der Fall, wird eine öffnende und gleich darauf eine schließende Klammer erwartet (wie angesprochen, werden Parameter in diesem Teil nicht behandelt).
  Nun wird der Funktions-Scope geparsed (durch einen Aufruf der entsprechenden Methode parseScope) und anschließend die Funktion in unserer Umgebung (_env) gespeichert. Zu guter letzt wird der derzeitige Scope _cur_scope auf null gesetzt, da außerhalb einer Funktion kein globaler Scope existiert.
• parseScope erwartet zunächst eine geschweifte Klammer und darauf 0 oder mehr Deklarationen, die (sofern vorhanden) mit den Methoden parsePrintDecl und parseVarDecl ermittelt werden. Derartige Deklarationen werden in der _decls Eigenschaft von Scope gespeichert.
  Abschließend wird noch eine schließende geschweifte Klammer erwartet.
• parsePrintDecl
  Nachdem eine Instanz der Print-Deklaration angelegt wurde, läuft eine while-Schleife solange, bis das Ende der Datei erreicht wurde (_loc.eof() ist true). Dabei wird in jeder Iteration eine Expression erwartet. Sollte keine vorgefunden werden, kann nichts ausgegeben werden und ein Fehler wird geworfen. Andernfalls wird die Expression zur Print-Deklaration durch den Aufruf von addExpr hinzugefügt.
  Da wir festgelegt haben, dass mehrere Expressions durch ein Komma voneinander getrennt werden müssen, wird nun geprüft, um ein solches folgt. Ist dies nicht der Fall, ist die Print-Deklaration offensichtlich abgeschlossen und die Schleife wird abgebrochen.
  Zu guter Letzt wird die Print-Deklaration noch zum aktuellen Scope (_cur_scope) durch den Aufruf von addDecl hinzugefügt.
• parseVarDecl
  Diese Methode wird mit einem string als Parameter aufgerufen, der den vermuteten Variablen-Namen beinhaltet.
  Zunächst wird überprüft, welche Form der Zuweisung überhaupt stattfindet. In diesem Tutorial erlauben wir nur Zuweisungen mit =, alle anderen werden als Fehler behandelt.
  Nach erfolgreicher Überprüfung wird nun eine Expression erwartet. Wird keine vorgefunden, wird ein Fehler geworfen. Andernfalls legen wir durch den Aufruf von addVarDecl eine (neue) Variablen Deklaration mit dem übergebenen Namen und der gefundenen Expression im derzeitigen Scope (_cur_scope) an und antworten abschließend mit true.
• parseStringExpr
  Zunächst wird überprüft, ob ein einleitendes Anführungszeichen vorgefunden wird, da ja definiert wurde, dass ein String eine beliebige Zeichenkette zwischen zwei Anführungszeichen ist.
  Sollte diese Überprüfung erfolgreich sein, wird ein leerer String angelegt. Anschließend läuft eine while-Schleife solange, bis das Ende der Datei erreicht wurde (_loc.eof() ist true) oder ein schließendes Anführungszeichen vorgefunden wird. Jedes Zeichen, das während des Schleifen-Durchlaufs gelesen wird, wird in dem String aufgenommen. Nach der Schleife wird das schließende Anführungszeichen erwartet. Darauf folgend wird der String an die Label Instanz unserer Umgebung (Env) durch einen Aufruf von addStr übergeben. Dieser Aufruf gibt wiederum einen String zurück, der das Assembler-Label repräsentiert. Dieser wird als StringExpr zurückgegeben.

Zwischenbemerkung

Die folgenden Funktionen, die das parsen von Expressions übernehmen, werden für die meisten auf den ersten Blick vielleicht etwas bedrohlich und/oder fremdartig wirken.
Schauen wir uns deswegen zunächst nochmal ein Beispiel an. In diesem Teil des Tutorials sind Expressions simple Ausdrücke und bestehen aus einer Summe oder Differenz von Termen. Terme wiederum bestehen aus einer Multiplikation, einer Division oder einer Modulo Operation von je zwei Faktoren (Eventuell erinnert sich noch jemand an die linke und rechte Seite, von denen ich im Kapitel Binären Expressions sprach). Ein Faktor wiederum besteht nur aus einer Zahl, die möglicherweise mit einem Vorzeichen behaftet ist.
Wenn wir also die Expression 6 * 7 + 8 betrachten, könnten wir diese auch als geschachtelte Funktionsaufrufe der folgenden Form verstehen add(mul(6, 7), 8).
Und nichts weiter passiert im eigentliche Sinne in diesen Methoden. Um nicht gegen die Regeln der Mathematik zu verstoßen, rufen sich die Methoden gegenseitig auf, damit die Operationen in der richtigen Reihenfolge ausgeführt werden.

• parseExpr
  Zunächst wird die Methode parseTerm aufgerufen und ihre Rückgabe (ein Zeiger auf eine Expression) in der Variable lhs zwischengespeichert.
  Sollte lhs jedoch ein nullptr sein, wird abgebrochen und es wird ebenso ein nullptr zurückgegeben.
  Ansonsten beginnt nun eine while-Schleife, die solange läuft, bis wir das Ende der Datei erreichen.
  In dieser Schleife aktzeptieren wir (folgend auf die gefundene Expression) entweder gar nichts oder eine Addition/Subtraktion. Dazu akzeptieren wir die Zeichen + und - und erwarten eine darauf folgende weitere Expression, um die Binäre Expression zu vervollständigen. Die Binäre Expression besteht aus dem Expression-Zeiger lhs und dem nun vorgefundenen Expression-Zeiger rhs und wird ihrerseits in lhs gespeichert. Dadurch wird eine derartige Schachtelung erreicht, wie sie in der Zwischenbemerkung angesprochen wurde.
  Sobald weder Plus noch Minus Zeichen mehr zu finden sind, wird abgebrochen und der Expression-Zeiger lhs zurückgegeben.
• parseTerm
  Auch hier wird zunächst eine andere Methode aufgerufen: parseFactor.
  Dessen Rückgabe Wert (ein Zeiger auf eine Expression) wird in der Variable lhs zwischengespeichert. Sollte der Expression-Zeiger jedoch ein nullptr sein, wird ein solcher auch zurückgegeben und abgebrochen.
  Andernfalls wird (wiederum) eine while-Schleife bis zum Auffinden des Datei Endes durchlaufen. In dieser Schleife akzeptieren wir Multiplikationen, Divisionen und Modulo Operationen. Um diese Operationen zu kompletten Binären Expressions zu vervollständigen, werden die jeweiligen Zeichen (*, / und %) akzeptiert und eine darauf folgende weitere Expression erwartet. Auch in dieser Methode besteht die Binäre Expression aus den Expression-Zeigern lhs und rhs und wird wiederum in lhs gespeichert.
  Sobald weder Multiplikation, Division noch Modulo Operationen vorgefunden werden, wird die Schleife verlassen und der Expression-Zeiger lhs zurückgegeben.
• parseFactor
  Diese Methode ist wieder etwas einfacher.
  Zunächst akzeptieren wird ein mögliches Vorzeichen und merken uns, ob ein solches gefunden wurde.
  Dann wird überprüft, um was für einen Faktor es sich genau handelt. Dazu wird zunächst geprüft, ob eine Zahl vorliegt. Wenn dem so ist, wird eine NumExpr mit dem Wert gespeichert.
  Wird eine öffnende Klammer vorgefunden, wird ein geklammerter Ausdruck erwartet. Dieser kann durchaus wiederum aus weiteren Termen bestehen, weswegen die parseExpr Methode aufgerufen wird. Abschließend wird eine schließende Klammer erwartet.
  Wenn es sich um einen Identifier (Bezeichner) handelt, dann erwartet wir, dass es der Name einer Variable ist. Wir prüfen also, vom momentanen Scope ausgehend, ob eine Variable mit einem solchen Namen existiert (dazu benutzen wir die Funktion seekingDown). Wird keine solche Variable vorgefunden, werfen wir einen Fehler. Ansonsten speichern wir einen Zeiger auf die Variable in einer VarExpr.

  Abschließend holen wir uns wieder ins Gedächtnis, ob der vorgefundene Faktor negativ ist (also ein Vorzeichen besitzt). Ist dem so, wird erwartet, dass eine valide Expression vorgefunden wurde. Ist dem so, wird diese in einer NegExpr verpackt und zurückgegeben, andernfalls würde eine entsprechende Fehlermeldung ausgegeben werden. Ansonsten wird der vorgefundene Expression-Zeiger direkt zurückgegeben.

Das war es schon. 😉

Schlussbemerkung

Wie schon im Kapitel Assembler erwähnt, generieren die Assembler-Funktionen ausschließlich 32 Bit Assembler, da dies einfacher zu handhaben und zu verstehen ist. Für eine fehlerfreie Ausführung benötigt ihr also entweder einen 32 Bit Compiler, oder ihr müsst das Compiler-Flag -m32 bei der Kompilierung mit angeben.
Des Weiteren wurde jeglicher Code des Tutorials in C++11 / C++14 geschrieben und benötigt einen Compiler, der diesen Standard verarbeiten kann. Für dieses Tutorial wurde unter Windows 7 / Windows 8.1 der gcc 4.9.1 / 5.X verwendet.

Sollte bei euch der folgende Fehler auftreten:
rt.c:(.text+0x5d): undefined reference to `alpha_main'
Kann es daran liegen, dass ihr in der rt.c (also unserer Runtime) vor der Deklaration und dem Aufruf von alpha_main einen Unterstrich davor setzen müsst: _alpha_main (Siehe auch Präfix).

Um nun den Parser zu testen, können wir ein Test-Programm der folgenden Form schreiben:

main() {
    print "Hallo Welt"
}

und es unter hello.alpha speichern.
Anschließend kompilieren wir unser Projekt:
g++ -o main.exe main.cpp asm.cpp Expr.cpp VarDecl.cpp Scope.cpp Parser.cpp Func.cpp Decl.cpp Labels.cpp Env.cpp Loc.cpp -std=c++1y -Wall
(unter Windows kann auch die make_main.bat verwendet werden)
und kompilieren dann unser Hallo Welt Programm mit main hello.alpha.
Es wird eine hello.s Datei erstellt, die den generierten Assembler beinhaltet, welcher ungefähr so aussehen sollte:

.text
.globl	_alpha_main
_alpha_main:
	pushl	%ebp
	movl	%esp, %ebp
# Begin Scope
# Begin print
	pushl	$L_0_STR
	call	_print_str
	addl	$4, %esp
	call	_print_ln
# End print
# End Scope
	popl	%ebp
ret
L_0_STR:
	.ascii	"Hallo Welt\0"

Hallo Welt

ausgegeben.

Fazit

Soviel zu diesem Teil des Tutorials. Die Punkte 1, 3, (4) [nur Ausgabe, keine Eingabe] und (5) [nur die main Funktion] sind damit von unserer Liste an Zielen abgehakt. 🙂
Ich hoffe, ich konnte euch einen kleinen und hilfreichen Einblick in Sachen Compilerbau liefern.
Wenn ihr Anmerkungen, Kritik oder Ideen habt, wie man etwas besser machen könnte oder was unbedingt in die Sprache mit rein sollte, dann scheut euch nicht, einen Kommentar zu hinterlassen. Auch wenn ihr an irgendeiner Stelle findet, ich hätte mich deutlicher/präziser/detaillierter ausdrücken können.
Ich würde mich überaus freuen, wenn euch dieser Teil soweit angeregt und/oder neugierig gemacht hat, dass ihr auch die kommenden Teile lesen werdet. 🙂