© F. J. CARNEROS/Shutterstock.com
Eine ausführliche Einführung in die GraalVM – Teil 7

Truffle – Graals Compiler- Compiler


Unsere Serie über GraalVM neigt sich dem Ende zu, und wir haben schon viel darüber erzählt. Aber warum wir glauben, dass GraalVM zukunftsweisend ist, haben wir euch noch nicht gezeigt. Wir sind die ganze Zeit abstrakt geblieben. Vielleicht habt ihr noch in Erinnerung, dass wir Truffle einen „Compiler-Compiler“ genannt hatten. Aber was bedeutet das? Heute tauchen wir richtig tief ab und zeigen euch Quelltexte. Lasst uns eine eigene Programmiersprache schreiben!

Das ist das Schöne an Truffle. Es macht es einfach, Programmiersprachen zu schreiben. Mit etwas Übung müssten die 90 Minuten eines JAX-Vortrags reichen, live eine rudimentäre Programmiersprache zu schreiben.

Traditionell ist der Compilerbau den Profis vorbehalten. So etwas traut sich niemand zu. Das liegt – wie so oft im Leben – natürlich auch daran, dass die Profis eine große Show daraus machen. So kompliziert ist das nun auch wieder nicht. Aber mit Truffle wird es richtig einfach. Selbst wenn ihr keine Lust habt, eine eigene Programmiersprache zu entwickeln: Truffle senkt die Hürde, bei einer bestehenden Sprache mitzuentwickeln. Wir würden gerne einige von euch Leserinnen und Lesern inspirieren, eine kleine Verbesserung oder Erweiterung zu einer Truffle-Sprache beizutragen. Oder gar selbst eine Programmiersprache zu schreiben. Seid ihr dabei?

Boring Stuff

Jetzt haben wir unsere Messlatte richtig hoch gelegt. Trotzdem kommt jetzt erst einmal eine Zumutung für euch. Wir müssen zunächst zusehen, dass wir unser Projekt an den Start kriegen. Aber das GraalVM-Team hat schon gut vorgearbeitet. Für einen schnellen Start ist es eine gute Idee, die „Simple Language“ auszuchecken und damit zu experimentieren [1]. Noch besser ist EasyScript von Adam Ruka geeignet [2]. Das ist ein Repository mit vier Projekten, die Adam in vier Blogbeiträgen begleitet [3], [4]. In jedem Artikel beschreibt er einen Aspekt der Arbeit mit Truffle.

Für den Anfang möchten wir eure Aufmerksamkeit auf Teil 4 des Repositorys richten. Es besteht gerade mal aus drei Dateien mit zusammen 130 Zeilen, ist also sehr einfach und übersichtlich, enthält aber die komplette Infrastruktur, die wir brauchen. Wir können uns ins gemachte Nest setzen.

Die Sache ist die: Truffle deckt nur einen Teil der Infrastruktur ab, die wir brauchen. Um eine Programmiersprache zu schreiben, brauchen wir einen Lexer, eine Grammatik, einen Parser, einen Compiler oder Interpreter, einen Optimizer und einen Codegenerator. Truffle kümmert sich um die letzten drei Punkte. Lexer, Parser und Grammatik gehören streng genommen nicht zu Truffle. Darum müsst ihr euch selbst kümmern.

Das klingt komplizierter als es ist. Wenn ihr euch intensiver damit beschäftigen wollt, empfehlen wir euch die hervorragenden Artikel von Gabriele Tomassetti [5], [6]. Wir streifen das Thema in diesem Artikel nur kurz, um euch eine grobe Orientierung zu geben.

Sprache, Grammatik ...

In der Grammatik überlegt ihr euch, wie die Sprache aussieht. Dort steht zum Beispiel, dass eine Addition aus zwei Zahlen besteht, und zwischen die beiden Zahlen kommt ein Pluszeichen. Dort steht auch, dass ein if-Statement aus einer Bedingung besteht, die entweder true oder false sein kann, und dass danach ein oder zwei Codeblöcke mit Anweisungen folgen. Parser und Lexer kümmern sich darum, mit Hilfe dieser Grammatik EasyScript-Quelltexte zu nehmen und sie in einen abstrakten Syntaxbaum zu konvertieren.

Wenn ihr das programmiert, müsst ihr das natürlich etwas formaler aufschreiben. Wie das geht, seht ihr in der Datei EasyScript.g4 (Listing 1). Wir haben ein paar weniger wichtige Dinge weggelassen, um uns auf das Wesentliche konzentrieren zu können. Den vollständigen Quelltext findet ihr im GitHub-Repository von Adam Ruka [2].

