BAB II TINJAUAN PUSTAKA
2.1 Sintaks Program Komputer Kruse (1987) Mendefinisikan sintaks pada program komputer merupakan representasi dari struktur logika penulis program untuk mencapai tujuan atau output yang dikehendaki. Sintaks dapat ditulis dalam berbagai bahasa pemrograman seperti bahasa C, Java, C++, dsb. Penulisan sintaks untuk suatu program dengan suatu tujuan bisa dituliskan dengan sintaks yang berbeda. Misalnya terdapat 2 orang programmer A dan B yang bertujuan untuk mencetak tulisan “hello world !” sebanyak 3 kali dengan bahasa Java, maka programmer A dapat menulis kode program dengan sintaks berikut Tabel 2.1. Program “hello world !” programmer A import javax.io; class mainProgram{ public static void main(String[] args){ System.out.println(“hello world !”); System.out.println(“hello world !”); System.out.println(“hello world !”); } }
Sedangkan programmer B menulisnya dengan sintaks berikut Tabel 2.2. Program “hello world !” pada programmer B import javax.io; class mainProgram{ public static void main(String[] args){ for(int i = 1; i <= 3; i++){ System.Out.print(“hello world !”); } } }
Jika dilihat dari struktur program, umumnya setiap bahasa pemrograman harus mendeklarasikan sebuah function atau method sebelum menuliskan berbagai macam operasi tertentu didalamnya. Perbedaanya hanya dari sisi penulisan. Dalam penelitian ini, pemeriksaan kesamaan sintaks lebih mengkhusus pada
5
pemeriksaan kode program. Sehingga tetap memperhitungkan kesamaan kode program untuk bahasa pemrograman yang sama. Pemeriksaan dilakukan dengan memperhatikan struktur dan konten pada kode program tersebut. 2.1.1 Elemen Dasar Bahasa Java Untuk memeriksa kesamaan kode program dalam bahasa Java, sistem harus mengetahui beberapa elemen dasar dari Java yaitu tata cara atau format penulisan kode program, kata kunci (keyword) pada Java, dan separator. Untuk tata cara atau format penulisan kode program, Rahardjo, dkk (2007) menjelaskan elemen yang dimaksud diantaranya seperti komentar, variabel, kontrol program, input/output, kelas dan objek, dsb. Berikut merupakan tabel yang menjelaskan format penulisan elemen-elemen pada program Java beserta penjelasannya
Tabel 2.3. Format penulisan elemen kode program pada java NO
FORMAT PENULISAN
PENJELASAN
1
//ini komentar
Komentar untuk satu baris.
2
/*ini komentar
Komentar
beberapa baris*/
3
/** *Program “HelloWorld” *@author Wisesa
untuk
beberapa
untuk
keperluan
baris. Komentar
dokumentasi suatu program.
*/
4
tipe namaVariabel;
Deklarasi satu variabel dengan tipe data tertentu.
5
tipe variabel1,variabel2;
Deklarasi beberapa variabel dengan tipe data yang sama.
6
tipe variabel = nilai;
Inisialisasi nilai pada sebuah variabel.
7
tipe variabel1 = nilai1, variabel2 = nilai2;
8
tipe variabel1 =(tipeTarget) nilai;
9
tipe[] namaArray;
Inisialisasi beberapa nilai pada beberapa variabel. Proses typecasting (konversi nilai ke tipe data yang berbeda). Deklarasi array satu dimensi.
6
10
variabelArray = new
Inisialisasi array satu dimensi.
tipe[jumlahElemen];
11
tipe[][] namaArray;
Deklarasi array dua dimensi.
12
variabelArray = new
Inisialisisasi array dua dimensi.
tipe[jumElemen][jumElemen]
13
if(kondisi){ ..
kontrol
if
untuk
pemilihan 1 kondisi.
}
14
Prosedur
if(kondisi){ .. }else{
Prosedur kontrol if-else untuk pemilihan 2 kondisi.
.. }
15
if(kondisi1){ .. }else if(kondisi2){
Prosedur kontrol if-elseif-else untuk pemilihan 3 atau lebih kondisi.
.. }else{ .. }
16
switch(ekspresi){ case nilai1: ..
Prosedur kontrol switch-case untuk pemilihan kondisi.
break; case nilai2: .. break; default: .. }
17
for(inisialisasi; kondisi; iterasi){ ..
Prosedur kontrol for untuk sebuah perulangan.
}
18
for(inisialisasi1, inisialisasi2; kondisi1; iterasi1, iterasi2){ ..
Prosedur kontrol for untuk sebuah
perulangan
dengan
beberapa inisialisasi dan iterasi.
}
19
inisialisasi; while(kondisi){ ..
Prosedur kontrol while untuk sebuah perulangan.
iterasi; }
7
20
inisialisasi; do{ ..
Prosedur
kontrol
do-while
untuk sebuah perulangan.
iterasi; }while(kondisi);
21
class NamaKelas{
Deklarasi sebuah kelas.
.. }
22
NamaKelas variabel = new NamaKelas();
Instansiasi
kelas
dan
memasukkan
referensi
ke
sebuah variabel. 23
tipe namaMethod(daftarparameter){ ..
Deklarasi sebuah method pada sebuah kelas.
}
24
tipe namaMethod(daftarparameter){ .. return nilai;
Deklarasi sebuah method pada sebuah kelas dengan suatu nilai balik.
}
25
namaKonstruktor(daftarparameter){ ..
Deklarasi
konstruktor
pada
sebuah kelas.
}
26
tingkat-akses tipe namaVariabel;
27
tingkat-akses tipe namaMethod(daftarparameter){
Deklarasi
variabel
dengan
tingkat akses. Deklarasi
method
dengan
tingkat akses dan parameter.
.. }
28
class nama-subclass extends nama-superclass{ ..
Melakukan proses penurunan terhadap suatu kelas.
}
29
try{ .. }catch(tipeEksepsi namaVariabel){
Deklarasi
try-catch
untuk
pencegahan eksepsi dengan 1 tipe eksepsi.
.. }
8
30
try{
Deklarasi
..
try-catch
untuk
eksepsi
dengan
pencegahan
}catch(tipeEksepsi1
beberapa tipe eksepsi.
namaVariabel1){ .. }catch(tipeEksepsi2 namaVariabel2){ .. }
Format penulisan kode program pada tabel 2.3 nantinya akan menjadi acuan pada sistem untuk memeriksa konten dari kode program ataupun mengenali struktur dari kode program. Selain format penulisan, sistem juga harus mengenali kata kunci (keyword) pada Java. Menurut Rahardjo, dkk (2007), kata kunci adalah kata-kata yang telah didefinisikan oleh compiler dan memiliki arti dan tujuan spesifik. Java melarang pembuatan sebuah pengenal (nama variabel, konstanta, kelas, maupun method) dengan menggunakan kata kunci. Tabel 2.4 berikut ini menunjukkan kata kunci yang terdapat di dalam Java. Tabel 2.4. Kata kunci pada Java abstract
double
int
strictfp
boolean
else
interface
super
break
extends
long
switch
byte
final
native
synchronized
case
finally
new
this
catch
float
package
throw
char
for
private
throws
class
goto
protected
transient
const
if
public
try
continue
implements
return
void
default
import
short
volatile
do
instanceof
static
while
Kata kunci dapat diklasifikasikan menjadi beberapa fungsi yaitu tipe data, percabangan, perulangan, tingkat akses, dsb. Beberapa kata kunci memiliki fungsi khusus seperti return, new,
final, static,
dsb. Karena
untuk memeriksa kesamaan kode program, tidak membutuhkan makna 9
dari kode, melainkan hanya membutuhkan tata cara penulisan kode program, maka makna penulisan kata kunci dapat diabaikan. Elemen dasar yang juga penting dari sebuah bahasa pemrograman, khususnya java adalah adanya separator. Separator digunakan untuk memisahkan salah satu bagian program dengan bagian lainnya. Salah satu contoh dari separator yang paling sering digunakan pada setiap kode program adalah semicolon (tanda titik koma (;)), yang digunakan untuk memisahkan statement yang satu dengan yang lainnya. Tabel 2.5 menunjukkan daftar separator di dalam Java. Tabel 2.5. Daftar separator di dalam Java SIMBOL
NAMA
KEGUNAAN
SEPARATOR ()
Parentheses (tanda
Digunakan
kurung)
daftar
untuk
parameter
mengisikan di
dalam
method; untuk mengapit sebuah ekspresi dalam operasi tertentu (misalnya: operasi aritmetika), mengapit
ekspresi
di
dalam
statement kontrol, dan untuk melakukan typecast. {}
Braces (kurung
Digunakan untuk membuat blok
kurawal)
program (kelas, method, kontrol pemilihan, pengulangan)
dan
kontrol
dan
untuk
mengisikan nilai inisial pada deklarasi array. []
Bracket (kurung
Digunakan
siku)
mendeklarasikan array dan untuk mengambil/mengisi
untuk
nilai
dari
elemen array. ;
Semicolon (titik
Digunakan untuk memisahkan
koma)
statemen.
10
Comma (koma)
,
Digunakan untuk memisahkan variabel
pada
saat
proses
deklarasi. Juga dapat digunakan pada saat menggunakan statemen for.
Period (titik)
.
Digunakan untuk memisahkan nama paket, subpaket, dan kelas. Juga
digunakan
memisahkan data/method
untuk dari
sebuah referensi objek.
2.2 Ekspresi Reguler Menurut Aho, dkk (1994), ekspresi reguler atau yang biasa dikenal dengan regex merupakan sebuah ekspresi yang menjadi notasi penjelasan mengenai suatu bahasa. Regex dapat mendefinisikan secara tepat bahasa yang sama dan berperan sebagai bahasa input untuk banyak sistem yang memproses untaian string, seperti perintah search pada UNIX yaitu grep atau perintah-perintah sejenis untuk menemukan untai yang dilihat seseorang pada web browser atau sistem pemformatan teks. Seperti yang dijelaskan oleh Aho, dkk (1994), terdapat tiga operator pada regex. Ketiga operasi tersebut adalah 1. Gabungan (union) dua bahasa L dan M (disimbolkan dengan L ∪ M), yaitu himpunan untaian string yang berada baik pada L atau M atau pada keduanya. Sebagai contoh, jika L = {001, 10, 111} dan M = {∈, 001}, maka L ∪ M = {∈, 10,001, 111} 2. Rentengan (concantenation) bahasa L dan M (disimbolkan dengan L.M) adalah himpunan untaian string yang dapat dibentuk dengan mengambil sembarang untai pada L dan merentengnya dengan sembarang untai pada M. Sebagai contoh, jika L = {001, 10, 111} dan M = {∈, 001}, maka L.M atau disingkat LM saja, adalah {001, 10, 111, 001001, 10001, 111001}. Tiga untai pertama pada LM adalah untai-untai pada L direnteng dengan ∈. Karena ∈ merupakan
11
identitas rentengan, untai yang dihasilkan sama dengan untai pada L. Akan tetapi, tiga untai yang terakhir pada LM dibentuk dengan mengambil setiap untai pada L dan merentengnya dengan untai dengan untai kedua pada M yaitu 001. Sebagai contoh, 10 dari L direnteng dengan 001 dari M akan menghasilkan 10001 pada LM. 3. Tutupan (closure) bahasa L dilambangkan dengan L* dan mewakili himpunan yang untaianya dapat dibentuk dengan mengambil sembarang nomor untai dari L, mungkin dengan pengulangan (untai yang sama mungkin dipilih lebih dari satu kali) dan merenteng semuanya. Contohnya, jika L = {0, 1}, maka L* adalah seluruh untai angka-angka yang terdiri dari 0 dan 1 sedemikian hingga angkaangka selalu berpasangan (misalnya 011, 11110) dan ∈, tetapi tidak pernah 01011 atau 101. Lebih formal lagi, L* adalah gabungan tak berhingga ⋃𝑖≥0 𝐿𝑖 , dimana L0 = {∈}, L1 = L dan Li dengan i > 1 adalah LL…L (rentengan salinan L sebanyak i). Pada sistem operasi UNIX, terdapat aturan baku yang disebut standar IEEE POSIX Basic Regular Expression atau BRE, seperti yang dijelaskan oleh Ken (1968). Pada sintaks BRE, hampir semua karakter diberlakukan secara harfiah. Tabel 2.7 dibawah merupakan daftar Metacharacter dan deskripsinya.
Tabel 2.6. Daftar Metacharacter Metacharacter .
Deskripsi Sesuai dengan satu karakter apa saja. Dalam kurung siku, karakter titik sesuai dengan titik secara harfiah. Misal, a.c cocok pada “abc”,dll. Tapi [a.c] hanya cocok pada “a”, “.”, atau “c”.
[]
Ekspresi kurung siku. Sesuai dengan satu karakter yang ada dalam kurung. Misal, [abc] sesuai “a”, “b”, “c”. [a-z] menspesifikasikan sebuah range yang sesuai dengan huruf kecil dari “a” sampai “z”. Format ini dapat dicampur,
12
misalkan [abcx-z] sesuai dengan “a”, “b”, “c”, “x”, “y”, “z”. Karakter diberlakukan secara harfiah jika berada diawal atau diakhir tanda kurung siku, atau jika diawali dengan karakter escape seperti: [abc-], [-abc], atau [a\-bc]. [^]
Sesuai dengan satu karakter apa saja yang tidak ada dalam kurung.
^
Sesuai dengan awal string. Pada toolline-based, notasi ini sesuai dengan awal baris di mana saja.
$
Sesuai dengan akhir string. Pada toolline-based, notasi ini sesuai dengan akhir baris di mana saja.
BRE: \ (\) ERE: () \n
Mendefinisikan
subexpression
yang
dapat
dipanggil kemudian. Sesuai dengan subexpression ke-n dimana n bernilai 1 sampai 9.
*
Sesuai dengan elemen sebelumnya sebanyak 0 atau beberapa kali.
BRE: \{m,n\} ERE: {m,n} ERE :?
Sesuai dengan elemen sebelumnya minimal sebanyak m kali namun tidak lebih dari n kali. Sesuai dengan elemen sebelumnya sebanyak 0 atau 1 kali.
ERE: +
Sesuai dengan elemen sebelumnya minimal sebanyak 1 kali.
ERE: |
Operator alternasi yang sesuai dengan expression sebelumnya atau sesudahnya.
13
2.3 Abstract Syntax Tree (AST) Fei (2006) menyatakan, dalam ilmu komputer, Abstract Syntax Tree (AST) merupakan pohon yang merepresentasikan struktur abstrak sintaks dari source code yang ditulis dalam suatu bahasa pemrograman komputer. Setiap node dikonstruksi berdasarkan parameter penting yang ada pada source code. Pada AST, sebuah informasi bisa ditambahkan dalam konteks menjelaskan data dari node yang dibuat. Misalnya untuk keperluan penjelasan informasi dalam pemrosesan variabel. Misalnya diberikan sebuah source code dari program Java seperti pada tabel 2.6 berikut Tabel 2.7. Contoh source code pada Java int i=0; int j=4; for (; i<10; i++){ if (i<j) j=i*j; } return j;
Maka AST yang dihasilkan dari source code diatas ditunjukkan oleh gambar 2.1 berikut
Gambar 2.1. Model AST untuk source code pada tabel 2.6 14
Namun isi dari setiap node pada AST dapat disesuaikan dengan konteks permasalahan atau dalam konteks ini sesuai hasi ekstraksi dari data input kode program. Jika data yang diekstraksi berupa konten dari program, maka node dari AST akan diisi oleh konten tersebut.
2.4 Struktur Data B-Tree Menurut Cormen, dkk (2001), B-Tree adalah sebuah m-ary balanced search tree khusus yang digunakan dalam basis data karena strukturnya memungkinkan data yang disimpan untuk disisipi, dihapus, dan diambil dengan jaminan proses dengan waktu terburuk adalah O(log n), dimana setiap simpulnya terdiri dari (m/2) sampai m buah simpul anak, di mana m > 1 merupakan bilangan bulat . m adalah orde. Akar pohon B-tree paling sedikit memiliki 2 simpul anak. B-tree adalah struktur yang baik jika pohon digunakan pada memori yang lambat, karena ketinggian dan jumlah akses dapat diperkecil dengan mengambil bilangan m yang besar. Berikut merupakan contoh dari B-Tree dengan nilai orde sama dengan 5.
Gambar 2.2. Contoh struktur b-tree dengan nilai orde 5.
Didalam B-Tree, terdapat sejumlah operasi dasar yang sering digunakan, beberapa diantaranya akan diterapkan untuk membuat dan mengakses struktur b-tree dari kode program. Operasi dasar tersebut adalah
Searching. Sama halnya dengan Binary Search Tree (BST), jalan yang dipakai dalam proses pencarian adalah dengan cara Breath First Search (BFS) atau Depth First Search (DFS). BFS melakukan pencarian dengan
15
mengembangkan pohon pencarian secara horizontal sedangkan DFS secara vertikal.
Inserting. Proses penyisipan dilakukan untuk menambahkan sebuah data pada B-Tree tanpa harus menghapus node yang berada diataranya.
2.5 Probabilitas Naïve Bayes Probabilitas Bayesian adalah suatu interpretasi dari kalkulus yang memuat konsep probabilitas sebagai derajat dimana suatu pernyataan dipercaya benar. Teori Bayesian juga dapat digunakan sebagai alat pengambilan keputusan untuk memperbaharui tingkat kepercayaan dari suatu informasi. Umumnya, Naïve Bayes memiliki kelebihan mudah untuk dipahami, hanya memerlukan pengkodean yang sederhana, serta lebih cepat dalam perhitungan. Sedangkan kekurangan dari teori probabilitas bayesian yang banyak dikritisi oleh para ilmuwan adalah karena pada teori ini, satu probabilitas saja tidak bisa mengukur seberapa dalam tingkat keakuratannya. Dengan kata lain, kurang bukti untuk membuktikan kebenaran jawaban yang dihasilkan dari teori ini. Teorema Bayes menerangkan hubungan antara probabilitas terjadinya peristiwa A dengan syarat peristiwa B telah terjadi dan probabilitas terjadinya peristiwa B dengan syarat peristiwa A telah terjadi.
𝑃(𝐴|𝐵) =
𝑃(𝐴 ∩ 𝐵) 𝑃(𝐵)
(1)
Keterangan: 𝑃(𝐴|𝐵) = peluang A dengan syarat B 𝑃(𝐴 ∩ 𝐵) = peluang A irisan B 𝑃(𝐵) = peluang B. Untuk kejadian saling bebas, 𝑃(𝐴 ∩ 𝐵) = 𝑃(𝐴). 𝑃(𝐵). Probabilitas total untuk peluang bersyarat, dapat diturunkan dari pers(1). Misalkan A1, A2, …, AN adalah peristiwa saling bebas yang gabungannya sama dengan ruang sampel S. Himpunan ini akan dinamakan partisi dari S. Maka semua peristiwa dalam S dapat dinyatakan sebagai berikut
16
𝐵 = 𝐵 ∩ 𝑆 = 𝐵 ∩ (𝐴1 ∪ 𝐴2 ∪ … ∪ 𝐴𝑁 ) = (𝐵 ∩ 𝐴1 ) ∪ (𝐵 ∩ 𝐴2 ) ∪ (𝐵 ∩ 𝐴3 ) ∪ … ∪ (𝐵 ∩ 𝐴𝑁 )
(2)
Karena A1, A2, …, AN saling bebas maka 𝑃(𝐵) = 𝑃(𝐵 ∩ 𝐴1 ) + 𝑃(𝐵 ∩ 𝐴2 ) + ⋯ + 𝑃(𝐵 ∩ 𝐴𝑁 )
(3)
Dari pers(1), jika posisi A dan B ditukar, maka dapat dirubah menjadi 𝑃(𝐵 ∩ 𝐴) = 𝑃(𝐵|𝐴)𝑃(𝐴)
(4)
Sehingga pers(4) dapat disubstitusi ke pers(3) menjadi 𝑃(𝐵) = 𝑃(𝐵|𝐴1 )𝑃(𝐴1 ) + 𝑃(𝐵|𝐴2 )𝑃(𝐴2 ) + ⋯ + 𝑃(𝐵|𝐴𝑁 )𝑃(𝐴𝑁 )
(5)
Jadi didapatkan probabilitas kejadian marginal dari B adalah 𝑁
𝑃(𝐵) = ∑ 𝑃(𝐵|𝐴𝑘 )𝑃(𝐴𝑘 )
(6)
𝑘=1
Untuk peluang bersyarat, diperoleh peluang total yaitu
𝑃(𝐵|𝐴𝑖 ) =
𝑃(𝐵 ∩ 𝐴𝑖 ) 𝑃(𝐵 ∩ 𝐴𝑖 ) = 𝑁 ∑𝑘=1 𝑃(𝐴|𝐵𝑘 )𝑃(𝐵𝑘 ) 𝑃(𝐴)
(7)
Keterangan: 𝑃(𝐵|𝐴𝑖 ) = peluang kejadian bebas B dengan syarat kejadian Ai 𝑃(𝐴)
= peluang kejadian marginal dari A
2.6 Tree Pattern Matching (TPM) Tree Pattern Matching (TPM) merupakan sebuah metode yang digunakan untuk melakukan pencocokan sebuah pattern P terhadap suatu pohon T atau hutan F. Fei (2006) menjelaskan, pencocokan dilakukan dengan melihat
17
kesamaan terhadap node yang ada didalamnya. Proses pencocokan juga disebut sebagai mapping, karena proses ini akan melihat kesesuaian data antar pattern dan pohon atau hutan. P akan dikatakan match dengan T atau F jika T atau F juga mengandung data pada P dengan kesesuaian yang sama. Berikut merupakan contoh dari proses mapping menggunakan TPM dengan pola P dan pohon T.
Gambar 2.3. Sebuah proses mapping dengan TPM
18
