Hier habe ich versucht, in der Praxis einige wichtige Konzepte aus dem Bereich der Compilererstellung zu zeigen. Es besteht die Möglichkeit, dass solche 15-minütigen fertigen Geschichten ein guter Weg sind, um in komplexe Themen einzutauchen. Nur wäre es schön, nicht passiv zu lesen, was unten dargestellt wird, sondern auch den Code in Arbeit zu überprüfen.
Wenn die erste Erfahrung erfolgreich ist, können Sie in Zukunft weitere 15-minütige "Skizzen" zum Thema Compiler erwarten.
Was wird diskutiert
Machen wir einen Compiler für arithmetische Ausdrücke. Eine, die den Quelltext in umgekehrter polnischer Notation (auch RPN oder POLIZ genannt) in Zwischencode übersetzt, der mit dem Stapel funktioniert. Aber wir können hier auf Dolmetscher verzichten. Als nächstes übersetzen wir das Ergebnis sofort in eine C-Darstellung. Das heißt, wir bekommen einen Compiler von RPN nach C.
Übrigens werden wir den Compiler in Python schreiben. Aber lassen Sie dies nicht diejenigen aufhalten, die eine andere Programmiersprache bevorzugen. Hier ist eine nützliche Übung für Sie: Übersetzen Sie den folgenden Code in Ihre Lieblingssprache. Oder verwenden Sie eine bereits abgeschlossene Übersetzung:
F # Implementierung (von gsomix ):
erste Version
SSA-Version
Beginnen wir mit dem Parsen
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
Was haben wir hier gemacht? Die Scanfunktion empfängt vom Benutzer eine Zeichenfolge in umgekehrter polnischer Notation ("2 2 +").
Und am Ausgang erhalten wir seine Zwischendarstellung. Hier ist ein Beispiel:
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
Wir haben also schon den Compiler. Aber er ist sehr frivol. Denken Sie daran, dass es anfangs um C-Code ging.
Lassen Sie uns in C senden
def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code)
Was ist hier los? Schauen wir uns die Ausgabe dieser Funktion an (am selben Beispiel mit "2 2 +").
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
Ja, es sieht schon nach C-Code aus. Array st spielt die Rolle des Stapels und sp ist sein Zeiger. Normalerweise arbeiten virtuelle Stapelmaschinen mit diesen Dingen.
Das ist nur die Maschine selbst - den Dolmetscher haben wir nicht. Es gibt einen Compiler. Was haben wir noch? Es ist notwendig, die notwendigen Frames für das C-Programm hinzuzufügen.
Unser erster fertiger Compiler
ST_SIZE = 100 C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { int st[%d], sp = 0; %s printf("%%d\n", st[sp - 1]); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): code = [] for tag, val in ir: if tag == "Push": code.append("st[sp] = %d;" % val) code.append("sp += 1;") elif tag == "Op": code.append("st[sp - 2] = st[sp - 2] %s st[sp - 1];" % val) code.append("sp -= 1;") return "\n".join(code) def rpn_to_c(source): return C_CODE % (ST_SIZE, trans(scan(source))) print(rpn_to_c("2 2 +"))
Es bleibt die Ausgabe dieses Programms mit dem C-Compiler zu kompilieren.
Bist du noch bereit weiterzumachen? Dann lassen Sie uns diskutieren, was wir getan haben. Es gibt einen zweifelhaften Moment: Unser Compiler übersetzt konstante Ausdrücke, und Sie können sie einfach in der Kompilierungsphase berechnen. Es macht keinen Sinn, sie in Code zu übersetzen. Aber nehmen wir jetzt an, dass einige Argumente von außen auf den Stapel kommen können. Lassen Sie uns auf die Tatsache eingehen, dass die praktische Bedeutung unserer Entwicklung später angegeben werden kann. Jetzt ist es wichtig, sich einen Überblick über die Erstellung der einfachsten Compiler zu verschaffen, oder?
Gefällt dir die Überschrift? SSA - das klingt für jeden Compiler sehr solide. Und jetzt werden wir dieselbe SSA verwenden. Was ist das Bewegen wir uns in der richtigen Reihenfolge.
Wir generieren derzeit C-Code ohne virtuelle Maschinen. Aber warum brauchen wir ein Rudiment in Form von Stapeloperationen? Ersetzen wir diese Operationen durch die Arbeit mit gewöhnlichen Variablen aus C. Außerdem werden wir keine Variablen speichern - wir werden für jeden Ausdruck einen neuen Namen haben. Lassen Sie den C-Compiler damit umgehen. Es stellt sich heraus, dass bei uns jeder Variablen nur einmal ein Wert zugewiesen wird. Und das ist übrigens die Form von SSA .
Hier ist unser neuer Compiler.
C_CODE = r"""#include <stdio.h> int main(int argc, char** argv) { %s printf("%%d\n", %s); return 0; }""" def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens] def trans(ir): stack, code = [], [] name_cnt = 0 for tag, val in ir: if tag == "Push": code.append("int t%d = %d;" % (name_cnt, val)) stack.append("t%d" % name_cnt) name_cnt += 1 elif tag == "Op": a, b = stack.pop(), stack.pop() code.append("int t%d = %s %s %s;" % (name_cnt, b, val, a)) stack.append("t%d" % name_cnt) name_cnt += 1 return "\n".join(code), stack.pop() def rpn_to_c(source): return C_CODE % trans(scan(source)) print(rpn_to_c("2 2 +"))
Bitte beachten Sie, dass der C-Code keinen Stapel mehr enthält und die Arbeit damit während der Übersetzung simuliert wird. Der im Kompilierungsprozess verwendete Stapel enthält keine Werte, sondern Variablennamen.
Hier ist das Endergebnis:
#include <stdio.h> int main(int argc, char** argv) { int t0 = 2; int t1 = 2; int t2 = t0 + t1; printf("%d\n", t2); return 0; }
Zusammenfassung
Es scheint, dass die Zeit für unsere gemeinsame Lektion abgelaufen ist. Wir haben das Programm von einer Sprache in eine andere übersetzt. Dies wird als Übersetzung von Quelle zu Quelle bezeichnet. Oder - nur eine Übersetzung, die als Synonym für Kompilierung angesehen werden kann, aber normalerweise übersetzt der Compiler das Programm von einer Darstellung auf hoher Ebene in eine Darstellung auf niedriger Ebene. Es gibt auch das Schlagwort „Transpiler“ für den Source-to-Source-Übersetzer. Aber die Erwähnung des „Transpilers“ kann für Compiler-Experten ärgerlich sein, seien Sie vorsichtig!
Experimentieren Sie mit dem Code. Warten auf Feedback!