Listing 1: EasyScript.g4 (Pseudocode)

expression : left=literal '+' right= expression | literal literal : INT | FLOAT FLOAT : [0-9]+ '.' [0-9]+ INT : [0-9]+

Wenn ihr zum ersten Mal eine Grammatik seht, müsst ihr euch vermutlich erst einmal damit anfreunden. Es ist aber sehr einfach. Fangen wir unten an. Wir definierten dort Integer-Zahlen als Folgen von Ziffern. Das deckt sich mit dem, was ihr seinerzeit in der Schule gelernt habt. Zumindest fast: Im Beispiel haben wir die negativen Zahlen weggelassen.

Als Nächstes definieren wir die Fließkommazahlen. Das sind Sequenzen von Ziffern, denen ein Komma – oder vielmehr ein Punkt – und dann noch mehr Ziffern folgen. Das deckt sich mit unserem intuitiven Verständnis.

Danach kommen die Literale. Darunter versteht man hauptsächlich die explizit hingeschriebenen Zahlen und alle „direkten Strings“ (also alle Strings, die von Anführungszeichen umgeben sind). Bis jetzt haben wir nur ganze Zahlen und Fließkommazahlen definiert, also definieren wir die Literale so, dass sie entweder eine ganze Zahl oder eine Fließkommazahl sind.

Zum Schluss definieren wir noch die Ausdrücke. Ehrgeiziger sind wir in diesem Artikel nicht: Wir sind zufrieden, wenn wir eine Programmiersprache schreiben, in der wir addieren können. Das ist eine gute Basis, um später darauf aufzubauen. Machen wir es etwas konkreter. Wir wollen diese Ausdrücke berechnen können:

  • 42

  • 21 + 21

  • 7 + 14 + 21 + ... + 21 (sprich: beliebig viele Additionen)

Dafür definieren wir die „Expression“, die wahlweise ein Literal sein kann, oder auch ein Literal, das von einem Pluszeichen und einer weiteren Expression gefolgt wird.

Das in der Definition der Expression wieder eine Expression vorkommt, ist kein Zufall: diese Rekursion erlaubt es euch, beliebig komplizierte Programme zu schreiben.

... Punkt-vor-Strich-Rechnung ...

Alles andere, was ihr in eurer Programmiersprache findet, könnt ihr genauso formulieren. Egal, ob es sich um ein if-Statement, eine while-Schleife, eine Wertzuweisung oder eine Methodendefinition handelt. Es ist tatsächlich so einfach. Oder vielmehr: Alle modernen Programmiersprachen sind sorgfältig so konstruiert, dass sie mühelos in dieses Schema passen. Natürliche Sprachen wie Englisch oder Deutsch tun das nicht, sie sind komplexer. Aber die Grammatiken der Programmiersprachen sind flexibel genug, dass ihr alles ausdrücken könnt, was ihr formulieren wollt.

Die Grammatiken dienen dazu, die Programme eurer Programmiersprache in einen abstrakten Syntaxbaum zu übersetzen. Dieser Baum gibt die Reihenfolge vor, in der die Anweisungen der Programmiersprachen abgearbeitet werden. Truffle startet in Abbildung 1 links unten und arbeitet sich langsam nach rechts und nach oben vor.

vardanyan_rauh_graalvm7_1.tif_fmt1.jpgAbb. 1: Abstract Syntax Tree

Das gibt uns die Möglichkeit, ein wichtiges Feature eurer Programmiersprache in der Grammatik zu verstecken: die Punkt-vor-Strich-Rechnung. Listing 2 sorgt dafür, dass der abstrakte Syntaxbaum so aufgebaut wird, dass die Punkt-vor-Strich-Rechnung beachtet wird. Für die Grammatik würde es reichen, wenn wir Addition und Multiplikation in einer einzigen Grammatikregel definieren. Der Trick ist, die beiden Operationen in verschiedene Regeln aufzuteilen. Dieser kleine Trick reicht, um dafür zu sorgen, dass der Syntaxbaum immer so aufgebaut wird, dass die Punkt-vor-Strich-Regel automatisch beachtet wird. Die Subtraktion und die Division haben wir in Listing 2 gleich noch mit dazu genommen.

Listing 2: Punkt-vor-Strich-Rechnung (Pseudocode)

expression: multiplication '+' expression | multiplication '-' expression | multiplication multiplication: literal '*' multiplicati...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Gewinner-Teams

Wir bieten Lizenz-Lösungen für Teams jeder Größe: Finden Sie heraus, welche Lösung am besten zu Ihnen passt.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang