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 Expression s 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:
Die Oberklasse Expr
(zwecks Polymorphie)
IntExpr
für Ganzzahlen
NumExpr
für Gleitkommazahlen
CharExpr
für einzelne Zeichen
BinExpr
als Oberklasse für binäre Ausdrücke, wie Addition, Subtraktion etc.
AddExpr
für Additionen
SubExpr
für Subtraktionen
MulExpr
für Multiplikation
DivExpr
für Division
UnaExpr
als Oberklasse für unäre Operationen, wie Not, Negate etc.
NotExpr
für falsifizierbare Ausdrücke
NegExpr
für negative Ausdrücke
BitAndExpr
für Bit-And-Operationen (&
)
BitOrExpr
für Bit-Or-Operationen (|
)
BitXorExpr
für Bit-Xor-Operationen (^
)
BitNotExpr
für Bit-Not-Operationen (~
)
AndExpr
für das logische Und (&&
)
OrExpr
für das logische Oder (||
)
StringExpr
für Strings
ArrayExpr
für Arrays
IndexExpr
für Indices
IndexAssignExpr
für Zuweisungen von Indices
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
Spoiler
#ifndef INTERPRETER_EXPRESSION_HPP
#define INTERPRETER_EXPRESSION_HPP
#include "types.hpp"
#include <vector>
#include <memory>
struct Visitor;
struct Expr {
virtual Expr* syntaxCopy() const = 0;
virtual void accept(Visitor*) const = 0;
};
struct IntExpr : public Expr {
i32_t value;
explicit IntExpr(i32_t);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct NumExpr : public Expr {
f32_t value;
explicit NumExpr(f32_t);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct CharExpr : public Expr {
char value;
explicit CharExpr(char);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BinExpr : public Expr {
std::unique_ptr<Expr> left;
std::unique_ptr<Expr> right;
explicit BinExpr(Expr*, Expr*);
};
struct AddExpr : public BinExpr {
explicit AddExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct SubExpr : public BinExpr {
explicit SubExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct MulExpr : public BinExpr {
explicit MulExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct DivExpr : public BinExpr {
explicit DivExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct UnaExpr : public Expr {
std::unique_ptr<Expr> exp;
explicit UnaExpr(Expr*);
};
struct NotExpr : public UnaExpr {
explicit NotExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct NegExpr : public UnaExpr {
explicit NegExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitAndExpr : public BinExpr {
explicit BitAndExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitOrExpr : public BinExpr {
explicit BitOrExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitXorExpr : public BinExpr {
explicit BitXorExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitNotExpr : public UnaExpr {
explicit BitNotExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct AndExpr : public BinExpr {
explicit AndExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct OrExpr : public BinExpr {
explicit OrExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct AccessExpr : public Expr {
virtual const Expr* getAt(u32_t) const = 0;
virtual void setAt(u32_t, Expr*) = 0;
};
struct ArrayExpr : public AccessExpr {
std::vector<std::unique_ptr<Expr>> exps;
void add(Expr*);
virtual const Expr* getAt(u32_t) const;
virtual void setAt(u32_t, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct StringExpr : public AccessExpr {
std::string value;
explicit StringExpr(const std::string&);
virtual const Expr* getAt(u32_t) const;
virtual void setAt(u32_t, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct IndexExpr : public Expr {
std::unique_ptr<AccessExpr> exp;
std::unique_ptr<Expr> index;
explicit IndexExpr(AccessExpr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct IndexAssignExpr : public IndexExpr {
std::unique_ptr<Expr> assignment;
explicit IndexAssignExpr(AccessExpr*, Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
// TODO: CmpExpr
#endif //INTERPRETER_EXPRESSION_HPP
#ifndef INTERPRETER_EXPRESSION_HPP
#define INTERPRETER_EXPRESSION_HPP
#include "types.hpp"
#include <vector>
#include <memory>
struct Visitor;
struct Expr {
virtual Expr* syntaxCopy() const = 0;
virtual void accept(Visitor*) const = 0;
};
struct IntExpr : public Expr {
i32_t value;
explicit IntExpr(i32_t);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct NumExpr : public Expr {
f32_t value;
explicit NumExpr(f32_t);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct CharExpr : public Expr {
char value;
explicit CharExpr(char);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BinExpr : public Expr {
std::unique_ptr<Expr> left;
std::unique_ptr<Expr> right;
explicit BinExpr(Expr*, Expr*);
};
struct AddExpr : public BinExpr {
explicit AddExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct SubExpr : public BinExpr {
explicit SubExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct MulExpr : public BinExpr {
explicit MulExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct DivExpr : public BinExpr {
explicit DivExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct UnaExpr : public Expr {
std::unique_ptr<Expr> exp;
explicit UnaExpr(Expr*);
};
struct NotExpr : public UnaExpr {
explicit NotExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct NegExpr : public UnaExpr {
explicit NegExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitAndExpr : public BinExpr {
explicit BitAndExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitOrExpr : public BinExpr {
explicit BitOrExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitXorExpr : public BinExpr {
explicit BitXorExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct BitNotExpr : public UnaExpr {
explicit BitNotExpr(Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct AndExpr : public BinExpr {
explicit AndExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct OrExpr : public BinExpr {
explicit OrExpr(Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct AccessExpr : public Expr {
virtual const Expr* getAt(u32_t) const = 0;
virtual void setAt(u32_t, Expr*) = 0;
};
struct ArrayExpr : public AccessExpr {
std::vector<std::unique_ptr<Expr>> exps;
void add(Expr*);
virtual const Expr* getAt(u32_t) const;
virtual void setAt(u32_t, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct StringExpr : public AccessExpr {
std::string value;
explicit StringExpr(const std::string&);
virtual const Expr* getAt(u32_t) const;
virtual void setAt(u32_t, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct IndexExpr : public Expr {
std::unique_ptr<AccessExpr> exp;
std::unique_ptr<Expr> index;
explicit IndexExpr(AccessExpr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
struct IndexAssignExpr : public IndexExpr {
std::unique_ptr<Expr> assignment;
explicit IndexAssignExpr(AccessExpr*, Expr*, Expr*);
virtual Expr* syntaxCopy() const;
virtual void accept(Visitor*) const;
};
// TODO: CmpExpr
#endif //INTERPRETER_EXPRESSION_HPP
Expr.cpp
Spoiler
#include "Expr.hpp"
#include "Visitor.hpp"
IntExpr::IntExpr(i32_t val) : value(val) { }
Expr* IntExpr::syntaxCopy() const {
return new IntExpr(this->value);
}
void IntExpr::accept(Visitor* v) const {
v->visit(this);
}
NumExpr::NumExpr(f32_t val) : value(val) { }
Expr* NumExpr::syntaxCopy() const {
return new NumExpr(this->value);
}
void NumExpr::accept(Visitor* v) const {
v->visit(this);
}
CharExpr::CharExpr(char val) : value(val) { }
Expr* CharExpr::syntaxCopy() const {
return new CharExpr(this->value);
}
void CharExpr::accept(Visitor* v) const {
v->visit(this);
}
BinExpr::BinExpr(Expr* lhs, Expr* rhs) : left(lhs), right(rhs) { }
AddExpr::AddExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* AddExpr::syntaxCopy() const {
return new AddExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void AddExpr::accept(Visitor* v) const {
v->visit(this);
}
SubExpr::SubExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* SubExpr::syntaxCopy() const {
return new SubExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void SubExpr::accept(Visitor* v) const {
v->visit(this);
}
MulExpr::MulExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* MulExpr::syntaxCopy() const {
return new MulExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void MulExpr::accept(Visitor* v) const {
v->visit(this);
}
DivExpr::DivExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* DivExpr::syntaxCopy() const {
return new DivExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void DivExpr::accept(Visitor* v) const {
v->visit(this);
}
UnaExpr::UnaExpr(Expr* e) : exp(e) { }
NotExpr::NotExpr(Expr* e) : UnaExpr(e) { }
Expr* NotExpr::syntaxCopy() const {
return new NotExpr(this->exp->syntaxCopy());
}
void NotExpr::accept(Visitor* v) const {
v->visit(this);
}
NegExpr::NegExpr(Expr* e) : UnaExpr(e) { }
Expr* NegExpr::syntaxCopy() const {
return new NegExpr(this->exp->syntaxCopy());
}
void NegExpr::accept(Visitor* v) const {
v->visit(this);
}
BitAndExpr::BitAndExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitAndExpr::syntaxCopy() const {
return new BitAndExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitAndExpr::accept(Visitor* v) const {
v->visit(this);
}
BitOrExpr::BitOrExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitOrExpr::syntaxCopy() const {
return new BitOrExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitOrExpr::accept(Visitor* v) const {
v->visit(this);
}
BitXorExpr::BitXorExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitXorExpr::syntaxCopy() const {
return new BitXorExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitXorExpr::accept(Visitor* v) const {
v->visit(this);
}
BitNotExpr::BitNotExpr(Expr* e) : UnaExpr(e) { }
Expr* BitNotExpr::syntaxCopy() const {
return new BitNotExpr(this->exp->syntaxCopy());
}
void BitNotExpr::accept(Visitor* v) const {
v->visit(this);
}
AndExpr::AndExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* AndExpr::syntaxCopy() const {
return new AndExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void AndExpr::accept(Visitor* v) const {
v->visit(this);
}
OrExpr::OrExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* OrExpr::syntaxCopy() const {
return new OrExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void OrExpr::accept(Visitor* v) const {
v->visit(this);
}
void ArrayExpr::add(Expr* exp) {
this->exps.emplace_back(exp);
}
const Expr* ArrayExpr::getAt(u32_t index) const {
return this->exps.at(index).get();
}
void ArrayExpr::setAt(u32_t index, Expr* exp) {
this->exps.at(index).reset(exp);
}
Expr* ArrayExpr::syntaxCopy() const {
auto ae = new ArrayExpr();
for (auto& exp : this->exps) {
ae->add(exp->syntaxCopy());
}
return ae;
}
void ArrayExpr::accept(Visitor* v) const {
v->visit(this);
}
StringExpr::StringExpr(const std::string& val) : value(val) { }
const Expr* StringExpr::getAt(u32_t index) const {
return new CharExpr(this->value.at(index));
}
void StringExpr::setAt(u32_t index, Expr* exp) {
if (auto ce = dynamic_cast<CharExpr*>(exp)) {
this->value.at(index) = ce->value;
} else if (auto ie = dynamic_cast<IntExpr*>(exp)) {
this->value.at(index) = static_cast<char>(ie->value);
} else {
error("Only characters and integers can be assigned to string");
}
}
Expr* StringExpr::syntaxCopy() const {
return new StringExpr(this->value);
}
void StringExpr::accept(Visitor* v) const {
v->visit(this);
}
IndexExpr::IndexExpr(AccessExpr* e, Expr* i) : exp(e), index(i) { }
Expr* IndexExpr::syntaxCopy() const {
auto e = dynamic_cast<AccessExpr*>(this->exp->syntaxCopy());
return new IndexExpr(e, this->index->syntaxCopy());
}
void IndexExpr::accept(Visitor* v) const {
v->visit(this);
}
IndexAssignExpr::IndexAssignExpr(AccessExpr* e, Expr* i, Expr* a) : IndexExpr(e, i), assignment(a) { }
Expr* IndexAssignExpr::syntaxCopy() const {
auto e = dynamic_cast<AccessExpr*>(this->exp->syntaxCopy());
return new IndexAssignExpr(e, this->index->syntaxCopy(), this->assignment->syntaxCopy());
}
void IndexAssignExpr::accept(Visitor* v) const {
v->visit(this);
}
#include "Expr.hpp"
#include "Visitor.hpp"
IntExpr::IntExpr(i32_t val) : value(val) { }
Expr* IntExpr::syntaxCopy() const {
return new IntExpr(this->value);
}
void IntExpr::accept(Visitor* v) const {
v->visit(this);
}
NumExpr::NumExpr(f32_t val) : value(val) { }
Expr* NumExpr::syntaxCopy() const {
return new NumExpr(this->value);
}
void NumExpr::accept(Visitor* v) const {
v->visit(this);
}
CharExpr::CharExpr(char val) : value(val) { }
Expr* CharExpr::syntaxCopy() const {
return new CharExpr(this->value);
}
void CharExpr::accept(Visitor* v) const {
v->visit(this);
}
BinExpr::BinExpr(Expr* lhs, Expr* rhs) : left(lhs), right(rhs) { }
AddExpr::AddExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* AddExpr::syntaxCopy() const {
return new AddExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void AddExpr::accept(Visitor* v) const {
v->visit(this);
}
SubExpr::SubExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* SubExpr::syntaxCopy() const {
return new SubExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void SubExpr::accept(Visitor* v) const {
v->visit(this);
}
MulExpr::MulExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* MulExpr::syntaxCopy() const {
return new MulExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void MulExpr::accept(Visitor* v) const {
v->visit(this);
}
DivExpr::DivExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* DivExpr::syntaxCopy() const {
return new DivExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void DivExpr::accept(Visitor* v) const {
v->visit(this);
}
UnaExpr::UnaExpr(Expr* e) : exp(e) { }
NotExpr::NotExpr(Expr* e) : UnaExpr(e) { }
Expr* NotExpr::syntaxCopy() const {
return new NotExpr(this->exp->syntaxCopy());
}
void NotExpr::accept(Visitor* v) const {
v->visit(this);
}
NegExpr::NegExpr(Expr* e) : UnaExpr(e) { }
Expr* NegExpr::syntaxCopy() const {
return new NegExpr(this->exp->syntaxCopy());
}
void NegExpr::accept(Visitor* v) const {
v->visit(this);
}
BitAndExpr::BitAndExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitAndExpr::syntaxCopy() const {
return new BitAndExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitAndExpr::accept(Visitor* v) const {
v->visit(this);
}
BitOrExpr::BitOrExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitOrExpr::syntaxCopy() const {
return new BitOrExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitOrExpr::accept(Visitor* v) const {
v->visit(this);
}
BitXorExpr::BitXorExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* BitXorExpr::syntaxCopy() const {
return new BitXorExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void BitXorExpr::accept(Visitor* v) const {
v->visit(this);
}
BitNotExpr::BitNotExpr(Expr* e) : UnaExpr(e) { }
Expr* BitNotExpr::syntaxCopy() const {
return new BitNotExpr(this->exp->syntaxCopy());
}
void BitNotExpr::accept(Visitor* v) const {
v->visit(this);
}
AndExpr::AndExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* AndExpr::syntaxCopy() const {
return new AndExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void AndExpr::accept(Visitor* v) const {
v->visit(this);
}
OrExpr::OrExpr(Expr* lhs, Expr* rhs) : BinExpr(lhs, rhs) { }
Expr* OrExpr::syntaxCopy() const {
return new OrExpr(this->left->syntaxCopy(), this->right->syntaxCopy());
}
void OrExpr::accept(Visitor* v) const {
v->visit(this);
}
void ArrayExpr::add(Expr* exp) {
this->exps.emplace_back(exp);
}
const Expr* ArrayExpr::getAt(u32_t index) const {
return this->exps.at(index).get();
}
void ArrayExpr::setAt(u32_t index, Expr* exp) {
this->exps.at(index).reset(exp);
}
Expr* ArrayExpr::syntaxCopy() const {
auto ae = new ArrayExpr();
for (auto& exp : this->exps) {
ae->add(exp->syntaxCopy());
}
return ae;
}
void ArrayExpr::accept(Visitor* v) const {
v->visit(this);
}
StringExpr::StringExpr(const std::string& val) : value(val) { }
const Expr* StringExpr::getAt(u32_t index) const {
return new CharExpr(this->value.at(index));
}
void StringExpr::setAt(u32_t index, Expr* exp) {
if (auto ce = dynamic_cast<CharExpr*>(exp)) {
this->value.at(index) = ce->value;
} else if (auto ie = dynamic_cast<IntExpr*>(exp)) {
this->value.at(index) = static_cast<char>(ie->value);
} else {
error("Only characters and integers can be assigned to string");
}
}
Expr* StringExpr::syntaxCopy() const {
return new StringExpr(this->value);
}
void StringExpr::accept(Visitor* v) const {
v->visit(this);
}
IndexExpr::IndexExpr(AccessExpr* e, Expr* i) : exp(e), index(i) { }
Expr* IndexExpr::syntaxCopy() const {
auto e = dynamic_cast<AccessExpr*>(this->exp->syntaxCopy());
return new IndexExpr(e, this->index->syntaxCopy());
}
void IndexExpr::accept(Visitor* v) const {
v->visit(this);
}
IndexAssignExpr::IndexAssignExpr(AccessExpr* e, Expr* i, Expr* a) : IndexExpr(e, i), assignment(a) { }
Expr* IndexAssignExpr::syntaxCopy() const {
auto e = dynamic_cast<AccessExpr*>(this->exp->syntaxCopy());
return new IndexAssignExpr(e, this->index->syntaxCopy(), this->assignment->syntaxCopy());
}
void IndexAssignExpr::accept(Visitor* v) const {
v->visit(this);
}
Visitor.hpp
Spoiler
#ifndef INTERPRETER_VISITOR_HPP
#define INTERPRETER_VISITOR_HPP
#include "error.hpp"
#include <iostream>
struct IntExpr;
struct NumExpr;
struct CharExpr;
struct AddExpr;
struct SubExpr;
struct MulExpr;
struct DivExpr;
struct NotExpr;
struct NegExpr;
struct BitAndExpr;
struct BitOrExpr;
struct BitXorExpr;
struct BitNotExpr;
struct AndExpr;
struct OrExpr;
struct StringExpr;
struct ArrayExpr;
struct IndexExpr;
struct IndexAssignExpr;
struct Visitor {
virtual void visit(const IntExpr*) {
error("IntExpr is not implemented");
}
virtual void visit(const NumExpr*) {
error("NumExpr is not implemented");
}
virtual void visit(const CharExpr*) {
error("CharExpr is not implemented");
}
virtual void visit(const AddExpr*) {
error("AddExpr is not implemented");
}
virtual void visit(const SubExpr*) {
error("SubExpr is not implemented");
}
virtual void visit(const MulExpr*) {
error("MulExpr is not implemented");
}
virtual void visit(const DivExpr*) {
error("DivExpr is not implemented");
}
virtual void visit(const NotExpr*) {
error("NotExpr is not implemented");
}
virtual void visit(const NegExpr*) {
error("NegExpr is not implemented");
}
virtual void visit(const BitAndExpr*) {
error("BitAndExpr is not implemented");
}
virtual void visit(const BitOrExpr*) {
error("BitOrExpr is not implemented");
}
virtual void visit(const BitXorExpr*) {
error("BitXorExpr is not implemented");
}
virtual void visit(const BitNotExpr*) {
error("BitNotExpr is not implemented");
}
virtual void visit(const AndExpr*) {
error("AndExpr is not implemented");
}
virtual void visit(const OrExpr*) {
error("OrExpr is not implemented");
}
virtual void visit(const StringExpr*) {
error("StringExpr is not implemented");
}
virtual void visit(const ArrayExpr*) {
error("ArrayExpr is not implemented");
}
virtual void visit(const IndexExpr*) {
error("IndexExpr is not implemented");
}
virtual void visit(const IndexAssignExpr*) {
error("IndexAssignExpr is not implemented");
}
};
#endif //INTERPRETER_VISITOR_HPP
#ifndef INTERPRETER_VISITOR_HPP
#define INTERPRETER_VISITOR_HPP
#include "error.hpp"
#include <iostream>
struct IntExpr;
struct NumExpr;
struct CharExpr;
struct AddExpr;
struct SubExpr;
struct MulExpr;
struct DivExpr;
struct NotExpr;
struct NegExpr;
struct BitAndExpr;
struct BitOrExpr;
struct BitXorExpr;
struct BitNotExpr;
struct AndExpr;
struct OrExpr;
struct StringExpr;
struct ArrayExpr;
struct IndexExpr;
struct IndexAssignExpr;
struct Visitor {
virtual void visit(const IntExpr*) {
error("IntExpr is not implemented");
}
virtual void visit(const NumExpr*) {
error("NumExpr is not implemented");
}
virtual void visit(const CharExpr*) {
error("CharExpr is not implemented");
}
virtual void visit(const AddExpr*) {
error("AddExpr is not implemented");
}
virtual void visit(const SubExpr*) {
error("SubExpr is not implemented");
}
virtual void visit(const MulExpr*) {
error("MulExpr is not implemented");
}
virtual void visit(const DivExpr*) {
error("DivExpr is not implemented");
}
virtual void visit(const NotExpr*) {
error("NotExpr is not implemented");
}
virtual void visit(const NegExpr*) {
error("NegExpr is not implemented");
}
virtual void visit(const BitAndExpr*) {
error("BitAndExpr is not implemented");
}
virtual void visit(const BitOrExpr*) {
error("BitOrExpr is not implemented");
}
virtual void visit(const BitXorExpr*) {
error("BitXorExpr is not implemented");
}
virtual void visit(const BitNotExpr*) {
error("BitNotExpr is not implemented");
}
virtual void visit(const AndExpr*) {
error("AndExpr is not implemented");
}
virtual void visit(const OrExpr*) {
error("OrExpr is not implemented");
}
virtual void visit(const StringExpr*) {
error("StringExpr is not implemented");
}
virtual void visit(const ArrayExpr*) {
error("ArrayExpr is not implemented");
}
virtual void visit(const IndexExpr*) {
error("IndexExpr is not implemented");
}
virtual void visit(const IndexAssignExpr*) {
error("IndexAssignExpr is not implemented");
}
};
#endif //INTERPRETER_VISITOR_HPP
MathEval.hpp
Spoiler
#ifndef INTERPRETER_MATH_EVAL_HPP
#define INTERPRETER_MATH_EVAL_HPP
#include "types.hpp"
#include "Visitor.hpp"
struct MathEval : public Visitor {
f32_t value;
virtual void visit(const IntExpr*) override;
virtual void visit(const NumExpr*) override;
virtual void visit(const CharExpr*) override;
virtual void visit(const AddExpr*) override;
virtual void visit(const SubExpr*) override;
virtual void visit(const MulExpr*) override;
virtual void visit(const DivExpr*) override;
virtual void visit(const NotExpr*) override;
virtual void visit(const NegExpr*) override;
virtual void visit(const BitAndExpr*) override;
virtual void visit(const BitOrExpr*) override;
virtual void visit(const BitXorExpr*) override;
virtual void visit(const BitNotExpr*) override;
};
#endif //INTERPRETER_MATH_EVAL_HPP
#ifndef INTERPRETER_MATH_EVAL_HPP
#define INTERPRETER_MATH_EVAL_HPP
#include "types.hpp"
#include "Visitor.hpp"
struct MathEval : public Visitor {
f32_t value;
virtual void visit(const IntExpr*) override;
virtual void visit(const NumExpr*) override;
virtual void visit(const CharExpr*) override;
virtual void visit(const AddExpr*) override;
virtual void visit(const SubExpr*) override;
virtual void visit(const MulExpr*) override;
virtual void visit(const DivExpr*) override;
virtual void visit(const NotExpr*) override;
virtual void visit(const NegExpr*) override;
virtual void visit(const BitAndExpr*) override;
virtual void visit(const BitOrExpr*) override;
virtual void visit(const BitXorExpr*) override;
virtual void visit(const BitNotExpr*) override;
};
#endif //INTERPRETER_MATH_EVAL_HPP
MathEval.cpp
Spoiler
#include "MathEval.hpp"
#include "Expr.hpp"
void MathEval::visit(const IntExpr* exp) {
this->value = exp->value;
}
void MathEval::visit(const NumExpr* exp) {
this->value = exp->value;
}
void MathEval::visit(const CharExpr* exp) {
this->value = static_cast<i32_t>(exp->value);
}
void MathEval::visit(const AddExpr* 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;
}
void MathEval::visit(const SubExpr* 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;
}
void MathEval::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;
}
void MathEval::visit(const DivExpr* 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;
}
void MathEval::visit(const NotExpr* exp) {
exp->exp->accept(this);
this->value = !this->value;
}
void MathEval::visit(const NegExpr* exp) {
exp->exp->accept(this);
this->value = this->value * -1;
}
void MathEval::visit(const BitAndExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs & rhs;
}
void MathEval::visit(const BitOrExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs | rhs;
}
void MathEval::visit(const BitXorExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs ^ rhs;
}
void MathEval::visit(const BitNotExpr* exp) {
exp->exp->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
this->value = ~lhs;
}
#include "MathEval.hpp"
#include "Expr.hpp"
void MathEval::visit(const IntExpr* exp) {
this->value = exp->value;
}
void MathEval::visit(const NumExpr* exp) {
this->value = exp->value;
}
void MathEval::visit(const CharExpr* exp) {
this->value = static_cast<i32_t>(exp->value);
}
void MathEval::visit(const AddExpr* 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;
}
void MathEval::visit(const SubExpr* 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;
}
void MathEval::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;
}
void MathEval::visit(const DivExpr* 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;
}
void MathEval::visit(const NotExpr* exp) {
exp->exp->accept(this);
this->value = !this->value;
}
void MathEval::visit(const NegExpr* exp) {
exp->exp->accept(this);
this->value = this->value * -1;
}
void MathEval::visit(const BitAndExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs & rhs;
}
void MathEval::visit(const BitOrExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs | rhs;
}
void MathEval::visit(const BitXorExpr* exp) {
exp->left->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
exp->right->accept(this);
const i32_t rhs = static_cast<i32_t>(this->value);
this->value = lhs ^ rhs;
}
void MathEval::visit(const BitNotExpr* exp) {
exp->exp->accept(this);
const i32_t lhs = static_cast<i32_t>(this->value);
this->value = ~lhs;
}
types.hpp
Spoiler
#ifndef INTERPRETER_TYPES_HPP
#define INTERPRETER_TYPES_HPP
#include <cstdint>
using u64_t = std::uint64_t;
using u32_t = std::uint32_t;
using u16_t = std::uint16_t;
using u8_t = std::uint8_t;
using i64_t = std::int64_t;
using i32_t = std::int32_t;
using i16_t = std::int16_t;
using i8_t = std::int8_t;
using f64_t = double;
using f32_t = float;
#endif //INTERPRETER_TYPES_HPP
#ifndef INTERPRETER_TYPES_HPP
#define INTERPRETER_TYPES_HPP
#include <cstdint>
using u64_t = std::uint64_t;
using u32_t = std::uint32_t;
using u16_t = std::uint16_t;
using u8_t = std::uint8_t;
using i64_t = std::int64_t;
using i32_t = std::int32_t;
using i16_t = std::int16_t;
using i8_t = std::int8_t;
using f64_t = double;
using f32_t = float;
#endif //INTERPRETER_TYPES_HPP
error.hpp
Spoiler
#ifndef INTERPRETER_ERROR_HPP
#define INTERPRETER_ERROR_HPP
#include <iostream>
template <typename T>
void println(std::ostream& stream, const T& last) {
stream << last << std::endl;
}
template <typename T, typename... Args>
void println(std::ostream& stream, const T& first, Args&& ...args) {
stream << first;
println(stream, args...);
}
template <typename... Args>
void debug(Args ...args) {
println(std::cout, args...);
}
template <typename... Args>
void error(Args ...args) {
std::cerr << "Error: ";
println(std::cerr, args...);
throw "Aborting...";
}
template <typename... Args>
void warning(Args ...args) {
std::cerr << "Warning: ";
println(std::cerr, args...);
}
template <typename... Args>
void ensure(bool cond, Args... args) {
if (!cond) {
error(args...);
}
}
#endif //INTERPRETER_ERROR_HPP
#ifndef INTERPRETER_ERROR_HPP
#define INTERPRETER_ERROR_HPP
#include <iostream>
template <typename T>
void println(std::ostream& stream, const T& last) {
stream << last << std::endl;
}
template <typename T, typename... Args>
void println(std::ostream& stream, const T& first, Args&& ...args) {
stream << first;
println(stream, args...);
}
template <typename... Args>
void debug(Args ...args) {
println(std::cout, args...);
}
template <typename... Args>
void error(Args ...args) {
std::cerr << "Error: ";
println(std::cerr, args...);
throw "Aborting...";
}
template <typename... Args>
void warning(Args ...args) {
std::cerr << "Warning: ";
println(std::cerr, args...);
}
template <typename... Args>
void ensure(bool cond, Args... args) {
if (!cond) {
error(args...);
}
}
#endif //INTERPRETER_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.