Zweihunderttausend Rechnungen pro Nacht
Die Tarifregel des Stadtwerks aus der letzten Lektion läuft jetzt für zweihunderttausend Rechnungen pro Nacht. Den Baum jedes Mal zu durchlaufen dauert zu lange.
Also übersetzt das System den Baum einmal in eine flache Liste winziger Schritte. Diese Liste läuft dann für jede Rechnung. Diese Übersetzung ist die letzte Aufgabe eines Compilers.
Am Ende dieser Lektion
Notiz
Ich kann einen Syntaxbaum in Befehle für eine Stackmaschine übersetzen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Codeerzeugung | das Übersetzen eines Syntaxbaums in Befehle | |
| Stack | ein Stapel, bei dem der letzte Wert zuerst wieder herunterkommt | |
| Stackmaschine | eine Maschine, deren Befehle ihre Werte vom Stack nehmen | PUSH 7 |
| Bytecode | Befehle für eine Stackmaschine, die in Software läuft | |
| Optimierung | Code so ändern, dass er dasselbe mit weniger Arbeit tut | -O2 |
| Konstantenfaltung | eine Rechnung schon beim Übersetzen ausführen | 24 * 60 wird 1440 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Eine Stackmaschine rechnet auf einem Stapel
Eine Stackmaschine legt ihre Zwischenwerte auf einen Stack. PUSH 7 legt 7 oben drauf. SUB nimmt die zwei obersten Werte herunter, zieht ab und legt das Ergebnis zurück.
Für Stackcode aus einem Baum erzeugen Sie zuerst den Code jedes Kindes und danach den Befehl des Knotens. Beim Lauf lässt jedes Kind seinen Wert auf dem Stack liegen, bereit für den Knoten.
Beispiel: der Code für 7 - 2 * 3
| Befehl | Stack danach, oben steht rechts |
|---|---|
| PUSH 7 | 7 |
| PUSH 2 | 7, 2 |
| PUSH 3 | 7, 2, 3 |
| MUL | 7, 6 |
| SUB | 1 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Codeerzeuger für - und *
# Codeerzeugung: erst die Kinder, dann die Rechnung.
def erzeuge(baum, code):
if type(baum) == int:
code.append(["PUSH", baum])
return
erzeuge(baum[1], code)
erzeuge(baum[2], code)
if baum[0] == "-":
code.append(["SUB"])
else:
code.append(["MUL"])
code = []
erzeuge(["-", 7, ["*", 2, 3]], code)
for zeile in code:
print(zeile)
# Aendern Sie den Baum in ["*", ["-", 7, 2], 3] und fuehren Sie erneut aus.
Auch Python betreibt eine Stackmaschine
Python durchläuft Ihren Baum nicht jedes Mal. Es übersetzt ihn in Bytecode, also Befehle für eine Stackmaschine in Python selbst, und führt diese aus.
Das Modul dis gibt den Bytecode einer Datei aus. Die Befehle schreiben eine Datei aus einer Zeile, rechnung.py, und zeigen ihren Bytecode. Beachten Sie RESUME oben und die zwei Zeilen am Ende nicht: Jede Datei hat sie.
In den Ordner compiler wechseln
cd ~/compilerHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Programm aus einer Zeile schreiben
echo "brutto = netto * menge + 2" > rechnung.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Sein Bytecode
python3 -m dis rechnung.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Beispiel: der Bytecode von rechnung.py
| Bytecode | Unser Stackcode | Was er tut |
|---|---|---|
| LOAD_NAME netto | LOAD netto | Den Wert von netto auflegen |
| LOAD_NAME menge | LOAD menge | Den Wert von menge auflegen |
| BINARY_OP (*) | MUL | Zwei herunternehmen, das Produkt auflegen |
| LOAD_SMALL_INT 2 | PUSH 2 | Die Zahl 2 auflegen |
| BINARY_OP (+) | ADD | Zwei herunternehmen, die Summe auflegen |
| STORE_NAME brutto | Noch keiner | Den obersten Wert an brutto binden |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Optimierer arbeitet schon beim Übersetzen
gcc erzeugt Code für einen echten Prozessor, mit Registern statt nur einem Stack. Mit -O2 optimiert er außerdem.
Die Befehle schreiben den Assemblercode zweimal, einmal ohne und einmal mit Optimierung. Dann zählt grep -c -w die Zeilen mit der ganzen Zahl 49, dem Ergebnis von square(7). Im Quelltext steht 49 nirgends. Achten Sie darauf, wo die Zahl auftaucht.
Assemblercode ohne Optimierung
gcc -S -O0 -o ohne.s hello.cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Assemblercode mit -O2
gcc -S -O2 -o schnell.s hello.cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zeilen mit 49 ohne Optimierung
grep -c -w 49 ohne.sHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Zeilen mit 49 mit Optimierung
grep -c -w 49 schnell.sHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Auch Python faltet Konstanten
echo "minuten = 24 * 60" > konstant.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Der Bytecode der gefalteten Rechnung
python3 -m dis konstant.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein häufiger Fehler
Warnung
Viele glauben, Optimierung führe dieselben Befehle nur schneller aus. Mit -O2 hat gcc die Arbeit umgeschrieben: Er hat square(7) selbst ausgerechnet, also multipliziert main gar nicht mehr. Ein Optimierer darf jeden Befehl ändern, solange das Programm dasselbe tut. Die nächsten zwei Befehle zeigen das.
Das optimierte Programm bauen
gcc -O2 -o schnell hello.cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Das optimierte Programm starten
./schnellHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Weiterführend
Ergänzen Sie uebersetze um Konstantenfaltung. Prüfen Sie vor dem Code einer Rechnung, ob beide Kinder einfache Zahlen ergeben. Wenn ja, rechnen Sie das Ergebnis aus und erzeugen ein einziges PUSH.
Falten Sie von unten nach oben, sodass ["-", 7, ["*", 2, 3]] zu [["PUSH", 1]] wird. Erklären Sie dann, warum sich ein Baum mit einem Namen darin nur teilweise falten lässt.