tugas teori komputasi (cs3113) file · web viewj = 1 2 3 …… 250. array yang berfungsi untuk...
Post on 27-Apr-2019
221 Views
Preview:
TRANSCRIPT
I. DESKRIPSI MASALAHDalam melakukan perancangan perangkat lunak yang mengimplementasikan
PDA dengan null stack, kami membatasi masalah yang ditangani sebagai berikut:
1. Perangkat lunak tidak menangani pengecekan struktur IF-THEN-ELSE
pada bahasa selain Pascal.
2. Kondisi status pada IF tidak berupa ekspresi boolean, hanya bernilai true
atau false.
3. Statement setelah THEN dan ELSE bisa berupa blok IF-THEN-ELSE lagi
(bersarang) ataupun statement saja.
4. Data yang diinputkan user bernilai valid jika berhasil di-trace sampai inputan
habis dan stack berakhir dengan kondisi null.
II. STRATEGI SOLUSILangkah-langkah untuk menyelesaikan masalah pengecekan struktur blok IF-
THEN-ELSE pada bahasa PASCAL adalah sebagai berikut:
1. Membuat diagram PDA dengan null stack yang deterministik, lengkap
dengan definisinya.
Definisi:
M = (Q, Σ, Γ, S, F, Z, Δ)
Q = {q0, q1, q2, q3, q4, q5, q6, q7, q8, q9, q10, q11, q12, q13, q14}
Σ = {if, then, begin, end, st, else, ;, true, false}
Γ = {z, if, begin, true, false, end, else }
S = q0
F = Ø
Z = z
Δ = Current State Input Top
Stack Next State Isi Stack
q0 If z q0 Ifz
q0 True If q0 Trueif
q0 False If q0 Falseif
q0 Then True q1 ε
q0 Then False q1 ε
q1 If Begin q0 Ifbegin
1
q1 If If q0 Ifif
q1 Begin If q1 Beginif
q1 St Begin q3 Begin
q1 St If q2 If
q1 ; Begin q1 Begin
q1 ; z q6 z
q1 ; If q6 If
q1 Else If q5 ε
q1 ε If q1 ε
q1 ε else q8 ε
q1 ε Z q7 z
q1 End Begin q4 ε
q1 End If q8 Endif
q2 End Begin q4 ε
q2 End If q8 Endif
q2 Else If q5 ε
q2 ; z q6 z
q2 ; If q6 If
q2 ε If q2 ε
q2 ε z q7 z
q2 ε else q8 ε
q3 ; Begin q1 Begin
q3 End Begin q4 ε
q4 End Begin q4 ε
q4 End If q8 Endif
q4 ; z q4 z
q4 ; Begin q4 Begin
q4 ; If q6 If
q4 ; Else q13 Else
q4 Else If q5 Ε
q4 ε If q4 ε
q4 ε z q7 z
2
q4 Ε else q8 ε
q5 If z q0 Ifz
q5 If Begin q0 Ifbegin
q5 If If q0 Ifif
q5 St If q4 If
q5 St Begin q4 Begin
q5 St z q4 z
q5 End Begin q4 ε
q5 End If q8 Endif
q5 ; If q6 If
q5 ; z q6 z
q5 Else If q5 ε
q5 Begin Begin q1 Beginbegin
q5 Begin If q1 Beginif
q5 Begin z q1 Beginz
q5 ε If q5 ε
q5 ε z q7 z
q6 ; z q6 z
q6 ; If q6 If
q6 ε If q6 ε
q6 ε z q7 z
q8 ε End q9 ε
q8 ; End q14 End
q8 Else End q12 Elseend
q9 ε If q9 ε
q9 ε Begin q10 ε
q10 ε Else q8 ε
q10 ε End q9 ε
q10 ε If q11 ε
q11 ε End q9 ε
q11 ε If q11 ε
q11 ε Else q8 ε
3
q11 ε z q8 z
q12 If Else q0 Ifelse
q12 Begin Else q1 Beginelse
q12 ; Else q13 Else
q12 St Else q13 Else
q13 ε Else q8 ε
q13 ; Else q13 Else
q14 ; End q14 End
q14 ε End q9 ε
Diagram PDA dari definisi diatas:
Gb.1 PDA-null stack untuk pengecekan IF-THEN-ELSEpada bahasa pemrograman Pascal
4
2. Mendefinisikan grammar.
Grammar atau aturan produksi dari PDA tersebut adalah:
<statement> ::= IF <status> THEN <sub>
| IF <status> THEN begin <sub> end
| IF <status> THEN <sub> ELSE <sub>
| IF <status> THEN begin <sub> ELSE <sub> end
<status> ::= TRUE | FALSE
<sub> ::= <statement> | st
3. Melakukan perancangan perangkat lunak yang sesuai dengan PDA yang
telah dibuat.
Untuk perancangan ini akan dibahas pada bagian III.
4. Melakukan pengujian terhadap perangkat lunak yang telah dibuat dengan
mengambil contoh kasus.
Contoh kasus yang digunakan untuk menguji perangkat lunak ini terdiri dari
dua kasus. Kasus pertama untuk hipotesis struktur IF THEN ELSE yang
benar dan yang kasus kedua untuk struktur yang tidak beraturan.
III. PERANCANGANSetelah melakukan analisis masalah lalu membuat PDA, langkah berikutnya
adalah melakukan perancangan perangkat lunak.
III.1 ProsesProses yang dilakukan dalam perangkat lunak sebenarnya adalah pengenalan
input menjadi token-token. Kemudian token tersebut dicocokkan dengan PDA null
stack yang telah didefinisikan, dalam hal ini kami sebut sebagai tracing PDA. Jika
tracing inputan dari user sesuai dengan PDA yang didefinisikan, maka inputan
tersebut valid.
5
Gb.2. DFD Level 0
Gb.3. DFD Level 1 (Pengecekan PDA)
6
Gb.4. DFD Level 2 (Penyimpanan Inputan)
III.2 Data dan Struktur Data
Struktur Data
No
Struktur Data
1. inpraw = array of byte (1 .. 500)inpraw
I = 1 2 3 …… 500
Array yang berfungsi untuk menyimpan inputan. Tiap elemennya akan diisi kode ASCII dari karakter inputan. Contoh inputan = “ABC.” . maka array inpraw akan berisi
I = 1 2 3 4 2. arrkata1 = array of byte (1 .. 250)
arrkata1
J = 1 2 3 …… 250
Array yang berfungsi untuk menyimpan informasi posisi cursor dalam textbox inputan dimana suatu kata pada arrkata2 berada.
7
65 66 67 46
arrkata1 = berisi posisi kata arrkata2 = berisi kata
3. arrkata2 = array of string (1 .. 250)arrkata2
J = 1 2 3 …… 250
Array yang berfungsi untuk menyimpan kata. Definisi kata disini ialah : satu atau beberapa karakter yang dipisahkan oleh spasi, enter, atau karakter “;”. Karena karakter “;” juga akan diproses sebagai inputan PDA, maka karakter “;” dan posisinya juga disimpan dalam arrkata2 dan arrkata1.contoh: input =
maka arrkata1 dan arrkata2 akan berisiarrkata1
arrkata2
j = 1 2 3 4 5 4. jmlkar : integer
Variabel yang berisi jumlah karakter pada kotak inputan (text1.text)5. sel : integer
Variabel yang berisi index kata yan sedang diproses6. stkawal : integer
Variabel yang berisi index awal dari stack7. stkakhir : integer
Variabel yang berisi index akhir dari stack8. kec : integer
Variabel yang berisi angka yang menyatakan kecepatan gerak dari objek stack yang sedang dianimasikan
9. vkedip : integerVariabel yang berisi angka yang menyatakan kecepatan kedip dari objek stack yang sedang di pop
10 currentst : string
8
PDA null stack ; if
0 4l 9 14 15
. Variabel yang berisi state pada saat sekarang (current state)
Event
No
Event
1. treset_click( )Untuk mengembalikan keadaan ke saat tahap pengguna belum menginstruksikan pemrosesan inputan (mengklik tombol start)
2. tstart_click( )Untuk memulai memproses inputan
3. tnext_click( )Untuk menuju pemrosesan selanjutnya
4. form_load( )Pertamakali software di load maka akan melakukan Inisialisasi variabel-variabel
5. kanan_timer( )Event timer yang mengatur gerak animasi ke kanan (ketika pop)
6. kedip_timer( )Event timer yang mengatur animasi kedip (ketika pop)
7. turun_timer( )Event timer yang mengatur gerak animasi bawah (ketika push)
8. texit_Click( )Untuk mengakhiri program
Module
No
Module
1. inputarray(inp As String)memasukkan karakter dari inputan ke array inpraw setelah sebelumnya diubah ke karakter ASCII terlebih dahulu.
2. removewhitespace( )modul untuk menghilangkan spasi dan enter. Memproses array inprawe, Modul akan memasukkan posisi kata pada array arrkata1 dan memasukkan katanya pada array arrkata2.
3. PlaySound(strFileName As String)fungsi untuk memainkan file wav
4. tidak_valid( )
9
modul yang berfungsi menammpilkan pesan tidak valid(invalid)5. pop( )
modul yang berfungsi melakukan proses pop pada stack. Modul tidak hanya menangani animasi tapi juga melakukan perubahan pada variabel yang terkait
6. push( )modul yang berfungsi melakukan proses push pada stack. Modul tidak hanya menangani animasi tapi juga melakukan perubahan pada variabel yang terkait
7. pda(curst As String, inputan As String, topstack As String )modul pda yang merupakan fungsi transisi dari pda pengecekan if-then-else.
III.3 Antarmuka
Desain form utama antarmuka perangkat lunak PDA adalah:
Gb.5. Desain antarmuka
Keterangan:
A = tempat mengisikan input
B = status validasi
C = tampilan hasil tracing
D = button RESET, START, NEXT, EXIT
E = tampilan hasil stack
10
A
B
C
D
E
III.4 Batasan Perangkat Lunak1. Software hanya menerima inputan maksimal 500 buah karakter ASCII.
<enter> dihitung 2 karakter ASCII, karena apabila menginputkan <enter>,
karakter ASCII yang disimpan adalah 13(enter) dan 10(line feed).
2. Dari maksimal 500 karakter ASCII tersebut, software masih dapat menerima
apabila jumlah kata yag terbentuk berjumlah kurang dari 250 buah. Karakter
“;” dianggap 1 kata. Contoh: ”if;then” dianggap 3 kata, yaitu “if”, “;”, dan
“then”.3. Batas jumlah stack (animasi stack di sebelah kanan) yang dapat diterima
ialah 22. Apabila ketika dalam tahap pemrosesan jumlah stack melebihi 22
maka kasus tersebut tidak dapat diterima software. Kasus tersebut tidak
dapat diterima software karena ruang yang ada tidak cukup untuk
menganimasikan stacknya.
IV. TOOLS YANG DIGUNAKANUntuk mengimplementasikan rancangan yang telah dibuat, kami memilih CASE
tools Microsoft Visual Basic 6. Hasil implementasi dari rancangan pada bagian III
adalah:
1. Tampilan awal saat membuka file .exe.
2. Setelah splash screen, akan langsung muncul tampilan berikut.
11
3. Jika user tidak mengisi input kemudian meng-klik akan muncul
pesan error
4. Jika user telah mengisi bagian input, kemudian meng-klik button
maka muncul tampilan berikut.
12
Untuk melanjutkan tracing input, klik button kemudian akan
terlihat pada bagian trace bahwa perangkat lunak telah mulai melakukan
pencocokkan data dan stack berubah.
13
Jika tracing telah selesai, akan muncul status atau
.
5. Jika user ingin melakukan inputan baru, klik button . Maka bagian
trace dan stack akan dikosongkan kembali.
6. Jika user ingin keluar dari aplikasi, klik button
V. PENGUJIAN PROGRAMPengujian dilakukan dengan membuat contoh kasus penanganan masalah
pengecekan IF THEN ELSE. Misalnya, user mengentrikan blok statement seperti
berikut:
Kasus I
if true then
begin
if false then
if true then
if true then
if true then
st
end
else
begin
if true then
st
end;
Maka selanjutnya perangkat lunak akan mulai mengecek statement yang
dientrikan. Ilustrasi saat proses pengecekan selesai:
14
Dari gambar tersebut terlihat bahwa pengecekan dilakukan dengan bantuan
stack. Jika stack tersebut berakhir dengan null, maka entri dari user tersebut valid
dan termasuk struktur IF THEN ELSE yang dapat diterima di bahasa Pascal.
Kasus II
if false then
st
else
if true then
st
else
begin
if true then
st
end
Setelah menekan tombol ENTER, perangkat lunak memulai pengecekan dengan
bantuan stack. Ilustrasi hasil akhirnya adalah sebagai berikut:
15
Berdasarkan ilustrasi di atas, terlihat bahwa stack tidak berakhir dengan null dan
status invalid. Hal ini berarti statement yang dientrikan oleh user tidak valid untuk
dikatakan sebagai struktur IF THEN ELSE pada bahasa Pascal.
16
top related