Tutorial Membuat Interpreter dan Compiler (bagian 3)
part 1 part 2 part 3 part 4 part 5 part 6 part 7 part 8 part 9
Source code untuk artikel ini: expr1.zip (sama dengan bagian 2)
Membuat Compiler
Di bagian 2 kita sudah mendefinisikan dan membuat interpreter untuk kalkulator. Berikutnya adalah: bagaimana kalau kita ingin membuat compiler? Interpreter hanya mengeksekusi program, dan tidak menghasilkan output. Compiler perlu mengoutputkan kode dalam bahasa assembly, yang kemudian akan dikompilasi oleh assembler. Mempelajari assembly yang lengkap butuh waktu, apalagi jika kita ingin menargetkan berbagai prosessor, sehingga membuat compiler yang mengoutputkan ke assembly langsung tidaklah mudah.
Karena sulitnya bahasa assembly, dalam tahap-tahap berikutnya, kita tidak akan mengoutputkan bahasa assembly langsung, tapi akan menggunakan bantuan LLVM (Low Level Virtual Machine). Tapi untuk tahap-tahap awal, saya bisa menunjukkan bagaimana output assembly langsung bisa dibuat, apalagi dalam bahasa yang sangat sederhana seperti ini.
Pertama saya akan membahas dulu apa bedanya sebuah compiler dengan interpreter. Sebuah compiler menghasilkan kode assembly dari sebuah program. Compiler tidak menghasilkan file executable. Diberikan program Z dalam bahasa X, compiler membuat versi assembly dari program Z tersebut. Jadi compiler hanya menerjemahkan sebuah bahasa ke ekivalennya dalam bahasa assembly.
Tugas mengubah ke bahasa mesin dilakukan oleh assembler. Assembler mengubah instruksi assembly menjadi bahasa mesin. File yang dihasilkan compiler ini disebut sebagai object code, file ini sudah dalam bahasa mesin, tapi belum bisa dieksekusi.
Mengapa belum bisa? karena masih ada fungsi-fungsi yang belum diketahui definisinya. Misalny, ketika Anda membuat program dalam C, apakah Anda mengimplementasikan sendiri fungsi printf? biasanya tidak, karena fungsi itu sudah ada di Library. Proses berikutnya adalah menggabungkan library dengan object code untuk membentuk executable. Proses ini dilakukan oleh program linker.
Yang paling penting bagi kita bukanlah urutan proses tersebut, tapi apa yang ada dalam sebuah compiler yang membedakannya dari interpreter. Sebagian komponen compiler sama dengan interpreter. Bagian parser sama persis, sehingga kita bisa memakai parser dari tutorial bagian sebelumnya.
Algoritma
Algoritma dasar untuk compiler masih sama dengan interpreter. Pada versi interpreter, kita langsung menjalankan program, nah di versi compiler ini, kita menghasilkan teks di setiap langkah (teks bahasa assembly). Kode assembly tidak langsung dituliskan ke file, tapi ditampung dulu dalam sebuah StringBuffer. Untuk memudahkan, saya akan menggunakan pendekatan berbasis stack (stack based) dan bukan register based (akan saya jelaskan nanti alasannya). Jika Anda tertarik, Anda bisa membaca Wikipedia mengenai Stack machine dan Register machine.
Di awal kita perlu membuat sebuah template, yang merupakan kerangka program. Berikutnya, di setiap langkah kita menghasilkan instruksi yang sesuai, misalnya ketika menemui sebuah integer, kita menghasilkan instuksi untuk menaruh integer tersebut di stack. Ketika menemui instruksi untuk menambah dua ekspresi, kita panggil secara rekursif kode program kita untuk menghasilkan assembly bagi operand kiri dan operand kanan, lalu kita hasilkan instruksi untuk menjumlahkan kedua hasilnya.
Memakai Assembly
Kita akan membatasi bahasan kita untuk Intel x86 32 bit saja. Untuk mengimplementasikan compiler dalam bahasa sederhana tersebut, kita hanya perlu 6 instruksi dan 2 register. Instruksi pertama adalah push <reg> atau push <nilai> untuk menaruh nilai ke stack. Lalu pasangannya adalah pop <reg> untuk menaruh isi stack ke register. Berikutnya kita perlu instruksi add untuk menjumlah, sub untuk mengurangi, dan imull untuk mengalikan integer. Kita juga perlu instruksi call untuk memanggil fungsi printf milik library C, serta ret untuk kembali dari fungsi utama ke sistem operasi.
Kita akan menggunakan syntax assembly AT&T, dan saya hanya mengetes ini di Linux. Ada beberapa tutorial assembly untuk Linux, misalnya http://asm.sourceforge.net/howto/Assembly-HOWTO.html, Anda bisa membaca aneka tutorial jika Anda benar-benar blank mengenai assembly. Setiap file output pasti punya kerangka dasar seperti ini:
.section .rodata
.mytext:
.string "Result %d\n"
.text
.globl main
.type main, @function
main:
/*aneka macam perintah akan diletakkan di sini*/
ret
.size main, .-main
Untuk mengevaluasi ekspresi, kita selalu menggunakan stack. Contohnya begini, Jika kita memiliki (1 * 3) + (4 - 5), kita akan memiliki tree, dengan + sebagai akar (root), anak pertama akan mengandung subtree dengan * di root serta 1 dan 3 di anak, sedangkan anak kedua memiliki subtree dengan - di root serta 4 dan 5 sebagai anak.
Ketika menemui '+', kita ingin agar ekpresi di sebelah kiri (1 * 3) dievaluasi dulu, lalu sebelah kanan di evaluasi (4-5), dan hasil evaluasi keduanya kita jumlahkan. Pertama, kita evaluasi 1 * 2. Ketika menemui *, kita ingin agar bagian kiri (1) dan (3) dievaluasi, lalu hasilnya baru dikalikan. Ketika mengevaluasi 1, maka hasilnya adalah instuksi assembly untuk menaruh 1 di stack, ketika menemui 3, maka hasilnya juga instruksi assembly untuk menaruh hasilnya di stack. Perhatikan awalan $ di syntax AT&T artinya angka 1 dan 3 merupakan literal:
pushl $1
ISI STACK:
1
pushl $3
ISI STACK:
1 3
Ketika menemui *, kita pop 2 angka dari stack, lalu kita kalikan kedua angka tersebut, lalu taruh hasilnya di stack:
popl e%ax
ISI STACK:
1
Isi EAX = 3
popl %ebx
ISI STACK:
kosong
Isi EBX = 1
imull %ebx, %eax ; artinya EAX = EAX * EBX
ISI STACK:
kosong
Isi EAX = 3
pushl %eax
ISI STACK:
3
Sekarang kita evaluasi (4-5), langkahnya sama dengan di atas (jika tidak yakin, Anda bisa menjalankan compilernya), di akhir, kita akan mendapati isi stack seperti ini:
ISI STACK:
3 -1
Lalu operasi penjumlahan dilakukan
popl %eax --> ambil dari stack (-1)
popl %ebx --> ambil dari stack (3)
addl %ebx, %eax --> EAX = EAX + EBX
pushl %eax --> masukkan hasilnya ke stack
Di akhir, kita ingin mencetak hasilnya. Untuk mudahnya, kita akan menggunakan library C. Anda juga bisa menggunakan cara khusus sebuah OS, misalnya di DOS Anda bisa menggunakan INT 21 Fungsi 9 dan di Linux Anda bisa memanggil syscall write. Tapi cara-cara tersebut tidak portabel. Library C sudah tersedia di aneka OS berbasis UNIX, jadi demi kesederhanaan artikel, saya akan memakai library C. Di C, mencetak sebuah integer mudah sekali, cukup printf("Result: %d\n", result). Di assembly ini juga tidak sulit, cukup perlu:
pushl %eax
push $.mytext
call printf
popl %ebx
popl %ebx
Passing parameter dalam assembly dapat dilakukan via register atau stack (tergantung calling convention, dan jumlah parameternya, tapi itu tidak penting sekarang). Dalam kasus printf kita perlu menggunakan stack, parameter untuk printf dalam kasus ini ada dua, yang pertama adalah format string "Result: %d\n", yang saya letakkan di label .mytext, serta nilai integer yang akan kita cetak. Passing dilakukan terbalik, parameter terakhir dipush pertama.
Karena pushl %eax sudah dilakukan di akhir setiap ekspresi, maka kita tidak perlu mengulanginya. Seperti yang Anda lihat di bagian template, isi $.mytext adalah "Result: %d\n". Instruksi call digunakan untuk memanggil printf. Fungsi printf di C merupakan fungsi khusus (jumlah parameternya bisa banyak), sehingga kita perlu membuang lagi nilai yang dipush dengan popl ke sembarang register (dalam hal ini saya pilih saja %ebx).
Menjalankan compiler
Anda bisa menjalankan compiler ini seperti menjalankan interpreter. Output compiler ini ada dua, yang pertama adalah file assembly .s (misalnya input adalah test.e, maka outputnya adalah test.e.s), dan file executable (file test.e.exe). Jika compiler gcc tidak tersedia di sistem, maka hanya satu saja outputnya (.s). Anda bisa melakukan assembling dan linking dengan:
gcc -m32 namafile.s -o namafile.exe
Secara otomatis program Java akan mencoba menjalankan perintah itu, tapi tidak akan berhasil jika gcc tidak ada di path. Parameter -m32 memaksakan agar kita menggunakan mode 32 bit meski di OS 64 bit (OS yang saya pakai 64 bit, tapi sebagian besar orang masih memakai 32 bit).
Anda bisa mempelajari dan membandingkan dengan output sebuah program dalam bahasa C. Menggunakan compiler GCC, Anda bisa mengoutputkan kode assembly untuk sebuah program dalam bahasa C seperti ini:
gcc -S namafile.c
hasilnya adalah namafile.s. Sebenarnya gcc selalu menghasilkan file assembly .s, tapi file ini dibuat di direktori sementara. Dengan opsi -S kita meminta agar membuat file .s di direktori saat ini dan meminta gcc berhenti setelah membuat file .s (tidak meneruskan tahap assembler dan linker).
Kode Program
Source code compiler lebih panjang dari source code interpreter (83 baris vs 60 baris). Kode-kode berikut ini ada pada file ExprComp.java. Di bagian main kita buat dulu template dasar file assembly yang akan dihasilkan:
StringBuffer result = new StringBuffer();
result.append(".section .rodata\n");
result.append(".mytext:\n");
result.append(".string \"Result %d\\n\"\n");
result.append(".text\n");
result.append(".globl main\n");
result.append(".type main, @function\n");
result.append("main:\n");
el.compile(result);
result.append("ret\n");
result.append(".size main, .-main\n");
Lalu dibagian evaluasi (method compileExpr), kita perlu menghasilkan assembly yang sesuai, untuk integer:
if (expr.getType()==ExprLexer.INT) {
result.append("pushl $"+expr.getText()+"\n");
return;
}
Untuk +,-,* semua perlu dua operand, jadi instruksi awalnya pasti sama, yaitu: hasilkan instruksi untuk kiri dan kanan, lalu pop dua operand ke eax dan ebx:
if (expr.getText().equals("+") || expr.getText().equals("-")
|| expr.getText().equals("*")) {
compileExpr(result, (CommonTree)expr.getChild(0));
compileExpr(result, (CommonTree)expr.getChild(1));
result.append("popl %eax\n");
result.append("popl %ebx\n");
}
Berikutnya mudah, kalau + hasilkan addl, kalau - hasilkan subl, dan kalau * hasilkan imull:
if (expr.getText().equals("+")) {
result.append("addl %ebx, %eax\n");
}
if (expr.getText().equals("-")) {
result.append("subl %eax, %ebx\n");
}
if (expr.getText().equals("*")) {
result.append("imull %ebx, %eax\n");
}
Hasilnya kita kembalikan ke stack:
result.append("pushl %eax\n");
Setelah sebuah ekspresi selesai, kita perlu mencetaknya
void compileExpression(StringBuffer result, CommonTree expr) {
compileExpr(result, (CommonTree)expr.getChild(0));
result.append("push $.mytext\n");
result.append("call printf\n");
result.append("popl %ebx\n");
result.append("popl %ebx\n");
}
Jadi instruksi yang kita pakai benar-benar amat sedikit.
Program Java akan menyimpan hasil akhir ke file:
String asmname = argv[0]+".s";
FileWriter fw = new FileWriter(asmname);
PrintWriter pw = new PrintWriter(fw);
pw.println(result.toString());
fw.close();
Lalu hasilnya dikompilasi:
String command[] = {"gcc", "-m32", asmname, "-o",
argv[0]+".exe"};
Process p = Runtime.getRuntime().exec(command);
p.waitFor();
Perhatikan bahwa jika kompilasi gagal atau berhasil, tidak akan ada pesan apapun. Anda hanya akan tahu bahwa kompilasi berhasil atau tidak dengan melihat apakah file .exe tercipta atau tidak. Silahkan tambahkan sendiri kode untuk melakukan pemeriksaan tersebut.
Terlalu sederhana
Instruksi yang dihasilkan oleh compiler ini sangat sederhana, namun sangat tidak efisien. Karena semua hanyalah konstanta (kita belum bisa menerima input dari user), maka sebenarnya yang penting hanyalah hasil akhir saja. Meski demikian, latihan ini penting sebelum masuk ke bahasa yang bisa memiliki variabel/identifier.
Ketika kita sudah bisa menerima input dari user, eksekusi berbasis stack kurang efisien. Sebuah prosessor memiliki beberapa register, dan penggunaan stack lebih lambat dari register. Misalnya kita punya 3 variabel, kita bisa meletakkan 3 variabel tersebut di register, tanpa perlu menyentuh stack sama sekali. Tapi masalah muncul ketika jumlah variabel semakin banyak. Jumlah register di prosessor terbatas (biasanya 16-32 register), jadi kita tetap perlu memakai stack ketika jumlah variabel semakin banyak. Kita harus dengan pintar mengatur, variabel apa yang masuk register dan apa yang masuk stack. Masalah ini dinamakan register allocation problem. Anda bisa membaca aneka buku dan paper untuk memahami masalah tersebut.
Kita juga harus memiliki pengetahuan assembly aneka prosessor untuk bisa membuat kode assembly yang baik. Masalahnya terutama adalah masalah optimasi, ada banyak cara untuk melakukan suatu hal (misalnya membagi dua bisa dilakukan dengan shift right satu bit), sebuah compiler yang baik harus bisa memilih instruksi terbaik untuk menghasilkan kode tercepat.
Di masa yang akan datang, saya akan menunjukkan bagaimana menggunakan LLVM, yang akan bisa mengoutputkan kode bahasa mesin, tapi kita sendiri tidak perlu memahami aneka prosessor. LLVM merupakan proyek yang sudah ada sejak 9 tahun yang lalu (tahun 2000), dan sudah didukung oleh banyak perusahaan besar (Adobe, Apple, dsb).
Bahan Latihan
- Tambahkan operator /, tangani kasus pembagian dengan 0.
- Tambahkan unary operator + dan -.
blog comments powered by Disqus
Copyright © 2009-2018 Yohanes Nugroho