Untuk apa membuat compiler ?

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

Ada dua alasan:

1. 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.

2. Aplikasi dari dua hal penting dalam pembuatan compiler (parsing dan pembuatan abstract syntax tre) sangat luas, misalnya source-to-source translators (menerjemahkan secara otomatis dari satu bahasa pemrograman ke bahasa lain, misalnya f2c yang menerjemahkan FORTRAN ke C), refactoring tools, reengineering tools, metrics tools (mengukur jumlah baris kode/fungsi, dsb untuk metrik perangkat lunak), consistency checkers (memeriksa apakah kode program konsisten dengan aturan), dan lain-lain (silakan lihat aplikasi lain 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 (misalnya bahasa scripting di game, atau macro di word processor tertentu, bahkan Cascading Style Sheeet 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). Proses berikutnya adalah assembling yang dilakukan assembler untuk menghasilkan bahasa mesin. Proses terakhir untuk membuat executable file dilakukan oleh linker.

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.