SIMULASI TRANSFORMASI REGULAR EXPRESSION TERHADAP FINITE STATE AUTOMATA

Pelita Informatika Budi Darma, Volume : IV, Nomor: 1, Agustus 2013

ISSN : 2301-9425

SIMULASI TRANSFORMASI REGULAR EXPRESSION TERHADAP FINITE STATE AUTOMATA Sinar Sinurat Dosen Tetap STMIK Budi Darma Medan Jl. Sisingamangaraja No. 338 Simpang Limun Medan www.stmik-budidarma.ac.id // E-Mail :[email protected]

ABSTRAK Automata adalah aktivitas yang mengurusi persoalan formalisasi tatabahasa (grammar) dengan alat bantu mesin matematis. Finite State Automata (FSA) terdiri dari Non-Deterministic FSA (NFSA) dan Deterministic FSA (DFA). FSA digunakan untuk mengenali bahasa reguler dengan notasi ekspresi. Dalam automata mengandung unsur : Grammar (tata bahasa), Parsing (mengurai string-string dalam buffer), Scanning (membaca data streaming ke dalam buffer) Dalam paper mencakup bahasan bagaimana proses transformasi reguler expression ke DFA dan NFA dengan menguraikan tahap demi tahap hingga muncul diagram transisi yang akan digunakan untuk meregulasi bahasa. Paper ini akan menghasilkan diagram transisi yang bersifat non deterministik dan deterministik, dan sebelumnya tabel diagram transisi sudah terbentuk. Kata Kunci : Buffer, ekspressi, scanning, diagram transisi, non determistik dan deterministik

1. Pendahuluan 1.1. Latar Belakang Teori bahasa adalah salah satu topik materi pendukung yang membicarakan formalisasi (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja. Mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Automata secara umum dipelajari bersama dengan teori bahasa. Alasan yang mendasar adalah sebagai berikut : 1. Rangkaian input dapat dianggap sebagai bahasa yang harus dikenali oleh automata tersebut. 2. Automata dapat berfungsi untuk membangkitkan bahasa tertentu yang aturannya ditentukan oleh tata bahasa (grammar) tertentu.

input yang sama. Perbedaan lainnya adalah DFA tidak menerima input kosong (empty), tidak seperti NDFA. FSA yang biasanya pertama kali dirancang adalah NFA, dan kemudian ditransformasi ke bentuk DFA sebagai bentuk yang lebih minimal dan efisien. Dalam proses transformasi, umumnya dilakukan beberapa tahapan khusus dan kompleks. 1.2. Tujuan Adapun tujuan yang ingin dicapai adalah: 1. Untuk mengetahui proses transformasi (konversi) ekspressi reguler ke bentuk DFA yang efektif dan lebih praktis. 2. Untuk memberikan deskripsi yang lebih praktis dalam pemahaman proses regulasi bahasa beserta proses pembuatan diagram transisi. 3. Untuk memberi kemudahan terhadap para pemrogram untuk membuat coding dalam bahasa pemrograman yang sesuai dengan keinginan. 1.3. Identifikasi Masalah Agar pembahasan tidak terlalu meluas dan tidak menyimpang dari tujuan maka maka unsur-unsur yang akan dibahas adalah sebagai berikut : 1. Pemberian input ekpressi reguler yang sederhana dan memenuhi kaidah grammar 2. Proses transformasi ekspressi reguler ke NFA kemudian kebentuk DFA dilakukan dengan tahap-tahap. 3. Tahap demi tahap transformasi mengandung langkah-langkah yang diulang (iterasi).

Beberapa perbedaan di antara keduanya adalah bahwa DFA menerima sebuah input dimana state tujuan dari input tersebut adalah satu, sedangkan NDFA dapat menuju beberapa state tujuan untuk “Simulasi Transformasi Regular Expression Terhadap Finite State Automata” Oleh : Sinar Sinurat

1


1.4. Batasan Masalah Agar pembahasan lebih fokus diberikan batasan yaitu: 1. Input ekspressi reguler/ bahasa reguler sembarang 2. Proses transformasi (konversi) dalam domain prinsip-prinsip kompilasi 3. State-state yang diterima adalah simbol nonterminal berupa 1 karakter huruf kapital atau angka. 4. Alfabet-alfabet yang diterima sebagai input untuk otomata adalah 1 karakter sembarang (non kapital jika huruf) dan alfabet empty (ε) sebagai karakter spasi (blank). 5. Tidak membahas penentuan inaccessible state dan state ekuivalen. 1.5. Metode Penelitian Penyelesaian paper ini dilakukan dengan cara : 1. Kepustakaan a. Mencari sejumlah literatur yang berhubungan dengan automata dan kompilasi baik berupa buku, artikel (majalah maupun internet), source code program, dan sebagainya. b. Mencari bentuk konversi yang lebih mudah dipahami dan diterakan ke dalam bahasa pemrograman c. Merancang algoritma yang menginterpretasikan seluruh langkah teoritis dalam bentuk pseudo code 2. Laboratorium a. Merancang coding program yang dapat dikompilasi sewaktu-waktu b. Menguji program dengan sejumlah input ekpressi reguler yang bervariasi c. Validasi dengan sejumlah teori dan mencatat sejumlah perbedaan antara teori dan praktek d. Implementasi 2.

Dasar Teoritis

2.1 Beberapa Pengertian Dasar Proses penerjemahan suatu bahasa sumber (source program) menjadi bahasa target (target program), biasanya dilakukan dengan proses kompilasi, perhatikan diagram berikut :

Beberapa tools software yang dapat digunakan bahasa sumber seperti : 1. Structure Editor : mengambil sejumlah untaian perintah untuk dibangun menjadi bahasa sumber, membuat teks, dan memodifikasi

2.

3.

4.

ISSN : 2301-9425

fungsi yang aneh serta menganalisa teks program dalam bentuk hirarki Pretty Printer : menganalisa suatu program dan cetakan dengan beberapa cara sehingga struktur program menjadi jelas, misalnya berupa font tertentu, indend (tab) Static Checker : membaca, mengalisa, menempatkan program dalam posisi tawaran perubahan serta mendeteksi program tanpa pernah dieksekusi Interpreter : menghasilkan suatu target program sebagai suatu translasi untuk dipakai menjadi source program

Program-program yang menggunakan teknologi kompiler konvensional antara lain : 1. Text Formatter : mengambil input sebagai stream karakter termasuk perintah untuk mengenali paragraf, gambar atau struktur matematika (subscript, superscript) 2. Silicon Compiler : fungsional programming languange di mana variabel-variabel merepresentasi bahasa untuk signal logika (0 or 1 or grup signal) tidak berada di memory akan tetapi ada di rangkaian switching 3. Query Interpreter : menerjemahkan predikat relasi dan operator boolean menjadi command untuk mencari database records yang memenuhi predikat Beberapa pemahaman dasar untuk mengenali (recognize), menerima (accept), ataupun membangkitkan (generate) sebuah kalimat dalam bahasa tertentu adalah sebagai berikut : 1. Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. 2. String adalah deretan terbatas (finite) simbolsimbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut. 3. Jika w adalah sebuah string maka panjang string dinyatakan sebagai w dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w= 4. 4. String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol  (atau ^) sehingga = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol. 5. Alfabet adalah hinpunan hingga (finite set) simbol-simbol

2.2 Operasi Dasar String Diberikan dua string : x = abc dan y=123  Prefix string w adalah string dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w “Simulasi Transformasi Regular Expression Terhadap Finite State Automata” 2 Oleh : Sinar Sinurat


 tersebut. Contoh : abc, ab, a, dan  adalah semua Prefix(x)  Proper Prefix string w adalah string dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut. Contoh : ab, a, dan  adalah semua Proper Prefix(x)  Postfix (Suffix) string w adalah string dihasilkan dari string w dengan menghilangkan nol atau lebih simbol paling depan dari string w tersebut. Contoh : abc, bc, c, dan  adalah semua Postfix(x)  Proper Postfix (atau Proper Suffix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol paling depan dari string w tersebut. Contoh : bc, c, dan  adalah semua Proper Postfix(x).  Head string w adalah simbol paling depan dari string w. Contoh : a adalah Head(x).  Tail string w adalah string dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut. Contoh : bc adalah Tail(x)  Substring w adalah string dihasilkan dari string w dengan menghilangkan nol atau lebih simbol paling depan dan/atau simbol paling belakang dari string w tersebut. Contoh : abc, ab, bc, a, b, c, dan  adalah semua Substring (x)  Proper Substring w adalah string dihasilkan dari string w dengan menghilangkan satu atau lebih simbol paling depan dan/atau simbol paling belakang dari string w tersebut. Contoh : ab, bc, a, b, c, dan  adalah semua Substring (x)  Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol dari string w tersebut. Contoh : abc, ab, bc, ac, a, b, c, dan  adalah Subsequence (x)  Proper Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol dari string w tersebut. Contoh : ab, bc, ac, a, b, c, dan  adalah semua Subsequence (x)  Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang. Contoh : concate(xy) = xy = abc123  Alternation adalah satu di antara dua buah string. Operator alternation adalah alternate atau . Contoh : alternate(xy) = xy = abc atau 123  Kleene Closure, berbentuk : x* = xxx … = 2

3

xx x … 

Positive Closure : x 2

3

xx x …



= xxx … =

ISSN : 2301-9425

2.3 Beberapa Sifat Operasi

Sejumlah operasi string yang dapat digunakan untuk transformasi adalah :

 Tidak selalu berlaku : x = Prefix(x) Postfix(x)  Selalu berlaku : x = Head(x)Tail(x)  Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x)  Postfix(x)  Selalu berlaku : ProperPrefix(x)  ProperPostfix(x)  Selalu berlaku : Head(x)  Tail(x)  Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya  Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya  Dua sifat aljabar concatenation : a. Operasi concatenation bersifat asosiatif : x(yz) = (xy)z b. Elemen identitas operasi concatenation adalah  : x = x = x  Tiga sifat aljabar alternation : a. Operasi alternation bersifat komutatif : xy = yx b. Operasi alternation bersifat asosiatif : x(yz) = (xy)z c. Elemen identitas operasi alternation adalah dirinya sendiri : xx = x  Sifat distributif concatenation terhadap alternation : x (yz) = xyxz  Beberapa kesamaan : a. Kesamaan ke-1 : (x*)* = (x*) b. c.





Kesamaan ke-2 : x = x  = x* Kesamaan ke-3 : (xy)* =xyxxyyxyyx… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.

2.4 Proses Regulasi Automata dan Bahasa Automata merupakan sekuensi proses secara otomatis yang menerima input dan menghasilkan output yang bersifat diskret. Rangkaian input yang diterima adalah string atau bahasa yang dikenali oleh automata. Jika rangkaian input yang diterima dan dikenali maka mesin menghasilkan output. Contoh dari automata yang telah dikenal luas adalah mesin Mealy dan mesin Moore. Bahasa merupakan kumpulan string-string dari simbol-simbol untuk suatu alfabet, atau rangkaian dari simbol-simbol yang memiliki makna. Dalam konteks automata, string-string yang di-input ke dalam otomata harus merupakan bahasa yang dapat dikenali oleh aturan pada automata. Aturan pada automata ini disebut sebagai fungsi transisi. Bahasa memiliki aturan yang disebut sebagai tata bahasa (grammar). Dalam hubungannya dengan automata, Noam Chomsky melakukan

“Simulasi Transformasi Regular Expression Terhadap Finite State Automata” Oleh : Sinar Sinurat

3


penggolongan menjadi 4 (empat) tingkatan bahasa berdasarkan aturan produksinya sebagai berikut: 1. Bahasa Reguler (tipe 3) Menggunakan Finite State Automata (FSA) sebagai pengenalnya. FSA umumnya terdiri dari sejumlah state (simbol non-terminal) sebagai kondisi pada automata, alfabet (simbol terminal) sebagai string input, state awal, state akhir, dan fungsi-fungsi transisi yang menentukan state automata yang aktif setelah menerima string input tertentu. FSA dapat dibagi menjadi 2 (dua) jenis, yaitu Non-Deterministic FSA (NFA) dan Deterministic FSA (DFA). Ciri-ciri sekaligus perbedaan di antara keduanya antara lain: a. NFA mengandung alfabet serta transisi empty (empty string/transition), sedangkan DFA tidak. b. State pada NFA dapat terdiri beberapa simbol non-terminal (mis. ABC), sedangkan state DFA hanya terdiri dari 1 simbol nonterminal. c. Satu alfabet input pada NFA dapat digunakan untuk menuju beberapa state yang berbeda (probabilitas), sedangkan alfabet input pada DFA hanya menuju 1 state. 2. Bahasa Bebas Konteks (tipe 2) Merupakan dasar pembentukan parser (pemroses analisis sintaksis pada kompilasi) yang dideskripsikan secara formal dengan notasi Backus-Nour Form (BNF) yang dikembangkan oleh Backus (1959) dan Peter Nour (1960). Bahasa ini menggunakan mesin Push-Down Automata. 3. Bahasa Context-Sensitive (tipe 1) Digunakan dalam proses analisis semantik dari tahapan kompilasi. Bahasa ini menggunakan mesin Linear-Bounded Automata. 4. Bahasa Unrestricted/ Alami (tipe 0) Bahasa ini seperti bahasa manusia. Menggunakan mesin Turing yang dirancang oleh Alan Mathison Turing. Mesin Turing digambarkan berupa barisan sel tersusun berupa pita yang dapat bergerak maju mundur, komponen aktif baca/ tulis pita yang memiliki status perhitungan serta dapat mengubah/ menulisi sel aktif pita. Model ini merupakan suatu kumpulan instruksi yang mendeskripsikan bagaimana komponen baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita, serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif, mengubah status dari komponen baca/tulis, dan mengubah posisi pita ke kiri atau ke kanan. 2.5 Analisa Penentuan Type Grammar

ISSN : 2301-9425

Untuk penulisan grammar, maka perlu memperhatikan tipe grammar sebagai berikut : 1. Grammar G 1 dengan Q 1 = {S  aB, B  bB, B  b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe contex free grammar (CFG) atau regular grammar (RG). Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VTVN maka G1 adalah RG. 2. Grammar G2 dengan Q2 = {S  Ba, B  Bb, B  b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VTVN maka G2 adalah RG. 3. Grammar G3 dengan Q3 = {S  Ba, B  bB, B  b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G3 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string VTVN (yaitu bB) dan juga string VNVT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG. 4. Grammar G4 dengan Q4 = {S  aAb, B  aB}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G4 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G4 bukan RG, dengan kata lain G4 adalah CFG. 5. Grammar G5 dengan Q5 = {S  aA, S  aB, aAb  aBCb}. Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe context sensitive grammar (CSG) atau unrestricted grammar (UG). Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G5 adalah CSG. 6. Grammar G6 dengan Q6 = {aS  ab, SAc  bc}. Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G6 kemungkinan tipe CSG atau UG. Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kananya (yaitu SAc) maka G6 adalah UG. 2.6. Derivasi Kalimat dan Penentuan Bahasa Untuk menentukan bahasa dari masing-masing grammar pada contoh berikut : Contoh 1 : G1 dengan Q1 = {1. S  aAa, 2. A  aAa, 3. A  b}, maka : derivasi kalimat terpendek : Derivasi kalimat umum : S  aAa (1) S  aAa (1)  aba (3)  aaAaa (2)   anAan (2)


4


Dari

ke dua pola L1(G1)={anbann 1}

 anban (3) kalimat diperoleh :

Contoh 2 : G2 dengan Q2 = {1. S  aS, 2. S  aB, 3. B  bC, 4. C  aC, 5. C  a}, maka : derivasi kalimat terpendek : Derivasi kalimat umum : S  aB (2) S  aS (1)  abC (3)   aba (5)  an-1S (1)  anB (2)  anbC (3)  anbaC (4)   anbam-1C (4)  anbam (5) Dari ke dua pola di atas diperoleh : L2(G2)={anbam n  ,m  1} Contoh 3 : G3 dengan Q3 = {1. SaSBC, 2. S abC, 3. bB  bb, 4. bC  bc, 5. CB BC, 6. cC cc} Maka diperoleh : derivasi kalimat terpendek : Derivasi kalimat umum : S  abC (2) S  aSBC (1)  abc (4)  aaSBCBC (1) Derivasi terpendek 2 :  aaabCBCBC (2) S  aSBC (1)  aaabBCCBC (5)  aabCBC (2)  aaabBCBCC (5)  aabBCC (5)  aaabBBCCC (5)  aabbCC (3)  aaabbBCCC (3)  aabbcC (4)  aaabbbCCC (3)  aabbcc (6)  aaabbbcCC (4)  aaabbbccC (6)  aaabbbccc (6)

ISSN : 2301-9425

Dari ke tiga pola kalimat di atas disimpulkan : L3 (G3) = { an bncnn  1} 2.7 SCANNING BUFFER Implementasi Scanner dengan siklus transformasi : GRER AHNAHDGR. Sebagai contoh, scanner (yaitu DFA) untuk mengenali identifier adalah :

Berikut fragmen program dari bahasa pascal : type Text_Pos = record {posisi penunjuk karakter} Row_Numb : word; {baris ke-, bisa ribuan baris/program_sumber} Char_Numb : byte; {karakter ke-, maksimum 255 karakter/baris} end; var Now_Pos : Text_Pos; {posisi sekarang} Line : string; {baris yang sedang diproses} End_of_line : byte; {posisi akhir baris yang sedang diproses} procedure Next_Character(var Ft : text); {baca karakter berikut pada program_sumber} begin with Now_Pos do { perintah with ... do ?} begin if Char_Numb = End_of_line then begin List_Line; {menampilkan kembali baris yang telah dibaca, beserta errornya} Next_Line(Ft); {membaca baris berikutnya} Row_Numb := Row_Numb + 1; Char_Numb := 1 end else Char_Numb := Char_Numb + 1; character := Line[Char_Numb] end end; procedure List_Line; begin write{Now_Pos.Row_Numb : 3, ‘ ‘); writeln(Line); List_Error; {menampilkan kesalahan-kesalahan yang terjadi pada suatu baris} end procedure Next_Line(Ft : text); begin readln(Ft, Line); End_of_line := length(Line) + 1: Line := Line + #32; {karakter spasi} end;

2.8 PENULISAN GRAMMAR Reguler Expression (RE) Vs Context Free Grammar (CFG). RECFG : Setiap bentuk yang dapat dideskripsikan oleh RE dapat di deskripsikan oleh CFG CFG dibentuk dari diagram transisi dengan aturan : “Simulasi Transformasi Regular Expression Terhadap Finite State Automata” 5 Oleh : Sinar Sinurat


ISSN : 2301-9425

transisi yang ada, maka jika state ketiga bukan merupakan anggota himpunan F berarti string tersebut tidak dapat diterima/dikenali oleh otomata. Misalnya : RE : (a|b)*abb maka CFG: A0  aA0|bA0|aA1 A1  bA2 A2  bA3 A3   RE digunakan untuk lexical analysis, alasannya adalah : 1. Penulisan RE lebih sederhana 2. Notasi RE lebih mudah dimengerti 3. RE dapat menghasilkan scanner yang efisien 4. Modularisasi analisis Di sisi lain bahwa RE lebih sesuai untuk mendeskripsikan token-token yaitu : 1. Identifier 2. Constant 3. Keyword (reserve word), dan lain-lain Sedangkan CFG lebih mudah untuk mendeskripsikan struktur tersarang (nested) dan berpasang (matched) yaitu 1. Tanda kurung yang berpasangan 2. Begin dan end 3. If dan else 4. FOR … do atau while … do 2.9 Finite State Automata FSA (NFA atau DFA) umumnya terdiri dari: 1. Himpunan state (simbol non-terminal) sejumlah terhingga yang disimbolkan dengan Q merupakan “keadaan” pada otomata yang dapat berubah menjadi state lain setelah menerima alfabet yang di-input. Dalam penulisan himpunan Q, state yang dituliskan pertama kali umumnya adalah state awal. 2. Himpunan alfabet (simbol terminal) sejumlah terhingga yang disimbolkan dengan  adalah simbol-simbol yang dapat dikenali oleh otomata ketika di-input sebagai string. 3. Himpunan fungsi transisi yang disimbolkan dengan  mengenali alfabet-alfabet (string) yang di-input pada otomata dan kemudian merubah state yang berlaku sekarang menjadi state lain. Misalnya string input terdiri dari 3 (tiga) alfabet, maka state dapat berubah sebanyak  3 kali dengan menggunakan  3 fungsi transisi. Contoh sebuah fungsi transisi adalah (S,0)=D, yang berarti bahwa jika alfabet 0 di-input saat state yang aktif adalah S maka state yang aktif menjadi D. 4. State awal yang disimbolkan dengan q0 adalah state yang langsung aktif saat automata dijalankan. State awal berjumlah 1 (satu) buah. 5. Himpunan state akhir (final) yang disimbolkan dengan F. Misalnya string input terdiri dari 3 (tiga) alfabet dengan menggunakan fungsi

Contoh komponen-komponen sebuah otomata adalah sebagai berikut: M = (Q,,,q0,F) Q = {S,A,B,C}  = {0,1} q0 = S F = {S}  = {(S,0)=B, (S,1)=A, (A,0)=C, (A,1)=S, (B,0)=S, (B,1)=C, (C,0)=A, (C,1)=B} Pada contoh di atas, S adalah state awal sekaligus state akhir. Fungsi transisi (S,0)=B berarti bahwa jika state sekarang adalah S dan alfabet yang di-input adalah 0, maka state berubah menjadi B. Adapun Tabel dan diagram yang digunakan dalam pembuatan pohon adalah : 1. Pohon sintaks dari Augmental RE r

2. Rules untuk menentukan nullable, firstpos, lastpos

3. Rules untuk menentukan followpos a. Jika n adalah cat-node left-child c1 dan rightchild c2, dan i adalah posisi dalam lastpos (c1) maka semua posisi lastpos (c2) adalah followpos (i) b. Jika n adalah node start dan i adalah posisi dalam lastpos (n) maka semua posisi firstpos (n) adalah dalam followpos (i) 3. Simulasi Model Transformasi 3.1 Model


6


Diberikan sembarang ekspressi reguler (RE), misalkan: r=(a|b)*abb, maka langkah-langkah untuk mengkonversikan adalah sebagai berikut : 1. Tambahkan augmented pada RE yaitu : r = ( a | b ) *a b b # 2. Berikan indeks untuk masing-masing karakter yang ada pada RE untuk menyatakan posisi node dalam pohon yaitu : r = ( a | b )* a b b # 1

2

3 4 5 6

3. Buatlah pohon sintaks untuk menyatakan nilai firstpost, lastpos dan nullable yaitu :

4. Buatlah tabel Followpos dalam Himpunan posisi semua simbol terletak pada sesudah symbol pada posisi n masing-masing node pada langkah 2 yaitu : Node 1 2 3 4 5 6

Followpos {1,2,3} {1,2,3} {4} {5} {6} -

5. Berdasarkan tabel pada langkah 4 dapat dibuat diagram transisi NFA (Digraph untuk fungsi followpos) yaitu :

6. Buatlah tabel DFA dengan menggunakan tabel followpos yaitu :

7. Bentuklah diagram transisi DFA dari tabel langkah 6 yaitu :

3.2 Simulasi DFA

ISSN : 2301-9425

Simulasi DFA dimaksudkan untuk mengenali token. type Token_Kind = record tipe : byte; nilai : byte end; var Token : array[0..Max_State] of Token_Kind; Found_Token : Token_Kind; {token yang ditemukan} Tok_Pos : Text_Pos; {posisi token dalam program sumber} procedure Next_Token(var Ft : text); {digunakan untuk mengenali sebuah token} var state1, state2 : shortint; begin state1 := 0; Tok_Pos := Now_Pos; repeat state2 := Next_State(state1, character); if state2 <> -1 then {-1 bersesuaian dengan x pada tabel transisi} begin state1 := state2; Next_Character(Ft); {baca karakter berikut pada program_sumber} {di antaranya menghasilkan nilai baru untuk Now_Pos} end; until state2 = -1; Act_for_Token(state1); end; procedure Act_for_Token(state : shortint); var Tok_Length : byte; Err : integer; begin Current_Token(Token[state].tipe, Token[state].nilai); Tok_Length := Now_Pos.Char_Numb Tok_Pos.Char_Numb; case Token[state].tipe of 0 : Error(‘Token tidak dikenal!’, Tok_Pos); 27 : Id := copy(Line, Tok_Pos.Char_Num, Tok_Length); 28 : val(copy(Line, Tok_Pos.Char_Num, Tok_Length), IN, Err); 29 : val(copy(Line, Tok_Pos.Char_Num, Tok_Length), RN, Err); end end; catatan : - copy(string, start, length) mengembalikan substring - val(string_value, number_variable, error_flag) : jika string_value = ‘137’ maka number_variable = 137 dan error_flag = 0 jika string_value = ‘string’ maka number_variable = 137 dan error_flag  0 - Token.tipe  {1, 2, 3, ..., 26} dimisalkan bernilai pasti, sehingga tidak perlu penangan-an lebih lanjut procedure Current_Token(tipe, nilai : byte); begin Found_Token.tipe := tipe; Found_Token.nilai := nilai; end;


7


4. Implementasi 4.1 Form Ekspressi Reguler Pada form ini dilakukan penginputan string untuk state, dan fungsi transisi dari NFA yang akan diproses (ditransformasi). Algoritma dalam penginputan state adalah sebagai berikut: 1. Input string 2. Jika string yang diinput adalah string akhir, beri tanda pada kotak cek Final. Algoritma dalam penginputan fungsi transisi adalah sebagai berikut: a. Input state. b. Cari state tersebut pada tabel transisi. i. Jika state tersebut tidak ada, kembali ke langkah a. ii. Jika state tersebut ada, dilanjutkan ke langkah c. c. Input alfabet. d. Cari alfabet tersebut pada tabel transisi. i. Jika alfabet tersebut tidak ada, maka kembali ke langkah c. ii. Jika alfabet tersebut ada, dilanjutkan ke langkah e. e. Input state tujuan dari fungsi transisi. f. Cari state tujuan tersebut pada tabel transisi i. Jika state tersebut tidak ada, kembali ke langkah f. ii. Jika state tersebut ada, dilanjutkan ke langkah g. g. Tambahkan fungsi transisi ke dalam tabel transisi. 4.2 Form Fungsi Pohon Transisi Form ini menampilkan simulasi proses pembentukan pohon fungsi transisi state yang memiliki transisi atas input firstpos, lastpos dan nullable. Algoritma proses ini adalah sebagai berikut: 1. Mulai dari leaf hingga root 2. Cek apakah node untuk fungsi and or atau fungsi * closure dan + closure. 3. Untuk masing-masing node akan diberi 3 nilai di mana untuk setiap leaf bahwa firstpos dan lastpos dari indeks yang ada pada pohon sedangkan nullable diberi nilai false. 4. Untuk selanjutnya pada proses pemberian nullable dilakukan berdasarkan tabel kebenaran ke dua ruas kanan dan ruas kiri. Dengan cara yang sama sehingga semua posisi node akan mendapatkan nilai nullable 5. Untuk pemberian nilai firstpos dan laspos untuk masing-masing node selain leaf gunakanlah tabel rules untuk nullabel, firstpos dan lastpos. Ulangi dengan cara yang sama sehinga semua node akan terisi nilai firstpos dan lastpos

ISSN : 2301-9425

6. Ambil posisi firstpos pada root untuk dijadikan menjadi set root. 5. Kesimpulan dan Saran. 5.1 Kesimpulan Berdasarkan uraian dari bab I hingga bab IV maka dapat diambil kesimpulan sebagai berikut : 1. Konversi ekspressi reguler menjadi DFA menjadi dasar pembentukan grammar pada bahasa dalam proses kompilasi 2. Konversi ini merupakan dasar analisa sintaksis dan semantik pada proses kompilasi 3. Dapat dijadikan sebagai media pembelajaran 5.2 Saran Demi kesempurnaan paper ini, perlu beberapa saran sebagai berikut : 1. Untuk dikembangkan dalam dalam beberapa bahasa pemrograman yang dinamis 2. Penguraian dalam topik ini masih banyak yang menyertakan teori-teori yang vital. Oleh karena itu untuk para pengembang selanjutnya dapat melengkapinya. Daftar Pustaka 1. Sanjay Bhargava, G.N. Purohit, “Construction of a Minimal Deterministic Finite Automaton from a Regular Expression”, Department Of Computer Science Banasthali unversity, 2011 2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ulman, “Teori Bahasa dan Otomata”, 2nd , Andi Offset, 2007 3. Marco Almeida, Nelma Moreira, Rog´erio Reis,“Exact Generation of Minimal Acyclic Deterministic Finite Automata”, Technical Report Series: DCC-2007-05 Version 1.0 4. Carmen Galvez and Félix MoyaAnegón,“Approximate Personal NameMatching Through Finite-State Graphs”, Department of information Science, University of Granada, Campus Cartuja, Colegio Máximo, 18071, Granada, Spain, 2007 5. Paritosh K. Pandya , “Finite State Automata Automata: Theory and Practice”, (TIFR, Mumbai, India), Unversity of Trento, 10-24 May 2005 6. H. Aho, Alfred V., Ravi Sethi and Jeffrey D. Ulman, “Compiler : Principle, Techniques and Tools”, Addition-Wesley Publishing Company, (1986) 7. Pittman, Thomas and James Peters, “The Art Compiler Design : Theory and Practice”, Prentice – Hall, (1992) 8. Aho, Alfred V., Ravi Sethi and Jeffrey D. Ulman, “Principles of Compiler Design”, Addison-Wesley, (1977) 9. Sumantri Slamet, Heru Suhartanto, “Teknik Kompilasi”, PT. Elex Media Computindo, 1993.


8

SIMULASI TRANSFORMASI REGULAR EXPRESSION TERHADAP FINITE STATE AUTOMATA

Recommend Documents