Die eigene Programmiersprache – Teil 1

28. Dezember 2014

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:

Ü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:



Diesen Code speichern wir als rt.c. Am Ende dieses Beitrags können wir dann die generierte Assembler-Datei und die rt.c zusammen kompilieren & linken.
Nehmen wir z.B. an, dass unsere Ausgabe Datei test.s heißt, ergibt sich folgender Konsolen-Befehl:
gcc -o test.exe test.s rt.c

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


CTE steht, wie der Kommentar verrät, für Compile Time Evaluation. Für jeden Typ, den wir zum Zeitpunkt der Kompilierung möglicherweise evaluieren, gibt es eine eigene Methode. Bisher also für Zeichenketten und Zahlen (i32_t ist dabei nur eine Abkürzung für einen 32 Bit Integer).
Zu guter Letzt folgt noch eine vollständig virtuelle Methode eval, mit der zur Laufzeit der Ausdruck evaluiert und in Assembler übersetzt wird. Dazu erwartet diese Methode eine Referenz auf einen std::ostream. Alle generierten (Assembler-)Ausgaben werden an diesen Stream gesendet.

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


NumExpr hält einen Zahlenwert und stellt die geforderte eval Methode der Basis-Klasse Expr bereit. Außerdem bietet es eine Methode für CTE.
Bei der Evaluierung dieser Klasse wird der Zahlenwert (_value) in das eaxRegister abgelegt. Von dort aus kann der Wert dann weiter verwendet werden. Dies ist speziell bei Termen nützlich (dazu später mehr im Kapitel BinaryExpr). Bei direkter Verwendung allerdings (z.B. bei direkter Zuweisung an eine Variable) wird die CTE-Fähigkeit dieser Expression ausgenutzt, um den redundanten Umweg über das eaxRegister zu vermeiden. Wie genau dieser Vorgang vonstatten geht, werden wir später u.a. beim Thema Variablen noch eingehender betrachten.

Es folgt die NegExpr:

NegExpr


Die NegExpr hält eine andere Expression, um dessen Wert zu negieren. Dazu wird bei der Evaluierung entweder (im Falle von CTE) die Zahl mit -1 multipliziert, oder aber die Expression wird evaluiert und anschließend negiert. Letzteres geschieht mittels des Assembler-Befehls neg (siehe Kapitel Assembler Funktionen).

StringExpr


Auch die StringExpr stellt die geforderte eval Methode bereit und bietet ebenfalls eine CTE Methode für Strings. Wie der Name _label allerdings erahnen lässt, steckt hinter der Eigenschaft nicht der eigentliche String, sondern etwas anderes. Dies wird später noch genauer betrachtet.

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

VarExpr


VarExpr hält einen Zeiger auf eine bestehende Variablen-Deklaration und bietet die geforderte Methode eval an.

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


Diese Klasse definiert, dass sie zwei Expressions als Argument erwartet: eine für die linke Seite und eine für die rechte.
Ein Beispiel:
1 + 2
Zu sehen ist eine simple Addition, wobei die linke Seite die 1 und die rechte Seite die 2 ist. Man kann das ganze als Funktionsaufruf der folgenden Form verstehen: add(1, 2).
Als Code ausgedrückt wäre es:

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:


Diese Klassen bieten die geforderte Evaluierungsmethode eval an. In der eval Methode wird die linke und rechte Expression ihrerseits evaluiert und dann anhand der entsprechenden Mathematischen Funktion miteinander verknüpft und ausgewertet. Dazu verweise ich auf die Übersicht der Assembler Funktionen add, sub, imul und idiv.
Anschließend wird der evaluierte Wert in das eax-Register geschrieben und kann von dort aus weiter verwendet werden. Speziell bei geschachtelten Termen ist dieses Vorgehen von Vorteil, da bei jeder Operation davon ausgegangen werden kann, dass sich der momentane Zwischenwert im eax-Register befindet.
Die Binären Expressions bieten keine CTE-Funktionalität, da das Auswerten eines mathematischen Terms zum Zeitpunkt der Kompilierung den Rahmen dieses Tutorials sprengen würde.

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:

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:


Wie zu sehen ist, bietet die Klasse PrintDecl bereits einen Konstruktor an, dem man die Mindestanforderung (eine Expression) direkt übergeben kann.
Zudem wird ersichtlich, dass die PrintDecl ihre Expressions sequentiell (realisiert durch einen std::vector) speichert, es findet keinerlei Konkatenation und eine damit verbundene (möglicherweise teure & aufwändige) Typ-Anpassung statt. Stattdessen wird bei der Übersetzung jede Expression für sich einzeln evaluiert und ausgegeben, wobei die Ausgabe ohne Zeilenumbruch am Ende geschieht. Der Zeilenumbruch folgt erst nach vollständiger Ausgabe aller zugehörigen Expressions einer Print-Deklaration.
Der gesamte Vorgang passiert (wie gehabt) innerhalb der eval Methode.

Zur Realisierung wird die Runtime-Funktion print_int bzw. print_str (je nach Typ der Expression) angewandt, für den Zeilenumbruch print_ln (Siehe Kapitel Runtime).
Wie bei der Betrachtung des Source-Codes eventuell auffällt, werden diese (und sämtliche andere) Runtime-Funktionen stets mit einem Unterstrich (_) als Präfix angesprochen. Dies ist unter GAS eine Notwendigkeit.

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:


Eine VarDecl hält eine Expression _expr, die die momentane Zuweisung der Variable darstellt, sowie einen boolean _mut, der angibt, ob die Variable konstant ist (dies wird in einem späteren Tutorial nützlich sein). Außerdem besitzt diese Deklaration eine Eigenschaft _bit_size mit dem Typ u16_t was einem unsigned short int (16 Bit) entspricht. Diese Eigenschaft repräsentiert die Größe der Variable und wird durch das BitSize enum angegeben. Dadurch wird garantiert, dass nur valide Größen zulässig sind. Die Standardgröße liegt bei BitSize::B_32 also 32 Bit (4 Byte) und ist damit so groß wie ein herkömmlicher int.
Des Weiteren hat diese Deklaration noch zwei Offsets: ein relatives Offset zum Stack-Anfang (_stack_offset) und ein absolutes Offset zum Basis Pointer (_base_offset).
Wenn jemand das letzte Tutorial gelesen hat, wird derjenige sich eventuell erinnern, dass wir dort nur das Stack-Offset verwendet haben. Im Grunde benötigen wir auch nur eines von beiden. Würden wir aber bspw. nur mit dem Stack-Offset arbeiten, hätten wir das Problem der relativen Adresse: sobald wir etwas auf den Stack pushen, ist unsere relative Adresse verfälscht, denn diese zeigt immer relativ zum Stack-Anfang, und der unterscheidet sich nun um ein Elemente (in der Regel 4 Byte). Daher benutzen wir innerhalb von Berechnungen (dort wo ~90% der Stack-Verwendung stattfindet) immer das Basis-Offset, während das Stack-Offset nur zur Zuweisung dient.
Generell könnten wir völlig auf die Verwendung des Stack-Offsets verzichten, ich behalte es jedoch (noch) aus Gründen der Gewohnheit bei.

Ein weiterer Unterschied der hervorgehoben werden sollte: Das Basis-Offset kann durchaus negative Werte annehmen (dies werden wir beim Thema Parameter in einem der folgenden Tutorials sehen), weswegen das Basis-Offset vorzeichenbehaftet ist, während das Stack-Offset vorzeichenlos ist.
Die Zuweisung findet innerhalb der eval Methode statt, wo die Expression evaluiert (sofern keine CTE möglich war) und anschließend an die jeweiligen Stack-Adresse geschrieben wird.

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:


Eine Funktion hat (bisher) lediglich einen Namen (in unserem obigen Beispiel wäre das main) sowie einen Scope (dazu im nächsten Kapitel näheres).
Natürlich besitzt eine Funktion eine Möglichkeit, sich evaluieren zu lassen. Dabei wird zunächst der Name der Funktion als Label (Einstiegspunkt) benutzt:

_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):


Die Eigenschaft _prev_used_storage gibt an, wie viel Speicher bereits benutzt wurde (von vorherigen Scope’s). Dies ist für geschachtelten Scope’s wichtig, denn jeder Scope muss wissen, ab welchem Offset seine Variablen gespeichert werden. Ohne diese Eigenschaft würde jeder Scope die Variablen vom Offset 0 aus anlegen und damit vorherige Variablen überdecken/-schreiben. Diese Eigenschaft ist eine Konstante und muss daher im Konstruktor (genauer gesagt in der Initialisierungsliste) belegt werden. Dies geschieht durch den übergebenen (vorherigen) Scope und dessen usedStorage Methode. Wer sich damit näher auseinandersetzen möchte, kann einen tieferen Einblick in der zugehörigen Source Datei Scope.cpp erlangen.
Es gibt sicher noch andere (bessere) Lösungen, aber ich habe (bisher) diesen Weg gewählt. Er ist simpel, funktioniert zuverlässig und ist zudem leicht zu erklären.

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


