Der eigene Interpreter – Grundlagen

26. November 2015

Seit meinem letzten Post in diese Richtung ist einiges an Zeit vergangen. Ich hatte bislang nicht genügend Zeit, damit weiter zu machen, da es leider recht schwer ist, eine Sprache in halbwegs optimalen Assembler zu übersetzen.
Ich habe mich stattdessen, wie man in den vorangegangenen Einträgen sicher bemerkt, wieder mehr mit PHP beschäftigt. PHP ist, im Gegensatz zu C und C++, eine Interpretierte Sprache. Das heißt, dass keinerlei Assembler oder Bytecode generiert wird. Normalerweise ist die sogenannte Zwischensprache, wie sie auch in der Regel bei kompilierten Sprachen vorliegt, das einzige Resultat bevor der Code interpretiert und ausgegeben wird. Diese Zwischensprache nennt man in diesem Fall OpCode. Es erinnert wage an Assembler und dient in kompilierten Sprachen dazu, Optimierungen vorzunehmen, bevor das Endergebnis (Assembler) generiert wird.
Das klingt insgesamt wesentlich einfacher, als halbwegs optimalen Assembler zu produzieren, oder nicht? Zumindest waren das meine Gedanken und daher habe ich beschlossen, mich etwas genauer mit diesem Thema auseinander zu setzen. Genügend Grunderfahrung habe ich ja mit Alpha bereits gesammelt. 😀

Fangen wir klein an. Was soll unsere interpretierte Sprache können? Ich stelle mir die anfängliche Syntax folgendermaßen vor:

var a = 42;
let b = a;
var c = [1, 2, 3];
let d = c[0];
c[1] = 0;

var ist (wen wundert es?) eine Variable. Also ein Behälter mit variablen Inhalt der sich ändern kann und, in der Regel, auch ändern wird.
let dagegen deutet auf einen Behälter mit konstanten Wert.
Wie ersichtlich wird, strebe ich zunächst Duck-Typing á la PHP/Perl/Python an, das erleichtert die Arbeit ungemein, wie wir noch sehen werden.

Und was brauchen wir dazu? Nun, zu aller erst einmal eine Struktur der Ausdrücke oder auch Expressions genannt. Und dann, bevor wir uns den eigentlichen Interpreter widmen, auch erst einmal einen Lexer, der unseren Code in einen schön handlichen Token-Stream zerlegt. Das mag anfänglich etwas nach Fach-Chinesisch klingen, wird aber noch ganz deutlich und einfach.

Beginnen wir mit der Planung. Wir brauchen die folgenden Expressions:

Damit wir mathematische Operationen auflösen können, brauchen wir noch eine Möglichkeit der Evaluation. Hier bietet sich das Visitor-Pattern an. Dazu greifen wir etwas vor und machen ein Beispiel.
Die Operation 2 * 3 würde sich wie folgt in unseren Expressions abbilden:

Expr* exp = new MulExpr(new IntExpr(2), new IntExpr(3));

Um jetzt dieses Beispiel zu reduzieren und zu evaluieren benötigen wir den Visitor. Dieser wird der Expression exp übergeben, welche ihn mit der von der Eltern-Klasse Expr angebotenen, virtuellen Methode accept entgegen nimmt. Innerhalb der accept-Methode von MulExpr passiert dann folgendes:

void MulExpr::accept(Visitor* v) const {
    v->visit(this);
}

Die entsprechende Methode des Visitor wird mit der konkreten Instanz von MulExpr aufgerufen. Darin würde es wie folgt aussehen:

void Visitor::visit(const MulExpr* exp) {
    exp->left->accept(this);
    const f32_t lhs = this->value;

    exp->right->accept(this);
    const f32_t rhs = this->value;

    this->value = lhs * rhs;
}

Den Code im ganzen zu verstehen ist nicht nötig, alles was nötig ist, erkläre ich jetzt:
Zunächst wird an der Linke-Seite (left) der Multiply-Expression die accept-Methode aufgerufen und die Visitor Instanz wird ihr übergeben. Dann speichern wir das evaluierte Ergebnis als float in lhs zwischen. Dasselbe passiert mit der Rechten-Seite (right). Im Anschluss multiplizieren wir die ausgewerteten Ergebnisse der rechten und linken Seite. Und das war’s.
Das mag jetzt einige zunächst überfordern, aber keine Sorge, es wird gleich klarer. Zumindest der Ablauf und der Grund für das Visitor-Pattern sollten im Groben schon einmal klar werden.

Gucken wir uns im Anschluss die konkrete Implementierung des Visitor Patterns an. Es ist relativ offensichtlich, dass wir nicht mit einem Visitor auskommen werden, daher erstellen wir wieder eine Oberklasse, von der die konkreten Visitor-Klassen dann erben. Zunächst benötigen wir nur eine konkrete Visitor-Klasse (MathEval), für das Endergebnis werden wir aber zumindest einen weitere Visitor benötigen. Doch genug der Worte, widmen wir uns den Implementierungen.

Expr.hpp

Expr.cpp

Visitor.hpp

MathEval.hpp

MathEval.cpp

types.hpp

error.hpp

Nachdem wir nun die grundlegende Struktur haben, probieren wir sie doch direkt aus:

#include <iostream>
#include "MathEval.hpp"
#include "Expr.hpp"

int main() {
    MathEval mev;

    auto exp = std::make_unique<AddExpr>(new IntExpr(42), new IntExpr(23));
    exp->accept(&mev);

    std::cout << mev.value << std::endl;
}

Das Ergebnis sollte 65 sein.

Nachdem wir nun Expressions interpretieren können, sollten wir auch dafür sorgen, dass wir überhaupt soweit kommen. Dazu benötigen wir einen Parser, der unsere Syntax in die vorhandenen Expressions überführt. Doch für diesen benötigen wir zunächst den schon angesprochenen Lexer. Um diese beiden Strukturen wird es im nächsten Kapitel gehen.