Blatt · Sprachen
Übersetzer — von Text zu Maschine, Schritt für Schritt
Zwischen einer Zeile Quelltext und dem, was der Rechner tut, liegen vier Verwandlungen, die sonst niemand zu sehen bekommt: Zeichen werden Wörter, Wörter werden ein Baum, der Baum wird Bytecode, der Bytecode wird Bewegung auf einem Stapel. Hier ist die ganze Kette an einem Stück — für eine kleine Sprache namens Kiesel, die genug kann, um wirklich zu rechnen: Variablen, Verzweigungen, Schleifen, Funktionen mit Rekursion.
Der erste Schritt zerlegt den Text in Wörter: Zahlen, Namen, Schlüsselwörter, Zeichen. Ab hier gibt es keine Leerzeichen und keine Kommentare mehr — nur noch Marken mit Zeile und Spalte, damit ein Fehler später sagen kann, wo er sitzt.
Der Baum entscheidet, was zu wem gehört: 2 + 3 * 4 wird nicht von
links nach rechts gelesen, sondern die Multiplikation hängt tiefer. Gebaut wird er von
einem Pratt-Parser — jedes Zeichen bringt seine eigene Bindungsstärke mit, und
das ersetzt die Grammatikregeln, die man sonst je Vorrangstufe schreiben müsste.
noch nichts ausgegeben
Ein Übersetzer, der falschen Code erzeugt, fällt nicht auf — er rechnet einfach etwas anderes. Deshalb steht hier alles doppelt: neben der Stapelmaschine läuft ein zweiter, unabhängig geschriebener Auswerter direkt auf dem Baum, und neben dem Pratt-Parser ein zweiter nach dem Verfahren des Rangierbahnhofs. Tausende zufällig erzeugte Programme müssen durch alle Wege dasselbe ergeben — mit und ohne Optimierer. Dazu ein Angriff auf die Fehlerbehandlung: zehntausend mutwillig zerstörte Quelltexte, von denen keiner den Übersetzer zum Absturz bringen darf.
noch nicht geprüft
Warum ein Baum
Text ist eine Reihe, Bedeutung ist eine Verschachtelung. Der Baum ist die Stelle, an der aus
2 + 3 * 4 die Aussage „addiere 2 zum Produkt von 3 und 4" wird — und der
einzige Ort, an dem sich Vorrang und Klammerung überhaupt sauber ausdrücken
lassen. Alles danach ist Buchhaltung.
Warum Bytecode
Den Baum direkt auszuwerten geht — der zweite Auswerter hier tut genau das. Bytecode legt dieselbe Bedeutung flach hin: eine Folge einfacher Befehle über einem Stapel, ohne Knotenobjekte und ohne Verzweigung nach Knotenart. Der gemessene Vorsprung ist dabei kleiner, als die Lehrbücher vermuten lassen — beide laufen hier in derselben Sprache, und ein Einmalprogramm verliert sogar, weil das Übersetzen mitzahlt. Die Zahl steht im Prüflauf, nicht in diesem Absatz.
Was der Optimierer darf
Nur das, was am Ergebnis nichts ändert: Konstanten zusammenfassen, doppelte
Vorzeichen streichen, Sprünge ins Nichts entfernen, toten Code nach einem zurück
weglassen. Ob er sich daran hält, wird nicht angenommen, sondern über dieselben tausenden
Programme nachgerechnet.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io