Di sini saya mencoba menunjukkan dalam praktek apa beberapa konsep penting dari bidang pembuatan kompiler. Ada kemungkinan bahwa cerita yang diselesaikan selama 15 menit tersebut bisa menjadi cara yang baik untuk menyelami topik yang kompleks. Hanya akan menyenangkan untuk tidak secara pasif membaca apa yang disajikan di bawah ini, tetapi juga untuk memeriksa kode dalam pekerjaan.
Jika pengalaman pertama berhasil, maka di masa depan Anda dapat mengharapkan "sketsa" 15 menit lainnya tentang masalah penyusun.
Apa yang akan dibahas
Mari kita membuat kompilator ekspresi aritmatika. Salah satu yang menerjemahkan teks sumber dalam notasi Polandia terbalik (juga disebut RPN atau POLIZ) menjadi kode perantara yang berfungsi dengan tumpukan. Tapi kita bisa melakukannya tanpa penerjemah di sini. Selanjutnya, kami segera menerjemahkan hasilnya menjadi representasi C. Artinya, kita mendapatkan kompiler dari RPN ke C.
Ngomong-ngomong, kita akan menulis compiler dengan Python. Tapi jangan biarkan ini menghentikan mereka yang lebih suka bahasa pemrograman lain. Inilah latihan yang bermanfaat untuk Anda: terjemahkan kode di bawah ini ke bahasa favorit Anda. Atau gunakan terjemahan yang sudah selesai:
Implementasi F # (oleh gsomix ):
versi pertama
Versi SSA
Mari kita mulai dengan penguraian
def scan(source): tokens = source.split() return [("Push", int(x)) if x[0].isdigit() else ("Op", x) for x in tokens]
Apa yang sudah kita lakukan di sini? Fungsi pemindaian menerima string dari pengguna dengan notasi Polandia terbalik ("2 2 +").
Dan pada output kita mendapatkan representasi perantara. Berikut ini sebuah contoh:
[ ('Push', 2), ('Push', 2), ('Op', '+') ]
Jadi, kita sudah mendapatkan kompilernya. Tapi dia sangat sembrono. Ingatlah bahwa pada awalnya ini tentang kode C.
Mari kita siaran di C
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)
Apa yang sedang terjadi di sini? Mari kita lihat output dari fungsi ini (menggunakan contoh yang sama dengan "2 2 +").
st[sp] = 2; sp += 1; st[sp] = 2; sp += 1; st[sp - 2] = st[sp - 2] + st[sp - 1]; sp -= 1;
Ya, sudah terlihat seperti kode C. Array st memainkan peran stack, dan sp adalah penunjuknya. Biasanya mesin stack virtual bekerja dengan hal-hal ini.
Itu hanya mesin itu sendiri - penerjemah, kita tidak punya. Ada kompiler. Apa yang tersisa? Penting untuk menambahkan bingkai yang diperlukan untuk program C.
Kompiler jadi pertama kami
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 +"))
Masih mengkompilasi output dari program ini dengan kompiler C.
Apakah Anda masih siap untuk melanjutkan? Kalau begitu mari kita bahas apa yang kita lakukan. Ada satu titik yang meragukan - kompiler kami menerjemahkan ekspresi konstan, dan Anda dapat menghitungnya hanya pada tahap kompilasi. Tidak masuk akal untuk menerjemahkannya ke dalam kode. Tapi mari kita ambil sekarang untuk beberapa argumen yang bisa masuk stack dari luar. Mari kita memikirkan fakta bahwa makna praktis dari perkembangan kita dapat diberikan nanti. Sekarang penting untuk mendapatkan ide umum membangun kompiler paling sederhana, bukan?
Apakah Anda suka tajuk utama? SSA - ini terdengar sangat solid untuk kompiler apa pun. Dan sekarang kita akan menggunakan SSA yang sama ini. Apa ini Mari kita bergerak berurutan.
Kami saat ini menghasilkan kode C, tanpa mesin virtual. Tetapi mengapa kita membutuhkan rudiment dalam bentuk operasi stack? Mari kita ganti operasi ini dengan bekerja dengan variabel biasa dari C. Selain itu, kami tidak akan menyimpan variabel - kami akan memiliki nama baru untuk setiap ekspresi. Biarkan kompiler C menangani semua ini. Ternyata dengan kita masing-masing variabel diberi nilai hanya sekali. Dan ini, omong-omong, adalah bentuk SSA .
Ini kompiler baru kami.
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 +"))
Harap dicatat bahwa tidak ada lagi tumpukan dalam kode C, dan bekerja dengannya disimulasikan selama penerjemahan. Tumpukan yang digunakan dalam proses kompilasi tidak mengandung nilai, tetapi nama variabel.
Inilah hasil akhirnya:
#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; }
Ringkasan
Tampaknya waktu untuk pelajaran bersama kita telah berakhir. Kami terlibat dalam menerjemahkan program dari satu bahasa ke bahasa lain. Ini disebut terjemahan sumber-ke-sumber. Atau - hanya terjemahan, yang dapat dianggap sebagai sinonim untuk kompilasi, tetapi biasanya kompiler menerjemahkan program dari representasi tingkat tinggi ke tingkat rendah. Ada juga kata kunci “transpiler” untuk penerjemah sumber-ke-sumber. Tetapi penyebutan “transpiler” dapat mengganggu bagi para ahli kompiler, hati-hati!
Eksperimen dengan kode. Menunggu umpan balik!