© Swill Klitch/Shutterstock.com
Eine ausführliche Einführung in die GraalVM – Teil 4

Tree Rewriting: Mein Freund, der Baum


In den letzten drei Artikeln dieser Serie haben wir euch vom Optimizer von GraalVM vorgeschwärmt. Habt ihr euch schon einmal gefragt, wie das technisch geht? Wie geht der Optimizer vor, oder anders gefragt: was müsstet ihr tun, um in GraalVM eine weitere Optimierung hinzuzufügen?

Viele der grundlegenden Ideen im Compilerbau wurden von jemandem entwickelt, der überhaupt nichts mit Softwareentwicklung zu tun hat. Noam Chomsky interessierte sich als Linguist für den Aufbau gesprochener Sprachen. In den 1950er und 1960er Jahren entwickelte er seine Theorien über die Grammatik der Sprachen. Er teilte natürliche Sprachen in vier immer komplexere Gruppen ein. Heute ist dieses Modell unter dem Namen „Chomsky-Hierarchie“ geläufig (Abb. 1). Die kleinste Gruppe – die regulären Sprachen – sind euch beim Programmieren bestimmt schon oft als „reguläre Ausdrücke“ begegnet.

vardanyan_rauh_graalvm4_1.tif_fmt1.jpgAbb. 1: Chomsky hierarchy by J. Finkelstein (Quelle: Wikimedia)

Auf besonders fruchtbaren Boden ist Chomskys Theorie bei den Compilerbauern gefallen. Programmiersprachen passen viel besser in das Schema als gesprochene Sprachen mit ihren vielen Ausnahmen und Logikbrüchen. Lest euch einfach mal die wörtliche Mitschrift einer freien, nicht vorbereiteten Rede oder eines Interviews durch: ihr werdet feststellen, dass kaum ein Satzende mit dem Anfang des Satzes zusammenpasst. Beim Zuhören ist das kein Problem, wir erkennen die grundlegenden Strukturen der Grammatik trotzdem.

Auch wenn der Sprecher allen Regeln folgt und wenn wir die zahlreichen Ausnahmen außer Acht lassen, sind gesprochene Sprachen ziemlich verwickelt. Sie fallen in der Regel unter die beiden äußeren Ringe der Zwiebel und folgen einer kontextfreien oder gar rekursiv aufzählbaren Grammatik.

Chomsky-Hierarchie bei Programmiersprachen

Programmiersprachen sind viel einfacher. Sie sind im Großen und Ganzen kontextfrei – mit einigen Ausnahmen: Variablennamen müssen in fast allen modernen Sprachen deklariert werden, bevor die Variable verwendet werden kann. Damit ist die Sprache nicht mehr kontextfrei, sondern die Menge der erlaubten Variablen hängt jeweils vom vorhergehenden Kontext ab.

Meistens formuliert man die Programmiersprache trotzdem mit einer kontextfreien Grammatik und kümmert sich um solche Spezialfälle im Nachgang. Kontextfreie Grammatiken haben den Vorteil, dass sie den Text automatisch und sehr intuitiv strukturieren – und diese Struktur lässt sich sehr einfach als Baum darstellen. Deshalb jetzt: Zeit für ein Beispiel – schaut euc...

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

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang