Tutorial Membuat Interpreter dan Compiler (bagian 1)

part 1 part 2 part 3 part 4 part 5 part 6 part 7 part 8 part 9

Untuk apa membuat compiler?

Sudah ada banyak bahasa di dunia ini, untuk apa belajar membuat interpreter atau compiler untuk sebuah bahasa?

Ada dua alasan:

Belajar membuat compiler merupakan latihan pemrograman yang bagus. Untuk membuat compiler, kita perlu mengetahui parsing, abstract syntax tree, dan aneka hal lain yang memerlukan algoritma dan struktur data yang kompleks.
Pengetahuan pembuatan compiler terutama parsing dan pembuatan abstract syntax tree dapat diaplikasikan ke berbagai bidang lain. Contoh aplikasi kedua ilmu tersebut misalnya source-to-source translators (penerjemahan otomatis dari satu bahasa pemrograman ke bahasa lain, misalnya f2c yang menerjemahkan FORTRAN ke C), refactoring tools, reengineering tools, metrics tools (mengukur jum lah baris kode/fungsi, dsb untuk metrik perangkat lunak), consistency checkers (memeriksa apakah kode program konsisten dengan aturan), dan lain-lain. Beberapa contoh aplikasi lain dari ilmu yang dipelajari ketika membuat compiler bisa dilihat di http://progtools.comlab.ox.ac.uk/members/torbjorn/thesis.

Tidak terlalu banyak orang yang belajar membuat compiler untuk general purpose language, kebanyakan orang belajar untuk membuat Domain specific language (DSL). DSL adalah bahasa yang digunakan hanya untuk aplikasi tertentu. Contoh DSL misalnya bahasa scripting di game, atau macro di word processor tertentu, bahkan Cascading Style Sheeet (CSS) pada HTML/XML juga bisa dipandang sebagai DSL. DSL biasanya jauh lebih sederhana dibandingkan general purpose language, karena tujuannya spesifik untuk domain tertentu.

Dalam bagian 1 ini saya akan membahas dasar teori parsing, teori yang saya bahas di sini singkat saja. Jika Anda ingin langsung praktik, silakan lanjut ke bagian kedua.

Cara Kerja Compiler

Compiler membaca sebuah source code dalam bentuk teks, menyatukan karakter-karakter yang berhubungan menjadi token, lalu memeriksa apakah token-token tersebut memenuhi grammar, setelah itu compiler akan memeriksa semantik input, dan membuat output dalam sebuah bahasa (yang umumnya adalah assembly). Jika outputnya adalah assembly maka proses berikutnya adalah assembling yang dilakukan dengan assembler untuk menghasilkan bahasa mesin. Proses terakhir untuk membuat executable file dilakukan oleh linker.

Mungkin terlalu banyak kata-kata asing di kalimat tersebut, secara singkat:

source code adalah kode program tekstual dalam bahasa tertentu
token adalah kumpulan karakter yang memiliki arti khusus. Misalnya token 123 adalah token angka seratus dua puluh tiga, tidak dipandang sebagai karakter terpisah 1, 2, dan 3.
grammar adalah tata bahasa. Misalnya dalam program kalkulator 11 + 23 merupakan sesuatu yang benar, tapi 12 + / 4 tidak benar (plus sebelum bagi tidak memiliki makna)
assembly adalah bahasa sederhana yang mudah diterjemahkan ke bahasa mesin. Tools untuk menerjemahkannya adalah assembler, dan prosessnya namanya assembling.
executable file adalah file program yang siap dijalankan
linker adalah tools yang akan menggabungkan kode mesin yang kita tulis dengan library
library adalah kumpulan kode yang disatukan dalam sebuah file yang dapat digunakan oleh sebuah program. Biasanya programmer tidak akan menulis sendiri kode untuk menghitung sinus, kosinus, dsb. Kode-kode standar ini biasanya ada pada sebuah library.

Fase dalam sebuah compiler

Urutan fase dalam sebuah compiler adalah: Lexical analysis/parsing, Semantic analysis, dan code generation. Tutorial ini tidak akan memisahkan bagian-bagian tersebut secara spesifik. Bahasa yang akan digunakan dalam tutorial ini cukup beragam, dimulai dengan Java namun berikutnya mungkin C juga akan dimasukkan.

Dasar-dasar parsing

Dasar parsing yang lengkap butuh beberapa minggu untuk menjelaskannya, tapi dalam praktik kita tidak perlu memahami 100% teori parsing untuk bisa membuat compiler. Saya akan merangkum dasar parsing ini dalam kurang dari 1000 kata.

Grammar adalah deskripsi formal suatu bahasa. Chomsky membagi grammar menjadi 4 tipe, dan hampir semua bahasa pemrograman merupakan bahasa dengan grammar tipe 2 (context-free grammar). Dalam tutorial ini tidak akan dibahas tipe grammar selain context-free. Umumnya grammar context free dinyatakan dalam notasi BNF (Backus Naur Form) atau EBNF (Extended BNF). Anda perlu mengerti sedikit BNF karena sintaks bahasa biasanya dinyatakan dalam BNF.

Lihat contoh grammar berikut (kita sebut ini grammar M) adalah:

<kalimat> ::= <katabenda> <katakerja> <katabenda>

<katabenda> ::= 'koala'|'KURSI'|'PISANG'

<katakerja> ::= 'MEMUKUL'|'MEMAKAN'|'MEMBUANG'

