TEKNIK KOMPILASI
TEKNIK KOMPILASI
Firrar Utdirartatmo
Kat a Pengantar
Penulis memberanikan diri untuk menyusun buku ini karena melihat kenyataan bahwa teknik kompilasi merupakan mata kuliah yang diajarkan pada jurusan-jurusan informatika atau ilmu komputer. Sementara buku-buku referensi yang membahas mengenai materi kuliah tersebut, yang berbahasa Indonesia masih sangat jarang ditemukan. Penulis memahami masih banyak mahasiswa yang mengalami kesulitan untuk membaca text-book berbahasa asing. Buku ini ditujukan terutama untuk dibaca oleh para mahasiswa yang sudah pernah memperoleh perkuliahan teori bahasa dan otomata. Meskipun begitu mereka yang belum pernah mempelajarinya tidak akan terlalu memperoleh kesulitan, karena penulis berusaha mengulang sedikit konsep-konsep yang penting dan perlu untuk diketahui. Untuk mereka yang belum mempelajari teori bahasa diharapkan memperdalam sendiri pemahaman teori bahasa, khususnya mengenai otomata berhingga (finite state automata), aturan produksi, dan tata bahasa bebas konteks (context free grammar). Diharapkan pembaca telah mengenal bahasa pemrograman tingkat tinggi dan struktur data. Pengetahuan mengenai bahasa assembly akan banyak membantu. Bisa dikatakan teknik kompilasi merupakan penerapan konsep-konsep yang sudah dipelajari pada teori bahasa dan otomata. Penulis mencoba memberikan banyak contoh-contoh yang berkaitan dengan suatu teori dalam setiap bab, untuk mempercepat pemahaman. Contoh-contoh yang digunakan kebanyakan memiliki kemiripan dengan bahasa Pascal. Hal ini disengaja karena bahasa Pascal lebih mudah untuk dibaca dan dipahami.
vi
Teknik Kompilasi
Listing program pada lampiran dibuat dengan menggunakan Turbo Pascal. Diharapkan dengan mencoba-coba sendiri program pada lampiran tersebut akan membantu pemahaman pembaca mengenai pengembangan sebuah kompilator. Minimal para pembaca dapat memahami mekanisme kerja sebuah kompilator. Mereka yang tertarik disarankan pula untuk membaca buku-buku lain mengenai teknik kompilasi, khususnya yang terdapat pada daftar pustaka. Sehingga diharapkan mampu melakukan pengembangan suatu kompilator yang lengkap. Penulis berterima kasih kepada Bapak Dr. Ing. Farid Wazdi, yang telah memberikan perkuliahan Teknik Kompilasi selama penulis menuntut ilmu di jurusan Teknik Informatika Institut Teknologi Bandung. Penulis juga mengucapkan terimakasih kepada segenap pihak yang telah membantu dan memberikan masukan bagi penulis, sehingga dapat menyelesaikan buku ini. Semoga buku ini dapat bermanfaat bagi pembaca, minimal menjadi suatu panduan awal untuk mempermudah mereka yang ingin mempelajari teknik kompilasi. Penulis memahami kekurangankekurangan yang terdapat pada buku ini karena keterbatasan pengalaman penulis, dan berharap pembaca bersedia memberikan koreksi dan saran kepada penulis. Penulis dapat dicapai pada . Yogyakarta, Januari 2001 Firrar Utdirartatmo
Daft ar I si
KATA PENGANTAR DAFTAR ISI DAFTAR ISTILAH BAB 1. PENDAHULUAN 1.1 Bahasa Pemrograman 1.2 Translator 1.3 Model Kompilator 1.4 Mutu Kompilator 1.5 Pembuatan Kompilator LATIHAN
v vii xi 1 1 3 5 11 13 14
BAB 2. PERANCANGAN BAHASA PEMROGRAMAN 2.1 Sumber Perancangan Bahasa Pemrograman 2.2 Tujuan Perancangan Bahasa Pemrograman 2.3 Detil Rancangan 2.4 Skenario Perancangan LATIHAN
17 17 18 22 32 32
BAB 3. KONSEP DAN NOTASI BAHASA 3.1 Hirarki Chomsky 3.2 Diagram Keadaan 3.3 Notasi BNF 3.4 Diagram Sintaks LATIHAN
35 35 39 40 40 41
BAB 4. ANALISIS LEKSIKAL 4.1 Tugas Scanner 4.2 Besaran Leksik LATIHAN
43 43 43 49
viii
Teknik Kompilasi
BAB 5. ANALISIS SINTAKSIS 5.1 Pohon Sintaks 5.2 Metode Parsing 5.3 Parsing dengan Brute Force 5.4 Parsing dengan Recursive Descent Parser LATIHAN
51 51 55 55 60 66
BAB 6. ANALISIS SEMANTIK, KODE ANTARA, DAN PEMBANGKITAN KODE 6.1 Analisis Semantik 6.2 Kode Antara 6.3 Notasi Postfix 6.4 Notasi N-Tuple 6.5 Pembangkitan Kode LATIHAN
67 67 69 69 71 73 75
BAB 7. CARA PENANGANAN KESALAHAN 7.1 Kesalahan Program 7.2 Penanganan Kesalahan 7.3 Reaksi Kompilator pada Kesalahan 7.4 Error Recovery 7.5 Error Repair LATIHAN
77 77 78 78 79 81 82
BAB 8. TEKNIK OPTIMASI 8.1 Dependensi Optimasi 8.2 Optimasi Lokal 8.3 Optimasi Global LATIHAN
83 83 83 85 87
BAB 9. TABEL INFORMASI 9.1 Kegunaan Tabel Informasi 9.2 Implementasi Tabel Informasi 9.3 Interaksi Antar Tabel 9.4 Contoh Implementasi Tabel Simbol LATIHAN
89 89 92 96 96 100
DAFTAR PUSTAKA LAMPIRAN 1 LAMPIRAN 2 LAMPIRAN 3 LAMPIRAN 4 LAMPIRAN 5
101 103 109 121 125 135
Daftar Isi
ix
LAMPIRAN 6 LAMPIRAN 7 LAMPIRAN 8 LAMPIRAN 9 LAMPIRAN 10
139 141 171 177 183
DAFTAR INDEKS
187
Pendahul uan
1.1 BAHASA PEMROGRAMAN Manusia dapat melakukan interaksi secara efektif dengan menggunakan media bahasa. Bahasa memungkinkan penyampaian gagasan dan pemikiran, tanpa itu komunikasi akan sulit terjadi. Dalam lingkungan pemrograman komputer, bahasa pemrograman bertindak sebagai sarana komunikasi antara manusia dan permasalahannya dengan komputer yang dipakai untuk membantu memperoleh pemecahan. Bahasa pemrograman menjembatani antara pemikiran manusia yang sering tidak terstruktur dengan kepastian yang diperlukan oleh komputer untuk melakukan eksekusi. Suatu solusi untuk suatu masalah akan menjadi lebih mudah bila bahasa pemrograman yang dipergunakan lebih dekat dengan permasalahan tersebut. Oleh karena itu, bahasa harus memiliki konstruksi yang merefleksikan terminologi dan elemen yang dipergunakan dalam mendeskripsikan masalah dan independen dari komputer yang dipergunakan. Bahasa pemrograman seperti ini biasanya bahasa tingkat tinggi. Komputer digital, di sisi lain, menerima dan memahami hanya bahasa tingkat rendah mereka sendiri, terdiri dari deretan nol dan satu, yang sulit dipahami oleh manusia. Bahasa pemrograman berdasarkan tingkat ketergantungannya dengan mesin bisa meliputi: 1. Bahasa mesin Merupakan bentuk terendah dari bahasa komputer. Setiap instruksi dalam program direpresentasikan dengan kode numerik, yang secara fisik berupa deretan angka 0 dan 1. Sekumpulan
2
Teknik Kompilasi
instruksi dalam bahasa mesin bisa dibentuk menjadi microcode, yaitu semacam prosedur dalam bahasa mesin. 2. Bahasa assembly Merupakan bentuk simbolik dari bahasa mesin. Setiap kode operasi memiliki kode simbolik, misalnya ADD untuk penjumlahan (addition) dan MUL untuk perkalian (multiplication). Sekumpulan instruksi dalam bahasa assembly bisa dibentuk menjadi makroinstruksi. Pada bahasa assembly tersedia alat bantu untuk diagnostik atau debug yang tidak terdapat pada bahasa mesin. Contoh produk yang ada untuk pengembangan dan debug bahasa assembly di pasaran saat ini, misalnya Turbo Assembler dari Borland, Macro Assembler dari Microsoft, DEBUG yang tersedia pada DOS, dan Turbo Debugger. Instruksi dalam bahasa Assembly biasanya terdiri dari beberapa field, misalnya field operasi diikuti satu atau lebih operan. 3. Bahasa tingkat tinggi (user oriented) Disebut tingkat tinggi karena lebih dekat dengan manusia. Memberikan fasilitas yang lebih banyak, kontrol program yang terstruktur, kalang (nested), block, dan prosedur. Contohnya: Pascal, BASIC 4. Bahasa yang problem oriented Memungkinkan penyelesaian untuk suatu masalah atau aplikasi yang spesifik. Contohnya: SQL (Structured Query Language) untuk aplikasi database, COGO untuk aplikasi teknik sipil. Bahasa yang problem oriented kadang dimasukkan pula sebagai bahasa tingkat tinggi. Dalam buku ini akan difokuskan pada pengembangan kompilator untuk bahasa tingkat tinggi prosedural seperti Pascal. Keuntungan bahasa tingkat tinggi dibandingkan bahasa tingkat rendah sebagai berikut: 1. Kemudahan untuk dipelajari, tidak membutuhkan latar belakang pengetahuan mengenai perangkat keras (hardware)karena sifatnya yang machine independent. 2. Lebih mendekati permasalahan yang akan diselesaikan 3. Pemrogram tidak perlu mengetahui bagaimana representasi data ke dalam bentuk internal di memory. Kemampuan untuk konversi data, seperti floating point misalnya sudah tersedia. Pe-
Pendahuluan
4.
5.
6. 7.
8. 9.
3
kerjaan tersebut ditangani oleh suatu sistem yang mentranslasikan program bahasa tingkat tinggi ke dalam bahasa mesin. Memberikan banyak pilihan struktur kontrol seperti: • kondisional (IF-THEN-ELSE) • looping (REPEAT..UNTIL, FOR) • struktur blok (BEGIN..END) • nested statement Struktur kontrol ini memberikan fasilitas untuk pemrograman terstruktur, sehingga program mudah dibaca, dipahami dan dimodifikasi. Ini akan mengurangi biaya pemrograman karena program lebih sederhana. Program lebih mudah di-debug. Bahasa tingkat tinggi menyediakan konstruksi yang mengurangi kesalahan pemrograman yang biasa muncul pada bahasa tingkat rendah. Sebagai contoh, deklarasi suatu variabel akan menjadi sesuatu yang berguna dalam mendeteksi kesalahan penggunaan variabel. Bahasa-bahasa biasanya mengharuskan penggunaan pointer secara konsisten. Suatu program yang terstruktur lebih mudah di-debug daripada yang tidak terstruktur. Kemampuan struktur data yang lebih baik, sehingga memfasilitasi pengekspresian suatu solusi dari masalah tertentu. Karena ketersediaan feature seperti prosedur, bahasa tingkat tinggi memungkinkan suatu deskripsi modular dan hirarkis dalam pemrograman. Suatu pekerjaan bisa diserahkan pada suatu tim, dan memungkinkan pembagian kerja. Kompatibilitas dan dokumentasi yang lebih baik dalam pengembangan program Tidak bergantung pada mesin (machine independent) sehingga memiliki portabilitas tinggi. Program hanya memerlukan sedikit perubahan untuk bisa dieksekusi pada mesin yang berbeda arsitektur internalnya dan instruksi bahasa mesinnya. Portabilitas ini akan mengurangi biaya.
Agar dapat dieksekusi, sebuah program dalam bahasa tingkat tinggi tentu saja harus ditranslasikan ke dalam bahasa mesin. Pada bagian berikutnya akan dibahas mengenai translator. 1.2 TRANSLATOR Sebuah translator melakukan pengubahan source code/source program (program sumber) ke dalam target code/object code/object