lineNr gibt die aktuelle Zeilennummer an und wird mit jedem Auffinden eines newline Symbols (nl oder als Ascii \n) erhöht. Dies wird im Abschnitt Parsen & Übersetzen noch einmal genauer angesprochen, wo der konkrete Programmabschnitt gezeigt wird.
input_file ist ein Zeiger auf einen std::ifstream und wird benutzt, um das aktuelle und nächste Zeichen aus der Datei zu lesen. Außerdem kann durch diese Instanz überprüft werden, ob das Dateiende erreicht wurde.
Übergeben wird die Instanz im Konstruktor als Referenz. Da wir allerdings nicht der Besitzer dieser Ressource sind, speichert die Klasse Loc nur den rohen Zeiger.

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.


_funcs ist der Speicherort unsere Funktionen, während die public Eigenschaft labels eine Instanz der zuvor besprochenen Komponente Labels darstellt.
Mit addFunc kann eine zusammengefasste Funktion hinzugefügt werden und die Methode eval evaluiert alle Funktionen und alle Labels und erstellt somit unseren eigentlichen Assembler-Code. Der std::ostream Parameter wird bei der Evaluierung der einzelnen Komponenten an die jeweiligen eval Methoden übergeben.

Parsen & Übersetzen

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

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:

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.

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:


Durch den Aufruf gcc -o hello.exe hello.s rt.c kompilieren wir mitsamt unserer Runtime und erhalten die Datei hello.exe.
Sobald wir diese Datei ausführen, bekommen wir ein fröhliches

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

4 Comments
pouk_
29. Dezember 2014 @ 14:53

Hi,
ich finde dein Artikel / Tutorial gut geschrieben, aber habe ein Problem beim Übersetzen der Assemblerdatei hello.s . Habe es so gemacht, wie du es beschrieben hast, bekomme aber trotzdem folgenden Fehler von gcc :
hello.s: Assembler messages:
hello.s:4: Error: invalid instruction suffix for `push'
hello.s:8: Error: invalid instruction suffix for `push'
hello.s:14: Error: invalid instruction suffix for `pop'

hello.s : http://pastebin.com/dWFafFLR
Freue mich schon auf die kommenden Teile 🙂
pouk_

Antworten
Architekt
29. Dezember 2014 @ 16:14

Hallo pouk_, danke für deinen Kommentar.
Ich befürchte, du hast einen 64 Bit Compiler. Gut das du es erwähnst, ich sollte deutlich machen, dass in dem Tutorial 32 Bit Assembler verwendet wird. Das ist mein Versäumnis, sorry dafür.
Kannst du dir einen entsprechenden 32 Bit Compiler laden, und es nochmal probieren? Dann sollte es eig. klappen. 🙂

edit: Habe den Blog-Eintrag mal dahingehend geupdatet.
edit 2: Ich sehe gerade, dass man mithilfe des -m32 Flags auch mit einem 64 Bit Compiler für 32 Bit kompilieren kann.
Quelle: http://www.cyberciti.biz/tips/compile-32bit-application-using-gcc-64-bit-linux.html

Antworten
pouk_
29. Dezember 2014 @ 17:08

Habe es jetzt mit dem flag -m32 ausprobiert, und es gab dennoch Fehler.

rt.c:(.text+0x5e): Nicht definierter Verweis auf `alpha_main'

Das konnte ich aber einfach beheben, indem ich die vor den Funktionsnamen in der rt.c ein „_“ setzte. Jetzt klappt es auch bei mir 😀
Danke für die Hilfe
btw : Ich habe 64bit Ubuntu

Antworten
    Architekt
    29. Dezember 2014 @ 17:16

    Ok, merkwürdig, unter Windows 8.1 bekomme ich exakt den gleichen Fehler, wenn ich den Unterstrich hinzufüge.
    Freut mich aber, dass es nun funktioniert. Ich werde dieses Verhalten am besten direkt mit in den Blog-Eintrag aufnehmen. 🙂

    Antworten

Schreibe einen Kommentar

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


*