Semua kalimat ini valid menurut grammar di atas (atau dikatakan bahwa: kalimat-kalimat berikut ini berada dalam bahasa yang didefinisikan oleh grammar M):

KOALA MEMAKAN KURSI
KOALA MEMAKAN PISANG
KOALA MEMUKUL KURSI
KOALA MEMUKUL KOALA
PISANG MEMAKAN KOALA

Sebuah unit dalam sebuah bahasa (sebuah "kata") disebut sebagai "token", sebuah token biasanya adalah sebuah kata atau simbol. Sesuatu literal seperti 'KOALA', 'KURSI' yang tidak bisa dipecah lagi disebut sebagai terminal. Parsing (syntactic analysis) adalah proses untuk menganalisis token untuk menentukan struktur grammarnya. Diberikan salah satu kalimat di atas, kita bisa melakukan parsing untuk menentukan apakah kalimat-kalimat di atas memenuhi grammar M.

Proses parsing biasanya terdiri dari dua bagian: bagian pertama adalah yang menggabungkan karakter demi karakter untuk membuat token (biasanya dilakukan oleh bagian yang disebut scanner atau lexer), dan bagian kedua adalah yang menentukan apakah token-token tersebut memenuhi grammar (dilakukan oleh bagian yang disebut parser).

Proses syntactic analysis hanya memeriksa grammar, tapi tidak menangani semantik. Kalimat "PISANG MEMAKAN KOALA" mungkin tidak valid secara semantik (kecuali ada pisang mutan yang bisa memakan Koala), tapi valid secara grammar. Pada tahap ini jangan pedulikan dulu masalah semantik.

Lihat contoh lain berikut (kita sebut ini grammar N):

<kalimat> ::= <aksi>|<pernyataan>

<aksi> ::= <katabenda> <katakerja> <katabenda>

<pernyataan> ::= <katabenda> <adverb> <katasifat>

<katabenda> ::= 'KOALA'|'KURSI'|'PISANG'

<katakerja> ::= 'MEMUKUL'|'MEMAKAN'|'MEMBUANG'

<adverb> ::= 'SANGAT'|'AGAK'|''

<katasifat> ::= 'BESAR'|'KECIL'

Contoh kalimat untuk grammar tersebut:

KOALA MEMAKAN KURSI
KOALA AGAK BESAR

Ada dua jenis metode parsing, yaitu bottom up dan top down. Tools yang memakai pendekatan bottom up parsing adalah YACC/Bison dan Tools yang memakai untuk top down parsing adalah ANTLR. Kedua tools tersebut gratis, dan boleh digunakan untuk keperluan non komersial maupun komersial. Tools-tools tersebut juga bisa dipakai di sembarang sistem operasi, misalnya Linux, Windows, FreeBSD, Solaris, dan OS X.

Bottom Up parsing

Bottom Up parser berusaha mencocokkan input dengan aturan produksi. Dalam kalimat koala MEMAKAN KURSI, parser akan melihat kata KOALA, lalu mencari aturan apa yang menghasilkan KOALA, dan kesimpulannya adalah <katabenda>, lalu berikutnya kata MEMAKAN adalah <katakerja> dan KURSI adalah <katabenda>. Dari ketiga aturan tersebut, kita bisa mereduksi menjadi sebuah <aksi>, dan ternyata aksi ini bisa direduksi lagi menjadi <kalimat> sehingga input tersebut adalah valid.

Top down parsing

Top down parser berusaha mengekspansi aturan produksi, dan mencocokkannya dengan input. Parser jenis ini akan mencoba mengekspansi <kalimat> menjadi <aksi> atau <pernyataan>, pertama jenis <aksi> akan dicoba (nanti jika ternyata bagian ini gagal, bagian <pernyataan> akan dicoba). Dari <aksi> bisa diekspansi menjadi <katabenda> <katakerja> <katasifat>. Kata benda diekspansi menjadi KOALA, KURSI, atau PISANG. Ternyata input KOALA cocok dengan salah satu terminal tersebut, sehingga bisa disimpulkan untuk saat ini, bahwa KOALA adalah <katabenda>, berikutnya <katakerja> akan dicoba diekspansi menjadi MEMUKUL, MEMAKAN atau MEMBUANG, dan karena ditemukan MEMAKAN, maka ini akan disimpulkan bahwa ini adalah <katakerja>, demikian juga disimpulkan bahwa <katabenda> menghasilkan KURSI.

Masalah dengan parser top down yang sederhana adalah parser ini akan bingung dengan grammar yang sifatnya rekursif kiri. Misalnya grammar sederhana berikut adalah untuk ekspresi digit plus/minus digit:

<ekspresi> ::= <ekspresi> ('+'|'-') <term> | <term>
<term> := ['0'..'9']

Ketika ingin mencocokkan ekspresi, parser akan mencoba mengekspansi <ekspresi> menjadi <ekspressi> dan <ekspresi> menjadi <ekspresi>, dan demikian seterusnya. Masalah ini bisa diselesaikan dengan mengubah bentuk di atas menjadi bentuk non rekursif. Tapi dalam kebanyakan kasus, Anda tidak perlu khawatir karena tools modern sudah menangani kasus tersebut.

Anda dapat membaca aneka buku kompilasi atau aneka artikel wikipedia untuk mengenal lebih jauh teori pembuatan parser dan compiler.

blog comments powered by Disqus

Links: compiler tutorial2 tutorial3 tutorial4 tutorial5 tutorial6 tutorial7 tutorial8 tutorial9