BAB II LANDASAN TEORI
2.1 Teori Himpunan 2.1.1 Himpunan dan Elemen himpunan Himpunan merupakan konsep abstrak dari kumpulan objek-objek. Objek-objek di sini memiliki arti yang sangat luas, karena bukan hanya mencakup benda-benda konkrit seperti jeruk, singa, dan sebagainya, melainkan juga mencakup hal-hal yang abstrak seperti bilangan 205, operasi penjumlahan, dan sebagainya. Dalam notasi matematis, himpunan ditulis sebagai daftar objek-objek yang diapit oleh tanda kurung kurawal, atau bisa juga ditulis menggunakan deskripsi sifat-sifatnya (walaupun ini dapat menimbulkan paradoks). Setiap objek tersebut disebut sebagai elemen himpunan. Himpunan itu sendiri dapat diberi nama, dan biasanya dituliskan dengan sebuah huruf besar. A = { jeruk, 8, :, { 5, 2, badak }, Joni } 2.1.2 Subhimpunan, kesamaan dua himpunan, dan ekivalensi dua himpunan Suatu himpunan A disebut sebagai subhimpunan dari himpunan B, atau A ⊂ B, jika setiap anggota himpunan A berada dalam himpunan B juga. Jika ternyata setiap anggota himpunan B terdapat juga di dalam A, maka A dan B memiliki anggotaanggota yang sama. Dengan demikian himpunan-himpunan A dan B dikatakan sama, ditulis A = B.
7
8 Jumlah anggota yang dimiliki A dituliskan sebagai |A|. Dua himpunan A dan B dikatakan ekivalen jika |A| = |B|. 2.1.3 Operasi-operasi pada himpunan Dua buah himpunan dapat dioperasikan untuk membentuk himpunan baru. Operasi-operasi tersebut adalah: • Komplemen Komplemen himpunan A, ditulis A , adalah himpunan yang semua anggota-anggotanya tidak terdapat dalam himpunan A, dalam suatu himpunan semesta tertentu. Dalam kaitan dengan visibilitas, maka suatu anggota kelas C yaitu s yang bersifat protected tidak dapat diakses oleh semua kelas yang bukan C atau bukan turunan dari C. Dengan demikian jika C adalah himpunan semua kelas-kelas turunan C beserta C sendiri, maka kelas-kelas yang terdapat dalam C tidak dapat mengakses s. • Gabungan (union) Gabungan dari dua himpunan, ditulis A ∪ B adalah himpunan yang mengandung baik anggota-anggota A maupun anggota-anggota B. Dalam kaitan dengan OOP, jika suatu objek hendak mengimplementasikan dua macam interface IA dan IB, maka objek tersebut harus memiliki metodametoda yang terdapat baik di dalam IA maupun di dalam IB. • Irisan (intersection) Irisan dari dua himpunan, ditulis A ∩ B adalah himpunan yang mengandung anggota-anggota A yang juga terdapat di dalam B. Sebagai
9 contoh, jika kelas A menurunkan A1 dan A2 (single inheritance), dengan
m(A), m(A1), dan m(A2) adalah himpunan anggota-anggota kelas A, A1, dan A2 secara berurutan, maka m(A) ⊂ m(A1), m(A) ⊂ m(A2), dan m(A1) ∩
m(A2) = m(A). • Beda (difference) Beda dari dua buah himpunan, ditulis A-B adalah himpunan yang anggotaanggotanya adalah anggota-anggota himpunan A yang tidak terdapat dalam himpunan B. Sebagai contoh, jika kelas A menurunkan kelas B, maka kelas B dapat mendefinisikan hanya anggota-anggota m(B)-m(A). • Beda setangkup (symmetric difference) Beda setangkup dua buah himpunan ditulis A⊕B, didefinisikan
A⊕B=(A∪B)-(A∩B). • Hasil kali Kartesius (Cartesian product) Hasil kali kartesius dari dua himpunan, ditulis A × B adalah himpunan yang anggota-anggotanya adalah pasangan berurutan dari anggota-anggota himpunan A dan B. Jika a adalah anggota A, dan b adalah anggota B, maka
A × B akan memiliki (a, b) sebagai anggotanya. Sebagai contoh, produksi tata bahasa bebas konteks merupakan perkalian kartesius dari himpunan nonterminal dengan himpunan string yang terdiri dari baik nonterminal maupun terminal.
10 • Himpunan kuasa (power set) Himpunan kuasa dari himpunan A adalah himpunan dari semua himpunan bagian yang mungkin dari himpunan A, dituliskan sebagai ℘(A) (Liu, 1985). Sebagai contoh, jika A={a,b,c} maka ℘(A)={∅, {a}, {b}, {c}, {a,
b}, {a, c}, {b, c}, {a, b, c}}. 2.1.4 Relasi biner Relasi biner (binary relation) R terhadap A dan B adalah himpunan pasanganpasangan berurutan antara anggota-anggota himpunan A dan himpunan B. Dengan demikian R ⊆ A × B. Jika a ∈ A, dan b ∈ B, dan (a, b) ∈ R, maka dapat dituliskan sebagai a R b (Liu, 1985). Relasi biner pada A adalah relasi biner anggota-anggota himpunan A terhadap anggota-anggota himpunan A itu sendiri. Relasi biner pada sebuah himpunan dapat memiliki sifat-sifat sebagai berikut: • Relasi refleksif Sebuah relasi R pada A disebut refleksif jika untuk setiap a ∈ A, (a, a) ∈ R. • Relasi irefleksif Sebuah relasi R pada A disebut irefleksif jika untuk setiap a ∈ A, (a, a) ∉ R.
11 • Relasi simetrik Sebuah relasi R pada A disebut simetrik jika untuk setiap a, b ∈ A, jika (a, b) ∈ R, maka (b, a) ∈ R juga. • Relasi antisimetrik Sebuah relasi R pada A disebut antisimetrik jika untuk setiap a, b ∈ A, jika (a, b) ∈ R, maka (b, a) ∈ R hanya berlaku jika a=b. Produksi tata bahasa haruslah bersifat antisimetrik karena jika tidak maka dapat terjadi suatu nonterminal diuraikan dan direduksi kembali. • Relasi transitif Sebuah relasi R pada A disebut transitif jika untuk setiap a, b, c ∈ A, jika berlaku (a, b) ∈ R dan (b, c) ∈ R, maka haruslah berlaku (a, c) ∈ R. Contoh relasi transitif adalah relasi < dan > pada bilangan bulat, juga relasi reduksi string oleh sebuah tata bahasa. • Relasi ekivalen Suatu relasi disebut relasi ekivalen jika relasi tersebut memiliki gabungan sifat refleksif, simetrik, dan transitif. Contoh dari relasi ekivalen adalah relasi = pada persamaan aljabar. 2.1.5 Penutup (closure) Misalkan P adalah sebuah himpunan sifat-sifat relasi. Jika R* adalah penutup-P (P – closure) dari relasi R, maka R* ⊃ R, dan R* memiliki sifat-sifat P. Sebagai contoh, terdapat relasi # sedemikian hingga:
12
a∈# (false or a) # a (true or a) # true Relasi ini merupakan evaluasi dari ekspresi yang terdiri dari false, true, dan operator or yang dituliskan di antara tanda kurung. Relasi # tidaklah refleksif karena tidak terdapat a # a. Jika $ adalah penutup refleksif (reflexive closure) dari #, maka untuk $ akan berlaku:
a∈$ (false or a) $ a (true or a) $ true
a$a Dengan demikian relasi $ memungkinkan untuk sebuah ekspresi tidak dievaluasi, karena (false or true) $ (false or true). Relasi $ tidaklah simetrik. Didefinisikan % sebagai penutup simetrik dari $. Dengan demikian % adalah penutup simetrik-refleksif (symmetric-reflexive closure) dari #, dan bagi % akan berlaku:
a, b ∈ % (false or a) % a (true or a) % true
a%a a%b→b%a
13 Relasi % tidak hanya mengevaluasi suatu ekspresi, melainkan dapat mengembangkan suatu ekspresi menjadi ekspresi yang lebih kompleks, misalnya (true or true) dapat menjadi (false or (true or true)). Penambahan sifat transitif terhadap % menyebabkan ekspresi dapat dievaluasi ataupun dikembangkan secara langsung, sementara akan membutuhkan lebih dari satu langkah pada relasi %. Jika > adalah penutup transitif (transitive-closure) dari %, atau merupakan penutup refleksif-simetrik-transitif (reflexive-symmetric-
transitive closure) dari #, maka akan berlaku: a, b ∈ > (false or a) > a (true or a) > true
a>a a>b→b>a a>b∧b>c→a>c Relasi dan penutup berguna dalam mendefinisikan aturan-aturan produksi suatu tata bahasa, proses reduksi suatu string, serta evaluasi suatu ekspresi. Penutup transitif (transitive closure) berguna untuk membangkitkan string dari sebuah nonterminal, dan reduksi string. 2.1.6 Fungsi Fungsi f yang memetakan himpunan A kepada B adalah himpunan bagian dari
A × B. Jika a ∈ A, maka hanya ada tepat satu anggota f yang mengandung a.
14
2.2 Bahasa Pemrograman 2.2.1 Kategori bahasa pemrograman Pada umumnya bahasa pemrograman dapat dibagi menjadi empat kategori: • Bahasa pemrograman fungsional • Bahasa pemrograman logik • Bahasa pemrograman imperatif • Bahasa pemrograman berorientasi objek Bahasa fungsional dan logik tidak akan dibahas di sini. 2.2.2 Bahasa pemrograman imperatif Elemen terkecil yang dapat dieksekusi dalam bahasa pemrograman imperatif adalah sebuah perintah. Perintah ini mengubah state awal menjadi state akhir.
State awal
Program
State akhir
Gambar 2.1 Perubahan state awal menjadi state akhir (sumber: Morgan (1994, p4))
Sebuah program dalam bahasa imperatif tersusun dari perintah-perintah yang masing-masing bertujuan untuk mengubah suatu prakondisi (precondition) atau
state awal menjadi paskakondisi (postcondition) atau state akhir. Sebuah state merupakan kumpulan variabel-variabel yang secara konkret pada komputer merupakan suatu sel memori tertentu, yang dapat berisi suatu nilai. Dengan demikian perintah assignment, yaitu mengasosiasikan suatu variabel dengan nilai tertentu, menjadi sangat dominan dalam bahasa imperatif.
15 B. Komponen-komponen bahasa pemrograman imperatif Berikut ini akan dijelaskan komponen-komponen bahasa pemrograman imperatif. Beberapa komponen mutlak ada (seperti nama), beberapa yang lain bisa dihilangkan, tetapi akan mengurangi readability dan writability suatu program. Nama Nama adalah barisan karakter yang diasosiasikan dengan suatu entiti dalam sebuah program. Hal-hal yang harus dipertimbangkan mengenai nama: • Karakter-karakter yang diijinkan untuk membentuk nama. Mengijinkan karakter-karakter aneh akan mengurangi readability dan writability. • Panjang maksimum yang diijinkan untuk nama dapat menurunkan readability jika terlalu panjang atau terlalu pendek. • Pembedaan huruf besar dan kecil • Kata-kata baku (reserved words), yaitu kata-kata yang tidak boleh didefinisikan ulang dalam program. Variabel Variabel adalah sebuah nama yang diasosiasikan dengan sel memori tertentu. Atribut-atribut variabel yang penting diperhatikan adalah: • Alamat/referensi memori yang ditunjuk oleh nama variabel tersebut • Tipe data, • Nilai, yaitu isi dari sel memori yang ditunjuknya • Masa aktif variabel (lifetime).
16 • Static binding dan dynamic binding. • Static type binding dan dynamic type binding. Tipe data Tipe data berkaitan dengan nilai apa yang dapat diasosiasikan dengan sebuah variabel, dan operasi-operasi apa yang dapat dilakukan terhadap variabel tersebut. Sebagai contoh, sebuah variabel dengan tipe data integer pada mesin 32-bit diijinkan untuk memiliki nilai -2147483648 hingga +2147483647 dan operasioperasi yang diijinkan adalah seperti penjumlahan, pengurangan, perkalian, dan beberapa operasi lainnya. Contoh lainnya, dalam bahasa Pascal jika a dan b adalah variabel bertipe integer, maka a+b berarti menjumlahkan kedua nilai yang dimiliki a dan b. Lain halnya jika a dan b bertipe string, a+b akan menggabungkan keduanya. Tipe data ordinal adalah tipe data untuk merepresentasikan elemenelemen yang terurut (Simons, 2002). Assignment
Assignment adalah pengubahan nilai suatu variabel, yang secara fisik berarti mengubah isi dari sel memori yang ditunjuk oleh variabel yang bersangkutan. Ekspresi Ekspresi merupakan barisan yang dibentuk dari kombinasi operator dan
operand. Ekspresi merupakan suatu mekanisme pengiriman nilai dalam serangkaian proses.
17 Struktur kendali (control structure) Struktur kendali (control structure) memungkinkan pengendalian alur program sehingga alur program dapat memiliki lebih dari satu kemungkinan. Struktur kendali yang mendasar adalah: • Seleksi dan lompatan Suatu pemrograman imperatif dapat memiliki hanya dua struktur kendali primitif, yaitu seleksi (selection) dan lompatan (jump). Kedua struktur kendali primitif ini saling ortogonal, dapat dikombinasikan untuk membentuk struktur kendali lain seperti perulangan, dan sebagainya. Bagaimana pun, penggunaan lompatan, yang biasanya dinamakan goto, sangat menyulitkan pembacaan program jika terlampau banyak digunakan (Djikstra, 1968). • Perulangan Struktur perulangan bertujuan untuk mengulang suatu blok statement. Struktur perulangan dapat dibentuk oleh seleksi dan lompatan. Ada tiga macam bentuk perulangan yang sering digunakan dalam bahasa pemrograman imperatif: a. Logical
posttest,
yaitu
perulangan
do..while,
atau
repeat..until dalam bahasa Object Pascal, mengerjakan suatu blok statement, dan ketika blok tersebut selesai dikerjakan, program akan menguji suatu kondisi. Jika kondisi terpenuhi, maka blok akan dikerjakan kembali. Paling sedikit satu kali blok statement akan
18 dikerjakan. Pada perulangan jenis ini pengujian kondisi diletakkan pada akhir blok. b. Logical pretest, yaitu perulangan while..do, menguji suatu kondisi, jika kondisi terpenuhi, maka blok akan dikerjakan. Selesai mengerjakan blok tersebut, kondisi diuji kembali. Dengan demikian dimungkinkan untuk tidak mengerjakan blok samasekali. Pada perulangan jenis pengujian dilakukan pada awal blok. c. Counter controlled, biasanya dalam bentuk perulangan for, mengulang suatu blok statement dengan menggunakan counter. Dalam bahasa C# terdapat foreach, yang tidak menggunakan counter, melainkan membaca satu per satu elemen array. Subprogram Subprogram adalah bagian dari program yang berdiri sendiri, sebagai abstraksi dari proses. Literal Literal adalah representasi data secara langsung dalam sebuah program. 15234 merupakan sebuah literal karena merepresentasikan data 15234. Literal yang umum terdapat dalam bahasa pemrograman adalah integer, string, dan floating-point. 2.2.3 Bahasa pemrograman berorientasi objek Bahasa pemrograman berorientasi objek menyediakan kemampuan untuk abstraksi bagi data dan proses, yang disatukan dalam sebuah tipe data abstrak yang disebut kelas.
19 • Enkapsulasi Setiap data dan operasi yang berkaitan dijadikan satu dalam sebuah kelas, sehingga data yang berkaitan tidak tersebar dan mudah ditemukan, karena diasosiasikan dengan suatu objek tertentu. • Inheritance
Inheritance atau penurunan dalam OOP berarti menghasilkan kelas baru dengan sifat-sifat yang dimiliki oleh kelas induknya (base class). Jika m(A) adalah himpunan anggota-anggota kelas A, dan i(A) adalah himpunan objek-objek yang mungkin diinstansiasikan dari A, dibedakan berdasarkan state yang dimilikinya. Jika A+ adalah kelas turunan A, maka
m(A) ⊆ m(A+). Dan |i(A+)| ≤ |i(A)|. Jika sifat-sifat dua atau lebih kelas dapat digabungkan sebagai kelas baru, hal ini disebut multiple inheritance. Multiple inheritance dipakai dalam C++, tetapi dapat menimbulkan beberapa masalah, seperti masalah penamaan metoda yang sama dari kedua kelas induk, sehingga multiple
inheritance tidak banyak dipakai dalam perancangan bahasa-bahasa pemrograman. • Polymorfisme dan dynamic binding Polimorfisme (polymorphism) mengijinkan suatu variabel dengan tipe suatu kelas untuk merepresentasikan objek kelas turunannya. Beberapa metoda dapat bersifat polimorfik (polymorphic), dalam arti nama metoda yang sama dari suatu kelas dapat memiliki implementasi yang berbeda dari
20 metoda kelas induknya. Dengan demikian dengan polimorfisme dapat dilakukan pengiriman pesan pada suatu objek tanpa harus diketahui tipe objek tersebut. Polimorfisme di dalam kode tujuan diimplementasikan dengan dynamic binding. Sebagai contoh dalam dunia nyata, kelas binatang merupakan kelas induk dari kelas mamalia dan kelas serangga. Karena semua binatang dapat berpindah tempat, maka pindahtempat merupakan salah satu metoda dalam kelas binatang. Baik mamalia maupun serangga memiliki metoda pindahtempat juga. Walaupun begitu, cara mamalia berpindah tempat berbeda dengan cara serangga berpindah tempat. Dengan demikian, metoda pindahtempat bersifat polimorfik. A. Komponen-komponen bahasa pemrograman berorientasi objek Kelas Kelas adalah sebuah template dari objek. Sebuah kelas adalah sebuah tipe data abstrak yang menyatukan data dengan proses. Data dinyatakan sebagai field, proses dinyatakan dalam metoda (method). Dengan demikian suatu kelas merupakan wujud dari enkapsulasi. Jika hendak dibuat suatu kelas yang memiliki metoda-metoda yang sama dengan suatu kelas lain, kelas baru ini dapat diturunkan dari kelas yang lain tersebut, sehingga tidak perlu mendefinisikan ulang metoda-metoda yang hendak dipakai. Hal ini merupakan wujud dari inheritance.
21 Kelas abstrak (abstract class) adalah kelas yang tidak berisi implementasi yang lengkap (samasekali tidak berisi implementasi jika benar-benar abstrak), berguna sebagai template bagi pembangunan kelas-kelas lain yang fungsinya lebih spesifik. Hal ini sangat berguna dalam kaitan dengan polimorfisme. Antarmuka (Interface) Antarmuka (interface) berlaku sebagai kelas abstrak, yang tidak memiliki implementasi
apa
pun.
Hanya
memperkenalkan
operasi-operasi
tanpa
mendefinisikan bagaimana seharusnya operasi tersebut dilakukan. Antarmuka harus diimplementasikan oleh suatu objek. Suatu variabel antarmuka dapat diasosiasikan dengan objek apa pun yang mengimplementasikan antarmuka tersebut. Field
Field adalah variabel-variabel yang merupakan anggota kelas, diasosiasikan dengan data tertentu. Metoda (method) Metoda (method) adalah subprogram yang disatukan dalam sebuah kelas. Metoda menunjukkan operasi yang dapat dilakukan terhadap suatu objek. Dengan kesatuan metoda dan field dalam sebuah objek, penulis program hanya perlu mengetahui operasi apa yang dapat dilakukan terhadap sebuah objek, dan data apa yang dapat diambil dari objek tersebut. Pemrogram tidak perlu mengetahui detail proses yang dilakukan oleh suatu objek.
22 B. Visibilitas Visibilitas memberikan batasan-batasan akses terhadap sebuah anggota kelas, berguna untuk menjaga agar informasi yang tidak diperlukan oleh objek lain tidak dapat diakses, dan memberi kemungkinan operasi-operasi yang jelas bagi objek lain. Ada tiga macam visibilitas yang digunakan secara umum: • Private, anggota-anggota kelas yang tidak dapat diakses selain oleh kelas itu sendiri. • Protected, anggota yang didefinisikan dalam sebuah kelas dapat diakses dalam kelas turunannya. • Public, anggota sebuah objek dapat diakses oleh objek lain. Tidak semua bahasa pemrograman menggunakan ketiganya. Beberapa bahasa pemrograman bahkan memiliki konsep yang berbeda-beda terhadap masing-masing visibilitas tersebut. Sebagai contoh, visibilitas private dalam C++ berarti dapat diakses oleh semua instance dari kelas yang sama, sedangkan dalam Delphi anggota kelas yang bersifat private dapat diakses oleh kelas lainnya dalam satu unit. 2.2.4 Kriteria evaluasi bahasa pemrograman Seperti telah disinggung dalam bab pendahuluan, ada tiga kriteria dalam menilai baik tidaknya suatu bahasa pemrograman. Kriteria yang dipaparkan di sini sesuai dengan kriteria yang dipaparkan oleh Sebesta (2002). Masing-masing tidak diukur secara kuantitatif.
23 A. Readability
Readability adalah mengenai mudah tidaknya suatu program yang ditulis dalam bahasa pemrograman tertentu untuk dapat dibaca dan dipahami maksudnya. B. Writability
Writability adalah mengenai mudah tidaknya menuliskan suatu program dalam bahasa pemrograman tertentu. Hal ini berkaitan dengan fitur-fitur yang disediakan. Semakin sedikit fitur-fitur yang disediakan, pemrogram harus membangun sendiri komponen-komponen yang mensimulasikan berbagai keperluannya. C. Reliability
Reliability atau reliabilitas menunjukkan bahwa suatu program yang ditulis dalam suatu bahasa pemrograman dapat melakukan tugasnya dengan baik dalam berbagai macam kondisi. Reliabilitas yang tinggi mendukung kemudahan dalam pengembangan suatu software.
Readability dan writability menentukan juga reliabilitas suatu bahasa pemrograman. D. Karakteristik yang berpengaruh pada masing-masing kriteria Karakteristik-karakteristik suatu bahasa pemrograman mempengaruhi ketiga kriteria yang telah disebutkan sebelumnya. Simplisitas Semakin sederhana suatu bahasa pemrograman, semakin sedikit fitur-fitur primitifnya. Semakin banyak fitur akan memaksa pemrogram untuk menghafalkan
24 banyak konstrak (penulisan) yang sebenarnya dapat disederhanakan. Jika terlampau banyak, akan mengakibatkan pemrogram hanya mempelajari sebagian dari bahasa pemrograman tersebut. Walaupun demikian, jumlah fitur yang terlalu sedikit akan menyebabkan penulisan program semakin panjang. Ortogonalitas Ortogonalitas dalam bahasa pemrograman menunjukkan bahwa beberapa konstrak-konstrak primitif dapat dikombinasikan membentuk struktur yang lebih kompleks. Ortogonalitas dan simplisitas saling terkait satu sama lain dalam menentukan
readability dan writability. Karena semakin banyak fitur primitif yang saling ortogonal justru menyebabkan program semakin kompleks. Program yang kompleks sukar dibaca maupun ditulis. Idealnya, sebuah bahasa pemrograman memiliki sedikit fitur primitif yang seluruhnya saling ortogonal. Struktur kendali Jika suatu bahasa pemrograman hanya menyediakan struktur kendali if dan
goto, misalnya, maka walaupun simplisitasnya tinggi dan ortogonalitasnya tinggi (if dan goto dapat digunakan untuk membangun struktur kendali yang lebih kompleks), program akan menjadi sukar dibaca. Penyediaan struktur kendali yang cukup akan meningkatkan readibiliy dan writability sebuah bahasa pemrograman. Umumnya, struktur kendali seleksi if..then..else dan switch, struktur perulangan pretest, posttest, dan
counter, serta procedure call cukup untuk memenuhi kebutuhan pemrograman.
25 Tipe data dan struktur Setidaknya suatu bahasa pemrograman imperatif harus menyediakan tipe data primitif integer, floating-point, string, dan boolean. Penggunaan tipe data merupakan hal yang penting untuk meningkatkan readability dan writability. Katakanlah sebuah bahasa pemrograman tidak mengenal tipe data string. String harus diemulasikan dengan menggunakan integer array. Maka untuk menuliskan string “Halo” saja kita perlu menuliskan (0x48, 0x61, 0x6C, 0x6F). Hal ini jelas sangat menyulitkan. Selain terdapatnya tipe data primitif, terdapatnya konstrak untuk struktur data sangat
meningkatkan
readability
dan
writability.
Struktur
data
record
memungkinkan pemrogram untuk menyatukan berbagai variabel dalam sebuah variabel lain, sedangkan array memudahkan pemrogram untuk menyatukan data dalam jumlah besar. Dalam OOP kelas merupakan struktur yang menggabungkan data dan proses. Disain sintaks Disain sintaks berkaitan dengan bentuk elemen-elemen dasar suatu bahasa, mencakup disediakannya kata-kata kunci yang cukup untuk merepresentasikan berbagai hal, kejelasan penulisan, dan sebagainya. Hal ini juga mencakup pengertian yang diasosiasikan terhadap suatu nama, seperti if untuk pencabangan, = untuk assignment, dan sebagainya.
26 Sebagai contoh, deklarasi metoda dalam DOGI menggunakan kata kunci method agar pembaca program dapat dengan mudah membedakannya dengan jenis anggota kelas yang lain. Abstraksi Abstraksi memungkinkan pemrogram untuk mendefinisikan berbagai struktur maupun operasi, tanpa harus mengetahui bagaimana implementasinya. Dukungan terhadap abstraksi yang umum ada dalam bahasa pemrograman adalah subprogram, kelas abstrak dan interface. Ekspresivitas Ekspresivitas berkaitan dengan fitur-fitur yang memungkinkan pemrogram untuk menggantikan cara penulisan yang kompleks dengan yang lebih sederhana. Sebagai contoh, walaupun struktur perulangan for dapat diemulasikan dengan while..do, tetapi struktur for lebih nyaman digunakan untuk perulangan yang membutuhkan variabel penghitung. Bahasa DOGI mendukung pendefinisikan sendiri penulisan yang paling intuitif untuk melakukan operasi terhadap suatu objek. Type checking
Type checking memungkinkan pendeteksian kesalahan lebih dini, yaitu pada waktu kompilasi. Assignment dua variabel yang memiliki tipe data yang saling tidak kompatibel dapat menimbulkan masalah serius jika dapat dikompilasi. Karena itu sebaiknya kompiler memberitahukan kesalahan ini pada waktu kompilasi. Hal ini lebih berkaitan dengan masalah reliability.
27 Penanganan Kesalahan (Exception handling) Suatu program harus dapat memastikan bahwa setiap kesalahan yang terjadi pada waktu program berjalan (run-time error) tidak akan menyebabkan program tersebut berhenti kecuali jika kesalahan tersebut terlalu fatal. Karena itu suatu program perlu menyediakan sistem penanganan kesalahan (exception handler). Suatu bahasa pemrograman dapat menyediakan konstrak khusus bagi penanganan kesalahan. Hal ini akan meningkatkan reliability. DOGI belum menyediakan penangan kesalahan. Aliasing
Aliasing dapat terjadi jika dua buah nama menunjuk pada suatu hal yang sama (secara numerik). Sebagai contoh, variabel a dan b bukan merupakan pointer maupun reference, tetapi memiliki lokasi memori yang sama. Dengan demikian, setiap perubahan pada b akan menyebabkan a berubah. Hal demikian akan mengurangi reliability.
2.3 Teori bahasa dan Otomata Sebuah bahasa adalah sebuah himpunan dari barisan simbol-simbol, yang disebut string. Dalam bahasa Indonesia, misalnya, simbol-simbol adalah keduapuluhenam abjad dan angka, ditambah tanda baca. Kombinasi simbol-simbol tersebut yang disusun dalam sebuah barisan dapat membentuk kalimat-kalimat dalam bahasa Indonesia. Untuk seterusnya simbol-simbol akan disebut abjad.
28 Himpunan abjad suatu bahasa biasanya diberi notasi Σ. Suatu string kosong adalah string yang tidak mengandung abjad apa pun, dinotasikan sebagai ε. Jumlah simbol-simbol yang dipakai untuk membentuk string s disebut panjang string s, dituliskan dengan notasi |s|. Karena string ε tidak terdiri dari abjad apa pun, maka |ε|=0. Bahasa yang terdiri dari semua kemungkinan string yang dapat dibentuk berdasarkan setiap abjad dalam Σ disebut bahasa universal dari Σ, diberi notasi Σ*. Sebagai contoh, jika Σ = { a, o, u } maka Σ* = { ε, a, o, u, aa, ao, au, oa, oo, ou, ua,
uo, uu, aaa, aao, … }. Dengan demikian hubungan antara sebuah bahasa L berdasarkan abjad Σ dengan bahasa universal dari Σ adalah L ⊆ Σ* 2.3.1 Tata bahasa (grammar) Biasanya dalam literatur-literatur selalu dipisahkan definisi formal antara tata bahasa jenis yang satu dengan yang lain. Karena definisi semua jenis tata bahasa dapat digeneralisasikan, dalam skripsi ini hanya akan dituliskan satu definisi yang berlaku untuk semuanya. Suatu tata bahasa adalah merupakan 4-tupel G = (N, T, P, S) (Hopcroft et al., 1979), dan bahasa yang dibentuk oleh G disebut bahasa L(G). Masing-masing dijelaskan sebagai berikut. • N adalah himpunan simbol-simbol nonterminal • T adalah himpunan simbol-simbol terminal • P adalah himpunan produksi-produksi atau aturan pengganti, dengan
P ⊂ (N ∪T)* × (N ∪T)*
29 • S adalah simbol awal (start symbol), yaitu
S∈N Digunakan untuk menunjukkan bahwa sebuah produksi yang diawali dengan S harus menjadi produksi yang pertama kali dipilih. Jika α, β dan γ adalah anggota-anggota dari (N∪T)*, maka produksi (α, β) digunakan untuk mengganti kemunculan α dalam γ dengan β. Sebagai contoh: Sebuah tata bahasa G = (N, T, P, S) dengan
N={E} T = { 0, 1, 2, +, - } P = { (E, E+E), (E, E-E), (E, 0), (E, 1), (E, 2) } S=E Dengan demikian tata bahasa G akan membentuk suatu bahasa L(G) yang secara esensial adalah himpunan string, dapat dituliskan dalam batasan-batasan berikut ini. 0, 1, 2 ∈ L(G)
a ∈ L(G) ∧ b ∈ L(G) → a+b ∈ L(G) a ∈ L(G) ∧ b ∈ L(G) → a-b ∈ L(G) Contoh beberapa anggota L(G) adalah 0, 0+2-1-2+0, dan 1-2-2.
30 Biasanya produksi-produksi dalam P tidak dinyatakan dalam bentuk pasangan berurutan, melainkan dengan notasi produksi menggunakan tanda panah (→). Dengan demikian produksi P di atas dapat dituliskan: E
→
E+E
(1)
E
→
E–E
(2)
E
→
0
(3)
E
→
1
(4)
E
→
2
(5)
Agar perbedaan nonterminal dengan terminal dapat terlihat dengan jelas, dalam skripsi ini terminal selalu ditulis dengan huruf tebal, sedangkan nonterminal tidak. Notasi ⇒ digunakan untuk mengganti bagian dari string γ dengan salah satu produksi dalam P. Notasi ⇒* menyatakan bahwa penggantian tersebut bisa terdiri dari beberapa langkah penggantian tunggal oleh ⇒. Relasi ⇒* adalah transitive-
closure dari relasi ⇒. Sebagai contoh untuk tata bahasa G di atas: E
⇒
E+E
⇒
E+E+E
(1)
⇒
E–E+E+E
(2)
⇒
1–E+E+E
(4)
⇒
1–2+E+E
(5)
⇒
1–2+0+E
(3)
⇒
1–2+0+1
(4)
Dengan demikian E ⇒* 1-2+0+1.
(produksi 1)
31 2.3.2 Hirarki bahasa menurut Chomsky Ada empat jenis bahasa menurut Chomsky, yaitu: • Bahasa jenis-0 atau bahasa tak terbatas (unrestricted language) Bahasa jenis-0 dibentuk dari tata bahasa yang aturan-aturan produksinya tidak dibatasi. • Bahasa jenis-1 atau bahasa sensitif konteks (context-sensitive language) Bahasa jenis-1 dibentuk dari tata bahasa yang aturan-aturan produksinya berbentuk: α → β , |β| ≥ |α|. α, β ∈ (N ∪ T)* • Bahasa jenis-2 atau bahasa bebas konteks (context-free language) Bahasa jenis-2 dibentuk dari tata bahasa yang setiap produksinya berbentuk:
A→α A∈N α ∈ (N ∪ T)* • Bahasa jenis-3 atau bahasa reguler (regular language) Bahasa jenis-3 dibentuk dari tata bahasa yang setiap produksinya berbentuk:
A → a atau A → a B
32 atau setiap produksinya berbentuk:
A → a atau A → B a A, B ∈ N a ∈ T* Bahasa pemrograman pada umumnya dapat dibentuk dengan tata bahasa bebas konteks. 2.3.3 Backus-Naur Form dan Extended Backus-Naur Form Bentuk Backus-Naur (Backus-Naur Form) hampir sama dengan tata bahasa bebas konteks (Sebesta, 2002, p110). Karena nonterminal-nonterminal dalam sebuah spesifikasi bahasa pemrograman sangat banyak, maka tidak cukup menuliskan setiap nonterminal menggunakan satu huruf. Karena itu dalam spesifikasi bahasa setiap nonterminal dalam BNF sering dituliskan di dalam tanda <..>, walaupun notasi ini tidak selalu dipakai. Sebagai contoh, salah satu produksi E pada contoh tata bahasa sebelumnya dapat dinyatakan dengan <ekspresi> → <ekspresi> + <ekspresi>.
Extended Backus-Naur Form (EBNF) adalah BNF yang diberi tambahan notasi untuk mempersingkat penulisan. Notasi-notasi tersebut dijelaskan sebagai berikut. • Bagian optional Dituliskan di antara tanda kurung siku, menunjukkan bahwa bagian tersebut boleh tidak ada.
33 Contoh: <seleksi>
→
if ( <ekspresi_boolean> ) <statement> [ else <statement> ]
merupakan kependekan dari <seleksi>
→
if ( <ekspresi_boolean> ) <statement>
<seleksi>
→
if ( <ekspresi_boolean> ) <statement> else <statement>
• Bagian yang dapat diulang Dituliskan di antara kurung kurawal, merupakan bagian yang dapat ada atau tidak, dan jika ada boleh lebih dari satu. Contoh: <exprs>
→
<expr> { , <expr> }
merupakan kependekan dari: <exprs>
→
<expr>
→
ε
→
, <exprs>
• Pemilihan Jika terdapat (a | b | c | d) maka penggantian dapat memilih antara satu dari keempat produksi tersebut. Contoh:
→
E (+|-)
Merupakan kependekan dari:
→
E +
→
E -
34 2.3.4 Otomata Otomata dapat digunakan untuk mengenali bahasa-bahasa. Jenis otomata yang akan dibahas di sini adalah otomata berhingga nondeterministik (nondeterministic
finite automata atau NFA), otomata berhingga deterministik (deterministic finite automata atau DFA), dan otomata pushdown (pushdown automata atau PDA). A. Otomata berhingga deterministik Otomata berhingga deterministik atau DFA adalah 5-tupel (Q, Σ, q0, F, δ), masing-masing dijelaskan sebagai berikut: • Q adalah himpunan berhingga dari state • Σ adalah himpunan berhingga abjad-abjad • q0 ∈ Q adalah state awal (initial state) • F ⊂ Q adalah himpunan state yang merupakan state akhir (final states) • δ: Q × Σ → Q adalah fungsi yang memetakan pasangan state dan abjad pada state lainnya, disebut sebagai fungsi transisi. DFA dapat digunakan untuk mengenali bahasa jenis-3 atau bahasa reguler. B. Otomata berhingga nondeterministik Otomata berhingga nondeterministik atau NFA adalah 5-tupel (Q, Σ, q0, F, ∆), masing-masing dijelaskan sebagai berikut: • Q adalah himpunan berhingga dari state • Σ adalah himpunan berhingga abjad-abjad • q0 ∈ Q adalah state awal (initial state)
35 • F ⊂ Q adalah himpunan state yang merupakan state akhir (final states) • δ: Q × Σ → ℘(Q) adalah fungsi yang memetakan pasangan state dan abjad pada sebuah himpunan state, disebut sebagai fungsi transisi. NFA dapat digunakan untuk mengenali bahasa jenis-3 atau bahasa reguler. Dapat dibuktikan bahwa sebuah NFA memiliki sebuah DFA padanannya (Hopcroft et al., 1979, pp22-23). Dengan demikian jika MN adalah sebuah NFA, dan MD adalah sebuah DFA, dan R adalah sebuah tata bahasa reguler, maka L(MN) = L(MD) = L(R). C. Otomata pushdown Otomata pushdown atau PDA adalah 7-tupel (Q, Σ, Γ, δ, q0, Z0, F), masingmasing dijelaskan sebagai berikut: • Q adalah himpunan berhingga dari state • Σ adalah himpunan berhingga abjad-abjad • Γ adalah himpunan berhingga simbol-simbol stack • q0 ∈ Q adalah state awal (initial state) • Z0 ∈ Γ adalah simbol awal stack (start symbol) • F ⊆ Q adalah himpunan state yang merupakan state akhir (final states) • δ: Q × (Σ ∪ {ε}) × Γ → Q × Γ*, adalah fungsi transisi PDA digunakan untuk mengenali bahasa bebas konteks. Untuk tata bahasa bebas konteks G terdapat PDA MP sedemikian hingga L(MP) = L(G).
36
2.4 Teknik kompilasi 2.4.1 Proses kompilasi Kompilasi adalah penerjemahkan suatu kode program dalam sebuah bahasa menjadi kode program dalam bahasa yang lain, yang akan dieksekusi oleh sebuah komputer. Komputer di sini tidak perlu merupakan suatu hardware, tetapi bisa merupakan sebuah komputer semu (virtual computer), yakni sebuah program yang berlaku sebagai sebuah komputer. Sebagai contoh, object code hasil kompilasi program yang ditulis dalam bahasa C++ akan dijalankan langsung oleh sistem operasi. Sedangkan bytecode hasil kompilasi program dalam bahasa Java akan dijalankan oleh Java Virtual Machine. Dalam hal ini sistem operasi dan Java Virtual Machine berlaku sebagai komputer semu. Urut-urutan pengerjaan kompilasi adalah seperti yang terlihat pada diagram berikut:
37
Kode sum b er
Penganalisis Leksikal
Penganalisis Sintaks
Tabe l Sim b ol
Penganalisis sem an tik
Pe m b angkit kod e an tara O ptim asi
Pe m b angkit kod e tujuan
Kode Tuju an
Gambar 2.2 Proses kompilasi (sumber: Sebesta (2002))
Sebuah kode program dalam bahasa sumber akan dibaca per karakter oleh penganalisis leksikal (lexical analyzer), untuk dimengerti sebagai satuan-satuan kecil yang disebut lexeme. Penganalisis leksikal menggunakan tata bahasa reguler yang mengimplementasikan DFA untuk membedakan setiap lexeme. Tidak semua karakter harus diperhatikan, seperti karakter-karakter spasi dan line feed. Penganalisis leksikal untuk DOGI dibuat menggunakan program Flex.
38 Barisan lexeme dikirim oleh penganalisis leksikal kepada penganalisis sintaks (syntax analyzer). Tugas dari penganalisis sintaks adalah membentuk pohon pengurai untuk memeriksa keabsahan dari struktur program yang dibuat. Proses ini juga disebut dengan penguraian atau parsing. Penganalisis leksikal biasanya merupakan implementasi dari DPDA dan struktur sintaks bahasa sumber dirancang agar memenuhi tata bahasa bebas konteks deterministik. Penganalisis sintaks untuk DOGI dibuat menggunakan program Bison. Jika penganalisis sintaks memeriksa struktur, maka penganalisis semantik (semantic analyzer) memeriksa pengertian dari program tersebut. Sebagai contoh, pada potongan program C++ berikut ini: char *str; int index; str = index + str;
Sekalipun secara sintaks benar, namun secara semantik salah, karena str tidak kompatibel dengan index. Biasanya penganalisis semantik tidak dipisahkan dengan pembangkit kode antara (intermediate code generator). Pembangkit kode antara akan menghasilkan kode dalam bahasa antara yang berbeda dari bahasa sumber maupun tujuan. Kode antara berguna dalam optimasi, karena kode tujuan biasanya lebih sulit untuk dioptimalkan. Kode antara akan diterjemahkan oleh pembangkit kode (code
generator) menjadi kode dalam bahasa tujuan.
39 Keseluruhan proses yang telah disebutkan di atas memerlukan bantuan tabel simbol (symbol table), yang berisi informasi mengenai simbol-simbol yang digunakan dalam kode sumber. 2.4.2 Semantik operasional Aturan semantik adalah aturan yang menggambarkan arti dari setiap produksi dalam sebuah bahasa pemrograman. Bentuk aturan semantik yang umum dipakai dalam pembuatan kompiler adalah semantik operasional. Semantik operasional mendeskripsikan arti dari sebuah produksi dengan serangkaian kode yang akan dieksekusi oleh suatu mesin virtual. Semantik operasional digunakan dalam input file Bison, untuk mendeskripsikan aksi yang akan dilakukan berkaitan dengan produksi tertentu. Sebagai contoh, produksi tata bahasa: statement
→
subProgram { call subProgram.address }
Menunjukkan bahwa produksi tersebut memiliki arti operasi call subProgram.address.
