DAFTAR REFERENSI [AIK94] A. Aiken. Measure of Software Similarity.
Tanggal akses : 20 September 2006 [ARW06] Arwin, Christian, S.M.M. Tahaghoghi (2006). Plagiarism Detection Across Programming Languages. School of Computer Science and Information Technology, RMIT University, Melbourne, Australia. [CHE03] Xin Chen, Brent Francia, Ming Li, Brian Mckinnon, Amit Seker (2003). Shared Information and Program Plagiarism Detection. University of California, Santa Barbara. [CLO00] Clough, P.D. (2000). Plagiarism in Natural and Programming Languages: An Overview of Current Tools and Technologies. Department of Computer Science, University of Sheffield, UK, Technical Report CS-00-05. [CLO03] Clough, P.D. (2003). Old and new challenges in automatic plagiarism detection. Department of Computer Science, University of Sheffield, UK. [COR01] Cormen, Leiserson, and Rivert (2001). Introduction to Algorithms. [FAI87] J. A. Faidhi, S. K. Robinson (1987). An empirical approach for detecting program similarity and plagiarism within a university programming environment. Computing in Education, Vol. 11, pp(11-19). [FIN95] Raphael A. Finkel (1995). Advanced Programming Language and Design. Menlo Park : Addison Wesley. [GRU98] Dick Grune, Ceriel JH. Jacobs (1998). Parsing Techniques : A Practical Guide. Vrije Universiteit Amsterdam. [HAL77] Halstead, M. H. (1977). Elements of software science. North Holland, New York. [HAN01] Hannabuss, S. (2001). Contested texts: issues of plagiarism. Library Management, MCB University Press, Vol. 22(6-7), 311-318. [HUL98] Hull, Stephen (1998). Business Object Glossary.
xi
Tanggal akses : 30 September 2006. [JOY99] Joy, M. & Luck, M. (1999). Plagiarism in Programming Assignments. IEEE Transactions of Education, Vol. 42(2), 129-133. [KAR87] Karp, Richard M., Michael O. Rabin (1987). Efficient Randomized PatternMatching Algorithms. IBM Journal of Research and Development 31(2), p 249-260. [KER98] Kernighan, Brian W., Dennis M. Ritchie (1998). The ANSI C Programming Language. 2nd ed. O’Reilly. [LUT00] Lutz Prechelt, Guido Malpohl, Michael Phlippsen (2000). JPlag: Finding plagiarisms among a set of programs. Fakultät für Informatik Technical Report 2000-1, Universität Kalrsruhe, Karlsruhe, Germany. [MIL05] Miller, George A. (2005). A lexical database for the English language. Tanggal akses : 7 Oktober 2006 [NEI02] www.neiu.edu (2002). Learning Management System (LMS). Tanggal Akses : 16 Februari 2007 [PAR89] Parker, Alan & Hamblen, James (1989). Computer algorithms for Plagiarism Detection. IEEE Transactions on Education, Vol. 32, Number 2. [PPA06] Peraturan Akademik Institut Teknologi Bandung (2006). Lampiran SK Rektor No. 153/SK/K01/PP/2006. [PUR00] Purwanti, Sri (2000). Diktat Kuliah IF221 Dasar Pemrograman, Pemrograman Fungsional, Bagian II:LISP. Jurusan Teknik Informatika, Fakultas Teknologi Industri, Institut Teknologi Bandung. [SAM94] Samuelson, P. (1994). Self-Plagiarism or Fair Use?. Communications of the ACM, Vol. 37(8), 21-25. [SIL02] Silberschatz, Korth & Sudarshan (2002). Database System Concepts. 4th ed. McGraw-Hill. [TEC06] techterms.org (2006). Token.
xii
Tanggal Akses : 20 September 2006 [VLS00] Bebas.vLSM.org (2000). Definisi Statistika. Tanggal akses : 30 September 2006. [WAG00] Wagner, Neal R. (2000). Plagiarism by Student Programmers. The University of Texas at San Antonio, Division Computer Science, San Antonio, TX 78249, USA. [WIR72] Wirth, Niclaus. (1972). The Programming Language Pascal (Revised Report). [WIS92] Wise, Michael J. (1992). Detection of Similarities in Student Programs: YAP'ing may be Preferable to Plague'ing. ACM SIGSCE Bulletin(proc. of 23rd SIGCSE Technical Symp.), 24(1), pp. 268-271. [WIS93a] Wise, Michael J. (1993). Neweyes: A System for Comparing Biological Sequences Using the Running Karp-Rabin Greedy String-Tiling Algorithm. Department of Computer Science, University of Sydney, Australia, Technical Report 463. [WIS93b] Wise, Michael J. (1993). String Similarity via Greedy String Tiling and Running Karp-Rabin Matching. Department of Computer Science, University of Sydney, Australia. [WIS96] Wise, Michael J. (1996). YAP3: Improved Detection of Similarities in Computer Programs and Other Texts. SIGCSE’96, 130-134
xiii
DAFTAR PUSTAKA [BEN02] Bennet, Simon. (2002). Object-Oriented Systems Analysis And Design Using UML 2nd Edition. McGraw Hill. [CUN93] Cunningham, Pádraig & Mikoyan, Alexander N. (1993). Using CBR Techniques to Detect Plagiarism in Computing Assignments. Tanggal akses : 19 September 2006 [EVE06] Eve Andersson, Philip Greenspun, Andrew Grumet (2006). Software Engineering for Internet Applications. The MIT Press. [HEX05] Hexham, Irving (2005). Academic Plagiarism Defined. Department of Religious Studies, University of Calgary. [UCH06] Department of Computer Science, University of Chicago. Lecture 4. Process and Method:. An Introduction to the. Rational Unified Process. Tanggal akses : 30 September 2006. [VER06] Verco, Kristina L., Michael J. Wise (2006). Comparing Structure and Attribute-Counting Systems. Department of Computer Science, University of Sydney, Australia. [YOU04] Kim, Young-Chul, Cho, Yong-Yoon & Moon, Jong-Bae (2004). A Plagiarism Detection System Using a Syntax-Tree. Transactions on Engineering, Computing and Technology V1.
xiv
LAMPIRAN A CONTOH PENERAPAN ALGORITMA GREEDY STRING TILING Berikut ini diberikan contoh penerapan algoritma Greedy String Tiling dalam membandingkan dua buah token string untuk mencari substring-substring yang sama. Namun karena langkah-langkah pada eksekusi algoritma GST ini sangat banyak, tidak semuanya akan diuraikan di lampiran ini, melainkan hanya kasus-kasus yang cukup penting untuk dapat menjelaskan cara kerja algoritma GST saja yang akan diuraikan. Contoh isi kedua token string yang dibandingkan yaitu sebagai berikut: P: PRG BGP VAR WR RD ASG ASG BGW ASG WR RD ASG EDW EDP T: BGP VAR VAR ASG BGW ASG WR RD ASG EDW BGW ASG EDW WR EDP
Notasi yang dipakai pada uraian penerapan algoritma GST dijelaskan sebagai berikut: : token string.
a.
P,T
b.
p
: posisi indeks pada token string P
c.
t
: posisi indeks pada token string T.
d.
maxmatch
e.
match(p,t,s)
: panjang minimum pasangan substring sama yang dicari. : menyimpan pasangan substring yang sama dimulai dari posisi pada token string
P
dan posisi
t
pada token string
T
p
dengan
panjang substring s. f.
Tanda ^ di bawah suatu token menyatakan bahwa token tersebut sedang ditunjuk pada iterasi tersebut. Sedangkan token yang dicetak miring dan diberi garis bawah mempunyai arti bahwa token tersebut sudah ditandai.
Pada contoh ini, input parameter minimum-match-length bernilai 3. Dengan begitu, pasangan substring sama yang mempunyai panjang lebih kecil dari 3 akan diabaikan. Jika 1 dipilih sebagai minimum-match-length, setiap pasangan token yang sama akan dianggap sebagai hasil plagiarisme. Hal itu tentunya berakibat pada hasil deteksi yang kurang akurat karena pada umumnya satu statement yang serupa sering ditemui pada source code hasil pengumpulan kelas pemrograman. Kasus tersebut bukanlah plagiarisme melainkan kesamaan yang tidak disengaja. Jika minimum-match-length dipilih bernilai lebih besar dari 3, akurasi hasil deteksi juga tidak akan optimal karena akan ada banyak pasangan substring sama yang diabaikan yang sebenarnya
1
A-2 merupakan hasil tindak plagiarisme. Oleh sebab itu pada eksekusi ini untuk kumpulan token string yang panjangnya sekitar belasan token dipilih 3 sebagai nilai minimummatch-length. Pada awal eksekusi, maxmatch diinisialisasi agar bernilai sama dengan minimummatch-length. Kemudian setiap token pada P dengan setiap token pada T dibandingkan. Berikut ini dijelaskan kasus-kasus yang terjadi ketika eksekusi pembandingan token string P dan T. 1.
Jika token yang sedang ditunjuk pada P tidak sama dengan token pada T maka pembandingan dilanjutkan untuk token pada posisi berikutnya di T berikutnya.
P p=0 T t=0 t=1 t=2 .. t=14
2.
0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
VAR
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
^ BGP
^ ^ ^ ^
Jika ditemukan token yang sama pada
P
dan T, maka bandingkan token-token di
posisi berikutnya sampai salah satu dari 3 kondisi berhenti berikut ditemui: a. jika token yang tidak sama ditemui. b. jika end of list dicapai. c. jika ditemukan token yang sudah ditandai.
P p=1 T t=0
P p=1 T t=0
P p=1 T t=0
0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
BGP
VAR
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
^ ^ 0 PRG
1
^
BGP
VAR
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
1
^
0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
1
2
^
BGP
VAR
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
1
2
^
A-3 3.
Setelah salah satu dari kondisi berhenti ditemui, cek apakah panjang substring sama yang baru ditemukan lebih besar atau sama dengan nilai maxmatch. Pada kasus ini panjang substring tersebut hanya 2 token, sementara maxmatch bernilai 3 (pada awal eksekusi diinisialisasi senilai minimum-match-length). Oleh karena itu pasangan substring ini akan diabaikan. Kemudian pembandingan per token dilanjutkan lagi.
P p=1 T t=1 t=2 .. t=15
4.
0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
VAR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
^ BGP
VAR
^ ^ ^
Pada kasus di bawah ini, ditemukan pasangan token yang sama yaitu token “wr”. Kemudian token-token pada posisi berikutnya dibandingkan sampai salah satu kondisi berhenti dicapai, yaitu ditemukan pasangan token yang tidak sama.
P p=3 T t=6
P p=3 T t=6
P p=3 T t=6
P p=3 T t=6
0 PRG
1 BGP
2 VAR
3 WR
BGP
VAR
VAR
ASG
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
^ ^ 0 PRG BGP
0 PRG BGP
0 PRG BGP
1 BGP VAR
1 BGP VAR
1 BGP VAR
2 VAR VAR
2 VAR VAR
2 VAR VAR
3 WR
4 RD
1
^
ASG
BGW
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
1
^
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
1
2
^
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
BGW
ASG
EDW
WR
EDP
3 WR
4 RD
5 ASG
1
2
^
ASG
BGW
ASG
3 WR
4 RD
5 ASG
1
2
3
^
ASG
BGW
ASG
WR
RD
ASG
EDW
1
2
3
^
Pada kasus ini, panjang substring sama dengan nilai maxmatch, yaitu 3. Karena itu dibentuk pasangan substring match(p,t,s) dengan s merupakan panjang substring tersebut. Pasangan substring dinyatakan sebagai match(3,6,3), yang kemudian disimpan dalam list of maximal-match.
A-4 5.
Pada kasus ini, ditemukan token lain yang sama pada posisi
p=7
dan t=4. Setelah
token-token pada posisi berikutnya dibandingkan ternyata ada 7 token pada substring tersebut. Jumlah token pada substring yang baru ditemukan lebih besar dari nilai maxmatch, sehingga nilai maxmatch di-assign menjadi 7. Pasangan substring dinyatakan sebagai
match(7,4,7)
dan dimasukkan ke dalam list of
maximal-match.
P p=7 T t=4
6.
0 PRG BGP
1 BGP VAR
2 VAR VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
1
2
3
4
5
6
7
^
ASG
EDW
WR
ASG
BGW
ASG
WR
RD
ASG
EDW
BGW
1
2
3
4
5
6
7
^
Pada fase markstrings, setiap
match(p,t,s)
apakah seluruh token pada
dan
P
T
14
EDP
pada list of maximal-match dicek
yang merupakan elemen maximal-match match(p,t,s)
tersebut sudah ditandai atau belum. Hanya
yang mempunyai
panjang sama dengan maxmatch yang diperiksa. Pada contoh ini, berarti hanya match(7,4,7) T
yang diperiksa. Setelah diketahui bahwa seluruh token pada
P
dan
yang merupakan elemen match(7,4,7) belum ditandai, maka tile bisa dibentuk.
Caranya adalah dengan menandai seluruh token-token tersebut.
P T
7.
0 PRG BGP
1 BGP VAR
2 VAR VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
1
2
3
4
5
6
7
BGW
ASG
EDW
ASG
BGW
ASG
WR
RD
ASG
EDW
1
2
3
4
5
6
7
13 EDP
14
WR
EDP
Setelah fase markstrings selesai, karena nilai maxmatch tidak sama dengan nilai minimum-match-length, maka pembandingan dimulai lagi dari awal fase scanpattern. Maxmatch diinisialisasi lagi menjadi sama dengan nilai minimummatch-length. Kemudian setiap token pada
P
dengan setiap token pada
T
dibandingkan lagi dari token pertama. Seperti pada pembandingan di kasus 4, ditemukan token yang sama pada p=3 dan t=6.
Namun kali ini karena token pada
T
sudah ditandai, maximal-match tidak
dibuat.
P p=3 T t=6
0 PRG
1 BGP
2 VAR
3 WR
4 RD
5 ASG
6 ASG
7 BGW
8 ASG
9 WR
10 RD
11 ASG
12 EDW
13 EDP
14
BGW
ASG
WR
RD
ASG
EDW
BGW
ASG
EDW
WR
EDP
^ BGP
VAR
VAR
ASG
^
A-5 8.
Setelah token terakhir pada P dan token terakhir pada T selesai dibandingkan, ternyata tidak ada maximal-match yang bisa dibentuk dari token-token yang belum ditandai. Karena tidak ada maximal-match, maka pada fase scanpattern tidak ada pengecekan yang dilakukan. Pada akhir fase scanpattern diketahui bahwa nilai maxmatch sama dengan minimum-match-length, sehingga eksekusi algoritma GST pun selesai.
LAMPIRAN B SKENARIO USE CASE B.1
Skenario Use Case Mendeteksi Plagiarisme
Nomor Use Case
UC-M-01.
Aktor
Pengajar.
Prekondisi
Form memulai deteksi sedang ditampilkan. Skenario Normal
Aksi Aktor
Respon Aplikasi Web
Respon Aplikasi Backend
1. Memilih nama direktori dan bahasa pemrograman source code target deteksi, memasukkan nilai sensitivitas dan alamat email notifikasi lalu menekan tombol “Eksekusi deteksi”. 2. Memeriksa kelengkapan dan validitas nilai-nilai yang dimasukkan. 3. Menyimpan nama direktori, bahasa pemrograman source code target deteksi, nilai sensitivitas, alamat email notifikasi, tanggal saat ini, dan waktu saat ini ke basis data. 4. Mengirimkan pesan ke aplikasi backend agar melakukan deteksi. 5. Mengambil informasi deteksi yang sudah tersimpan dalam basis data Deimos. 6. Membaca setiap source code yang terdapat di direktori masukan. Untuk setiap source code, dilakukan scanning dan parsing. Setiap kali proses parsing selesai dilakukan, jika tidak ada kesalahan sintaks
1
B-2 Aksi Aktor
Respon Aplikasi Web
Respon Aplikasi Backend maka nama setiap subdirektori program beserta token string yang dihasilkan disimpan ke basis data. 7. Memasangkan setiap program satu sama lain. Untuk setiap pasangan program, token string diambil dari basis data untuk dibandingkan, kemudian posisi bagian-bagian yang dianggap sama serta nilai similaritas pasangan program disimpan ke basis data. 8. Mengambil informasi alamat email yang tersimpan di basis data. 9. Mengirimkan email yang berisi notifikasi bahwa deteksi selesai.
10. Menampilkan pesan bahwa deteksi sudah selesai. Deteksi plagiarisme selesai. Hasil deteksi tersimpan di penyimpanan data
Kondisi Akhir
persisten Skenario Alternatif : Terjadi timeout atau kerusakan jaringan Aksi Aktor
Respon Aplikasi Web
1. Memilih nama direktori dan bahasa pemrograman source code target deteksi, memasukkan nilai sensitivitas dan alamat email notifikasi lalu menekan tombol “Eksekusi deteksi”. 2. Memeriksa kelengkapan nilai yang dimasukkan. 3. Memeriksa validitas nilai-nilai yang dimasukkan. 4. Menyimpan nama direktori, bahasa pemrograman source code target deteksi, nilai sensitivitas,
Respon Aplikasi Backend
B-3 Aksi Aktor
Respon Aplikasi Web
Respon Aplikasi Backend
alamat email notifikasi, tanggal saat ini, dan waktu saat ini ke basis data. 5. Mengirimkan pesan ke aplikasi backend agar melakukan deteksi. 6. Deteksi plagiarisme sesuai skenario normal. 7. Timeout. Kondisi Akhir
Walaupun terjadi timeout atau kerusakan jaringan, proses deteksi tetap tereksekusi di aplikasi backend.
B.2 Skenario Use Case Melihat Hasil Deteksi Pada Subbab ini diberikan skenario use case untuk use case melihat hasil deteksi. Terdapat dua jenis halaman untuk menampilkan hasil deteksi, yaitu halaman utama dan halaman perbandingan pasangan source code. Skenario use case untuk melihat masing-masing tampilan dapat dilihat pada Subbab B.2.1 dan Subbab B.2.2. B.2.1 Sub Skenario Use Case Melihat Halaman Utama Hasil Deteksi Nomor Use Case
UC-M-05.
Aktor
Pengajar.
Prekondisi
- Hasil deteksi sudah tersimpan di basis data. Skenario Normal Aksi Aktor
Respon Aplikasi Web
1. Menekan tombol “Lihat hasil deteksi”. 2. Mengambil informasi hasil deteksi dari basis data. 3. Menampilkan hasil deteksi pada halaman hasil deteksi utama. Kondisi Akhir
Ikhtisar hasil deteksi, tabel distribusi similaritas, dan matriks similaritas ditampilkan pada halaman hasil deteksi utama. Skenario Alternatif : Deteksi belum selesai Aksi Aktor
Respon Aplikasi Web
1. Menekan tombol “Lihat hasil deteksi”. 2. Mengambil informasi hasil deteksi dari basis data. 3. Menampilkan pesan bahwa deteksi belum selesai pada halaman hasil deteksi utama. Kondisi Akhir
Pesan bahwa deteksi belum selesai ditampilkan pada halaman hasil deteksi utama.
B-4 B.2.2 Sub Skenario Use Case Melihat Bagian-bagian Dugaan Praktek Plagiarisme pada Pasangan Source Code Nomor Use Case
UC-M-05.
Aktor
Pengajar.
Prekondisi
- Hasil deteksi sudah tersimpan di basis data. - Martriks similaritas pada halaman utama hasil deteksi sedang ditampilkan. Skenario Normal Aksi Aktor
Respon Sistem
1. Memilih pasangan source code yang ingin dilihat hasil deteksinya. 2. Mengambil informasi posisi bagian-bagian source code yang merupakan dugaan hasil praktek plagiarisme dari basis data. 3. Menampilkan pasangan source code disertai penanda warna pada bagian-bagian yang diduga merupakan dugaan hasil praktek plagiarisme. Pasangan source code disertai penanda warna pada bagian-bagian yang diduga
Kondisi Akhir
merupakan dugaan hasil praktek plagiarisme ditampilkan. Skenario Alternatif : Tidak ada source code pada direktori repository Aksi Aktor
Respon Sistem
1. Memilih pasangan source code yang ingin dilihat hasil deteksinya. 2. Menampilkan pesan bahwa source code tidak terdapat pada direktori. Kondisi Akhir
Pesan bahwa source code tidak terdapat pada direktori ditampilkan.
B-5
B.3 Skenario Use Case Menghapus Hasil Deteksi Nomor Use Case
UC-M-06.
Aktor
Pengajar.
Prekondisi
- Hasil deteksi sudah tersimpan di basis data. - Halaman menghapus hasil deteksi sedang ditampilkan. Skenario Normal Aksi Aktor
Respon Sistem
1. Memilih nama direktori yang hasil deteksinya ingin dihapus kemudian menekan tombol “Hapus hasil deteksi”. 2. Menghapus seluruh hasil deteksi pada basis data sesuai direktori yang dipilih aktor. Kondisi Akhir
Hasil deteksi pada basis data terhapus.
LAMPIRAN C PERANCANGAN SCANNER DAN PARSER Subsistem tokenizer merupakan satu-satunya subsistem yang bergantung pada bahasa pemrograman pada source code yang menjadi target deteksi plagiarisme. Tokenizer mempunyai tanggung jawab utama untuk mengubah source code program menjadi representasi linier berupa token string. Untuk itu, perlu dilakukan analisis statik terhadap source code. Kompilasi merupakan salah satu bentuk dari analisis statik, yang pada umumnya dibagi menjadi dua tahap: front-end (tahapan depan) yang bertugas menerjemahkan kode masukan ke dalam suatu bentuk antara dan back-end (tahapan belakang) yang bertugas memetakan fungsionalitas dari program kepada mesin target. Proses frontend sendiri, pada dasarnya terdiri dari dua proses utama, yaitu analisis leksikal dan analisis sintaks. Baik analisis leksikal maupun analisis sintaks mencakup translasi dari kode program ke dalam representasi antara (Intermediary Representation – IR). Analisis leksikal mengubah kode program menjadi serangkaian potongan teks tunggal dengan arti tertentu, sementara analisis sintaks menyusun token-token ke dalam sebuah pohon sintaks abstrak (abstract syntax tree). Bagian yang bertugas melakukan analisis leksikal sering disebut lexer atau scanner, sementara bagian yang bertugas melakukan analisis sintaks disebut parser. Sesuai dengan penjelasan di atas, untuk melakukan analisis statik diimplementasikan komponen scanner dan parser untuk bahasa pemrograman LISP dan Pascal.
C.1
Scanner
Scanner merupakan bagian yang bertugas untuk melakukan analisis leksikal. Analisis leksikal padalah proses pengubahan kode program ke dalam serangkaian simbol yang valid menurut grammar (tata bahasa) yang bersangkutan. Contoh simbol-simbol yang umum yaitu kata kunci/keyword, tanda baca, atau identifier (nama variabel, konstanta, fungsi dan prosedur). Untuk keperluan deteksi plagiarisme, pada tahap analisis leksikal ini semua whitespace dan informasi nama identifier diabaikan, sehingga tidak akan menjadi bagian dari rangkaian simbol yang dihasilkan. Hal tersebut dilakukan karena whitespace dan nama identifier merupakan bagian source code yang mudah 1
C-2 dijadikan target modifikasi oleh plagiat agar tindak plagiarisme yang telah dilakukannya tidak dapat dikenali oleh pengajar. Scanner pada umumnya bekerja menggunakan prinsip otomata nondeterministik. Pola leksikal dari simbol umumnya didefinisikan menggunakan regular expression (regex), karena format regex dapat menggambarkan pola leksikal secara kompak. Berikut ini adalah contoh pola regex untuk mengenali identifier (identifier didefinisikan sebagai string yang diawali oleh alfabet dan diikuti oleh sembarang alfabet atau angka) : alfabet Æ a|b|c|d|e|f|g|h|i|jk|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z angka Æ 0|1|2|3|4|5|6|7|8|9 identifier Æ alfabet {alfabet | angka} Pada detektor plagiarisme Deimos yang dibangun pada Tugas Akhir ini diimplementasikan scanner untuk bahasa pemrograman Pascal dan scanner untuk bahasa pemrograman LISP, yang masing-masing akan diuraikan pada Subbab C.1.1 dan C.1.2. C.1.1 Scanner untuk Bahasa Pemrograman Pascal Berikut ini merupakan rangkaian karakter yang valid pada bahasa pemrograman Pascal disertai pola regex yang mendefinisikannya :
any_char Æ karakter apapun digit Æ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 acceptable_char Æ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | U | T | U | V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | u | t | u | v | w | x | y | z | _ comment Æ ( * {any_char} * ) | { {anyChar} } scale_number Æ E + digit {digit} | E - digit {digit} Comment akan langsung diabaikan sehingga tidak menjadi bagian dari rangkaian
simbol yang dihasilkan. Simbol-simbol yang akan dimasukkan ke rangkaian simbol output yaitu identifier, unsigned_integer, unsigned_real, charcon dan stringcon. Berikut ini adalah pola regex untuk simbol-simbol tersebut:
C-3 identifier Æ acceptable_char {acceptable_char | digit} unsigned_integer Æ digit {digit} unsigned_real Æ digit {digit} . digit {digit} | digit {digit} scale_number | digit {digit} . digit {digit} scale_number charcon Æ ‘ any_char ‘ stringcon Æ ‘ any_char {any_char} ‘ Berikut ini merupakan daftar keyword bahasa pemrograman Pascal yang tetap dipertahankan informasinya dan menjadi bagian dari rangkaian simbol yang dihasilkan oleh scanner Pascal pada detektor plagiarisme Deimos: keyword Æ ( | ) | : | := | < | <= | <> | > | >= | * | + | - | , | . | / | ; | = | [ | ] | ^ | const | type | var | function | procedure | array | record | program | begin | end | if | case | repeat | while | for | else | until | of | do | to | downto | then | integer | real | char | div | mod | not | and | or | Boolean
| true | with | goto | set | file | label | packed | in | false | nil | read | readln | write | writeln | longint
C.1.2 Scanner untuk Bahasa Pemrograman LISP Berikut ini merupakan rangkaian karakter yang valid pada bahasa pemrograman LISP disertai pola regex yang mendefinisikannya: any_char Æ karakter apapun digit Æ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 acceptable_char Æ A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | U | T | U | V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r
| u | t | u | v | w | x | y | z | _ | : | { | } | ! | # | $ | % | & | * | + | - | . | / | < | > | = | ? | @ | [ | ]
| \ | ^ | ~ comment Æ ; {any_char} scale_number Æ E + digit {digit} | E - digit {digit} closed_stringcon Æ “ any_char {any_char} “ | | any_char {any_char} |
C-4 Komentar akan langsung diabaikan sehingga tidak menjadi bagian dari rangkaian
simbol yang dihasilkan. Simbol-simbol yang akan dimasukkan ke rangkaian simbol output yaitu number, stringcon, identifier, dan function_identifier. Berikut ini adalah pola regex untuk simbol-simbol tersebut: number Æ digit {digit} | digit {digit} . digit {digit} | digit {digit} scale_number | digit {digit} . digit {digit} scale_number stringcon Æ closed_stringcon | {acceptable_char | digit} acceptable_char {acceptable_char | digit} identifier Æ {acceptable_char | digit} acceptable_char {acceptable_char | digit} function_identifier Æ identifier
C.2
Parser
Parser merupakan bagian yang bertugas untuk melakukan analisis sintaks. Analisis sintaks yang juga dikenal sebagai parsing, adalah proses verifikasi terhadap source code untuk menguji apakah program yang dihasilkan merupakan kalimat yang legal menurut aturan sintaks / grammar pada bahasa yang bersangkutan. Aturan sintaks atau aturan tata bahasa yang berlaku untuk bahasa alami maupun bahasa pemrograman secara formal didefinisikan oleh Noam Chomsky [GRU98]. Menurut Chomsky, sebuah tata bahasa / grammar <Σ, N, P, S> terdiri dari 4 bagian : 1) Sebuah set terhingga Σ yang terdiri dari simbol terminal, komponen penyusun terkecil dalam bahasa tersebut. 2) Sebuah set terhingga N yang terdiri dari simbol nonterminal atau kategori sintaks, yang masing-masing merupakan koleksi subfrase dari kalimat. 3) Sebuah set terhingga P yang terdiri dari aturan atau produksi yang menggambarkan bagaimana tiap simbol nonterminal didefinisikan menggunakan simbol terminal dan/atau simbol nonterminal. 4) Sebuah nonterminal istimewa S, simbol awal, yang menspesifikasikan entitas
utama yang didefinisikan – misalnya kalimat atau program. Dalam konteks bahasa pemrograman, simbol terminal adalah simbol-simbol yang dikenali dalam bahasa tertentu, yaitu simbol-simbol yang menjadi bagian dari rangkaian simbol yang dihasilkan oleh scanner. Simbol nonterminal bersama dengan
C-5 aturan-aturan produksi digunakan untuk mendefinisikan bagaimana menyusun simbol-simbol terminal menjadi kalimat-kalimat yang valid agar dapat dipahami. Simbol awal merepresentasikan entitas yang hendak dibangun – misalnya, simbol awal dalam bahasa Pascal adalah <program>. Aturan produksi dalam sebuah grammar bahasa pemrograman umumnya dinotasikan menggunakan Backus Naur Form (BNF) atau Extended Backus Naur Form (EBNF) [FIN95]. BNF adalah sebuah metalanguage – bahasa untuk mendefinisikan bahasa lain. Berikut ini adalah sebuah contoh aturan produksi pada notasi BNF: <deklarasi> ::= var <list variabel> : ;
Pada contoh aturan produksi di atas,
var, :
dan
;
merupakan simbol terminal, dan
simbol nonterminal ditulis di antara pasangan kurung siku
<>.
Simbol
::=
pada BNF
dapat diartikan sebagai “didefinisikan sebagai” atau “mungkin tersusun dari”. Metode parsing yang digunakan pada implementasi parser untuk bahasa pemrograman Pascal pada Deimos yaitu metode LL(1) – huruf L yang pertama berarti bahwa simbol diproses berurutan dari kiri ke kanan, dan huruf L yang kedua berarti bahwa identifikasi produksi dimulai dari produksi terkiri, sementara angka 1 berarti simbol diproses satu per satu. Parser LL(1) dapat dibuat secara otomatis menggunakan generator atau secara manual menggunakan teknik recursive descent. Pada Tugas Akhir ini, parser LL(1) untuk bahasa pemrograman Pascal diimplementasikan
secara
manual
menggunakan
teknik
recursive
descent.
Perancangan parser tersebut secara lebih detil dijelaskan pada Subbab C.2.1. Untuk parser bahasa pemrograman LISP, pada implementasinya diintegrasikan dengan implementasi scanner agar dalam sekali pass saja sudah dihasilkan token. Untuk LISP hal ini dimungkinkan karena grammar LISP jauh lebih sederhana daripada Pascal. Grammar untuk parser LISP secara lebih detil dijelaskan pada Subbab C.2.2. C.2.1 Perancangan Parser untuk Bahasa Pemrograman Pascal Pada Subbab ini, diuraikan aturan produksi pada bahasa pemrograman Pascal menggunakan notasi BNF untuk keperluan perancangan parser. Aturan-aturan produksi tersebut diadopsi dari [WIR72]. Namun ada beberapa penambahan aturan pada grammar karena compiler yang dipakai di praktikum kelas pemrograman Teknik
C-6 Informatika ITB yaitu Free Pascal Compiler yang dapat menangani grammar yang sudah diperluas misalnya versi Borland dan Turbo Pascal. Tidak semua aturan sintaks yang dapat ditangani FPC diimplementasikan pada parser ini, melainkan hanya beberapa fitur yang sering dipakai oleh mahasiswa kelas pemrograman saja. Contohcontoh aturan sintaks tambahan tersebut misalnya nama program di awal source code dan terminal titik koma (;) ekstra di akhir statement case dan record. Beberapa modifikasi terhadap grammar dilakukan agar aturan-aturan produksi dapat diimplementasi untuk proses parsing dengan LL(1). Setiap aturan produksi akan menjadi satu prosedur pada implementasi parser di Tugas Akhir ini. <program> ::= program identifier ; . | . ::= {<procedure_and_function_declaration_part>} ::= ∈ | label unsigned_integer {, unsigned_integer} ; ::= ∈ | const {; } ; ::= ∈ | type {; } ; ::= ∈ | var ; { ;} <procedure_and_function_declaration_part> ::= ∈ | <procedure_declaration> ; ; | ; ; ::= unsigned_integer | unsigned_real ::= | stringcon | identifier | nil ::= string | <sign> | <sign> ::= + | ::= | identifier ::= identifier = ::= <simple_type> | <structured_type> | <pointer_type> ::= identifier = <simple_type> ::= <scalar_type> | <subrange_type> | identifier
C-7 <scalar_type> ::= ( identifier {, identifier} ) | integer | real | boolean | char <subrange_type> ::= . . <structured_type> ::= packed | ::= <array_type> | | <set_type> | <array_type> ::= array [ <simple_type> {, <simple_type>} ] of ::= record end ::= | ::= ; | ∈ ::= {; } ::= identifier {, identifier} : ::= case identifier : identifier of {; } ::= : ( ) ::= {, } <set_type> ::= set of <simple_type> ::= file of <pointer_type> ::= ^ identifier ::= identifier {, identifier} : ::= identifier {} ::= | | ^ ::= [ <expression> {, <expression>} ] ::= . identifier <expression> ::= <simple_expression> { <simple_expression>} <simple_expression> ::= { } | <sign> { } ::= = | <> | < | <= | >= | > | in ::= + | - | or ::= {<multiplying_operator> } <multiplying_operator> ::= * | / | div | mod | and
C-8 ::= | identifier | ( <expression> ) | not | <set> ::= {} | ( <expression> {, <expression>} ) <set> ::= [ <set_inside> ] <set_inside> ::= <expression> {, <expression>} <statement> ::= | unsigned_integer : ::= <simple_statement> | <structured_statement> <simple_statement> ::= ∈ | <simple_statement_tail> | <simple_statement_tail> ::= ∈ | := <expression> | ( <expression> {, <expression>} ) ::= goto unsigned_integer <structured_statement> ::= | | | <with_statement> ::= begin <statement> {; <statement>} end ::= | ::= if <expression> then <statement> <else_statement> <else_statement> ::= ∈ | else <statement> ::= case <expression> of {; } end ::= : <statement> ::= <while_statement> | | <while_statement> ::= while <expression> do <statement> ::= repeat <statement> {; <statement>} until <expression> ::= for identifier := do <statement> ::= <expression> <expression> ::= to | downto <with_statement> ::= with do <statement> ::= {, } <procedure_declaration> ::= <procedure_heading> ; ;
C-9 <procedure_heading> ::= procedure identifier <parameter_list> <parameter_list> ::= ∈ | ( {; } ) ::= <parameter_group> | var <parameter_group> | function <parameter_group> | procedure identifier {, identifier} <parameter_group> ::= identifier {, identifier} : identifier ::= function identifier <parameter_list> : identifier
Berdasarkan aturan produksi yang telah diuraikan di atas, token disimpan ketika aturan-aturan produksi tertentu dipenuhi. Daftar token untuk merepresentasikan source code berbahasa pemrograman Pascal diuraikan di Tabel C-1. Tabel C-1. Daftar Token yang Merepresentasikan Elemen Source Code Pascal Aturan produksi Token (integer) Keterangan program identifier ; Awal program 354 .
<procedure_declaration> ; ; ; ; for identifier := do <statement> repeat <statement> {; <statement>} until <expression> while <expression> do <statement> case <expression> of {; } end ifsy <expression> thensy <statement> <else_statement> else <statement> goto unsigned_integer := <expression> ( <expression> {, <expression>} ) write ( { stringcon ,} {, } ) ; read ( ) ; identifier =
168 797
Akhir program Awal prosedur
833 366
Akhir prosedur Awal fungsi
892 239 321
Akhir fungsi Deklarasi label Awal statement for
299 463
Akhir statement for Awal statement repeat
911 979
Akhir statement repeat Awal statement while
381 511
Akhir statement while Awal statement case
588 739 475
Akhir statement case Elemen statement case Awal statement if
983 175 641 445 733 214
Akhir statement if Awal statement else Akhir statement else Statement goto Assignment Pemanggilan prosedur
775
Mencetak nilai ke layar
496 816
meminta input pengguna Definisi tipe
C-10 Aturan produksi identifier = identifier { , } : <standard_scalar_type> identifier { , : <scalar_type> identifier { , : identifier identifier { , : <subrange_type> identifier { , : <array_type> identifier { , : identifier { , : <set_type> identifier { , :
Token (integer) 902 83
}
131
}
139
}
13
}
121
}
156
}
102
}
59
Keterangan Definisi konstanta Deklarasi variabel bertipe integer / boolean / real / char / longint. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe scalar. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe terdefinisi. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe subrange. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe array. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe record. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe set. Jumlah token sesuai jumlah variabel. Deklarasi variabel bertipe file. Jumlah token sesuai jumlah variabel.
C.2.2 Perancangan Parser untuk Bahasa Pemrograman LISP Pada Subbab ini, diuraikan aturan produksi pada bahasa pemrograman LISP menggunakan notasi BNF untuk keperluan perancangan parser. Di bawah ini merupakan aturan-aturan produksi tersebut. Untuk dapat mengenali simbol-simbol tersebut, perlu ada bantuan pengenalan kalimat ketika pembacaan file. Berikut ini didefinisikan aturan kalimat yang valid pada bahasa pemrograman LISP disertai pola regex yang mendefinisikannya : ::= ( {<s_expression>} ) ::= ( defun ( {} ) {<s_expression>} ) <list> ::= ‘ <list2> ::= ( {} ) ::= <list> | <list2> | <stringcon> | <s_expression> ::= | | | | | <list>
Sesuai dengan analisis pada Subbab 3.2.7.1, token yang dihasilkan oleh tokenizer Deimos
berupa
integer.
Daftar
keyword
LISP
serta
nilai
token
yang
merepresentasikannya diuraikan pada Tabel C-3, sedangkan daftar simbol LISP serta nilai token yang merepresentasikannya diuraikan pada Tabel C-2.
C-11 Tabel C-2. Daftar Simbol LISP serta Nilai Token yang Merepresentasikannya Simbol Token (integer) identifier 102 function_identifier 739 string_constant 192 number 131 Tabel C-3. Daftar Keyword LISP serta Nilai Token yang Merepresentasikannya Keyword Token (integer) Keterangan ( 445 ) 356 defun 692 Dipakai untuk pendefinisian fungsi ‘ 59 car | cdr | cadr | cddr | 692 Fungsi dasar untuk memanipulasi list, list | cons | append khususnya konstruktor dan selektor + | - | * | / | exp 289 Operator aritmatika print 299 dotimes 321 when 341 = | /= | < | > | <= | >= 354 Operator relasional loop 463 if 475 read 496 cond 511 let 641 Assignment dengan scope lokal setq 733 Assignment atom | listp | null | 797 Fungsi dasar untuk memanipulasi list, equal khususnya predikat not | and | or 816 Operator boolean lambda 833 return 911 do 979
LAMPIRAN D DIAGRAM SEQUENCE Pada lampiran ini diberikan diagram sequence berdasarkan definisi use case pada Subbab 3.2.5. Diagram sequence ini digunakan untuk membantu perancangan kelas final.
D.1
Diagram Sequence untuk Use Case Mendeteksi
Plagiarisme Pada Subbab ini diberikan diagram sequence untuk use case mendeteksi plagiarisme. Karena proses deteksi plagiarisme melibatkan banyak kelas dan pemanggilan fungsi, untuk kemudahan pembacaan dan perancangan terdapat empat diagram sequence untuk use case ini, yaitu diagram sequence untuk trigger deteksi, diagram sequence untuk tokenizing, diagram sequence membandingan setiap pasangan token string, dan diagram sequence mengirimkan notifikasi ketika deteksi selesai. D.1.1 Diagram Sequence untuk Trigger Deteksi Diagram sequence untuk trigger deteksi diberikan pada Gambar D-1. Kelas-kelas yang terlibat yaitu kelas Detection dan DetectionTrigger. Kedua kelas tersebut merupakan bagian dari aplikasi web Deimos.
: StartDetectionForm
: Detection
: DetectionTrigger
setDetectionInfo( )
insertDetecti onRecord( ) getDirectoryName( ) directory name
executeDetector( )
Gambar D-1. Diagram Sequence untuk Trigger Deteksi
1
D-2 D.1.2 Diagram Sequence untuk Tokenizing Diagram sequence untuk tokenizing diberikan pada Gambar D-2. Setelah aplikasi backend Deimos dieksekusi, dilakukan scanning dan parsing terhadap source code pada direktori input. Setiap proses parsing yang berhasil akan menghasilkan output berupa token string.
: Pengajar
: DirectoryBrowser
: Scanner
: Parser
: FileCReader
: Program
: T oken
: DatabaseConnector
browseDirectory( ) chooseLanguage( )
browseProgramDirectory( ) insertProgramRecord( ) modifyDatabase( )
startScan( )
setFilenam e( ) resetColRow( ) ST ART( )
ADVANCE( ) getCC( ) CC
selectStringRecord( ) reserved words of programm ing language setEverything( )
EOP( ) end of file closeFil e( ) tokens from scanner
startParse( )
getT okenContent( ) token content
addT oken( ) setEverything( )
modifyDatabase( )
parsing status
updateParseStatus( ) modifyDatabase( )
Gambar D-2. Diagram Sequence untuk Tokenizing
D-3 D.1.3 Diagram Sequence untuk Membandingkan Setiap Pasangan Token String Diagram sequence untuk membandingkan setiap pasangan token string diberikan pada Gambar D-3. Setiap token string yang dihasilkan dari tokenizing akan dibandingkan satu sama lain.
: Pengajar
: PairMaker
: RKRGreedyStringT iler
: Match
: ProgramPair
: T il e
: Program
: T oken
: DatabaseConnector
makePairs( ) com pare( ) getProgram1( ) program 1 getTokenStri ng( ) selectResul tSet( ) token records of program 1 setEverything( ) token string of program 1
getT okenContent( ) token content
getProgram2( ) program 2
getT okenString( ) selectResul tSet( ) token records of program 2 setEverything( ) token string of program 2
getT okenContent( ) token content
rkrgst( )
scanpattern( )
setEverything( )
markstrings( )
get_p( ) p get_t( ) t get_s( ) s
setEverything( )
insertT iles( ) insertTil eRecord( ) modifyDatabase( )
countSimilarity( )
setSimilarity( )
insertProgramPairRecord( ) modifyDatabase( )
Gambar D-3. Diagram Sequence untuk Membandingkan Setiap Pasangan Token String
D-4 D.1.4 Diagram Sequence untuk Mengirimkan Notifikasi bahwa Deteksi Selesai Diagram sequence untuk mengirimkan notifikasi bahwa deteksi selesai diberikan pada Gambar D-4. Notifikasi dikirimkan dalam bentuk email. Pengiriman email dilakukan melalui protokol SMTP.
: Pengajar
: MailSender
: Mail
: DatabaseConnector
sel ectStringRecord( ) email address setEverything( ) sendMail( ) getContent( ) content
getFromAddress( ) from address
getT oAddress( ) to address
getCcAddress( ) cc address
getSubject( ) subject
val idateMail( )
Gambar D-4. Diagram Sequence untuk Mengirimkan Notifikasi bahwa Deteksi Selesai
D-5
D.2 Diagram Sequence untuk Use Case Melihat Hasil Deteksi Pada Subbab ini diberikan diagram sequence untuk use case melihat hasil deteksi. Terdapat dua jenis halaman untuk menampilkan hasil deteksi, yaitu halaman utama dan halaman perbandingan pasangan source code. Diagram sequence untuk melihat masing-masing tampilan dapat dilihat pada Subbab D.2.1 dan Subbab D.2.2. D.2.1 Diagram Sequence untuk Melihat Halaman Utama Hasil Deteksi Diagram sequence untuk melihat halaman utama hasil deteksi diberikan pada Gambar D-5. Tampilan yang dihasilkan dapat dilihat pada Subbab 4.4.4.
: Mai nResul tPage
: DetectionResultFetcher
: Detection
setDirectoryName( ) selectDetecti onRecord( ) detection i nstance
setDetection( )
getDetectionInfo( ) getDirectoryName( ) directory name getDate( ) date getStartT ime( ) start ti me getEndT ime( ) end ti me getSensitivity( ) sensiti vi ty getPrgLanguage( ) programmi ng language
getNumberOfPrograms( )
detection i nformati on
countSi mil arityDi stributi on( ) similarity distribution array getColorT able( ) color array
getRepositoryList( ) list of programs
getSimi lari tyList( ) li st of si milarity of every pai r
Gambar D-5. Diagram Sequence untuk Melihat Halaman Utama Hasil Deteksi
D-6 D.2.2 Diagram Sequence untuk Melihat Halaman Perbandingan Pasangan Source Code Diagram sequence untuk melihat halaman perbandingan pasangan source code diberikan pada Gambar D-6. Rancangan tampilan halaman ini dapat dilihat pada Subbab 4.4.5. : Vi ewPairPage
: Detecti onResultFetcher
getTil esPosi tions( ) posi tions of til es for source code 1 getTil esPosi tions( ) posi tion of ti les for source code 2
Gambar D-6. Diagram Sequence untuk Melihat Halaman Perbandingan Pasangan Source Code
D.3 Diagram Sequence untuk Use Case Menghapus Hasil Deteksi Diagram sequence untuk use case menghapus hasil deteksi diberikan pada Gambar D-7. Semua record pada basis data yang merupakan hasil deteksi plagiarisme pada direktori input akan dihapus. : DeleteDetectionResultForm
: Detection
setDirectoryNam e( ) deleteDetectionRecord( )
Gambar D-7. Diagram Sequence untuk Use Case Menghapus Hasil Deteksi
