SURIANI D121181316_ Context Free Grammars

 Aplikasi pemanfaatan Context Free Grammars

 

CFG atau Context Free Grammar adalah tata bahasa formal di mana setiap aturan produksi adalah dalam bentuk A → B di mana A adalah pemproduksi, dan B adalah hasil produksi. Batasannya hanyalah ruas kiri adalah sebuah simbol variabel. Dan pada ruas kanan bisa berupa terminal, symbol, variable ataupun ɛ, Contoh aturan produksi yang termasuk CFG adalah seperti berikut ini:

• X → bY | Za
• Y → aY | b
• Z → bZ | ɛ
  

CFG dalam penggunaannya membutuhkan perlakuan seperti penyederhanaan dan perubahan bentuk. CFG sebelum diubah kedalam bentuk normal chomsky harus melalui proses penyederhanaan. proses penyederhanaan CFG ada tiga tahapan yaitu penghilangan produksi unit, useless dan epsilon (produksi kosong). pengguna terkadang menemui beberapa kendala atau kesulitan dalam menentukan hasil penyederhanaan CFG. Banyaknya produksi dan bentuk grammar yang rumit juga mempengaruhi pencarian solusi sehingga langkah yang di perlukan terlalu panjang untuk mencapai hasil penyederhanaan.

Context Free Grammar ( CFG ) menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.

Contoh, terdapat CFG dengan aturan produksi sebagai berikut dengan simbol awal S :

• S → AB
• A → aA | a
• B → bB | b

Maka jika ingin dicari gambar pohon penurunan dengan string : ‘aabbb’ hasilnya adalah seperti di bawah :

 

 

Proses penurunan / parsing bisa dilakukan dengan cara sebagai berikut :

• Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang di perluas terlebih dahulu.
• Penurunan terkanan ( rightmost derivation ) : simbol variabel terkanan yang diperluas terlebih dahulu.

 

Misal : Grammar sbb :

• S → aAS | a
• A → SbA | ba
  

 

Untuk memperoleh string ‘aabbaa’ dari grammar  diatas dilakukan dengan cara :

• Penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa
• Penurunan terkanan : S => aAS => aAa => aSbAa => aAbbaa => aabbaa

Aplikasi segmentasi teks Bahasa Indonesia menggunakan metode Context Free Grammar untuk pencocokan kalimat:

Metode yang digunakan untuk pencocokan kalimat dalam aplikasi ini adalah Context Free Grammar (CFG) yaitu dengan menentukan kalimat yang dicari pembentukannya sesuai grammar yang benar secara struktural maupun dalam maknanya.

Data ujicoba yang diperoleh dari aplikasi segmentasi teks ini diperoleh dari hasil pencocokan kalimat yang telah dibenarkan. Dari hasil pengujian diperoleh presentase hasil dengan aplikasi menggunakan metode context free grammar (CFG) adalah untuk kalimat dasar berpola subjek dan predikat (SP) 90%, untuk kalimat dasar berpola subjek, predikat, dan objek (SPO) 85%, dan untuk kalimat dasar berpola subjek, predikat, objek dan keterangan (SPOK) 85%. Presentase tersebut diperoleh dari kalimat yang pencocokannya benar sesuai program dimana setiap kalimat diinputkan 20 kalimat.

 

 

Referensi: 

http://etheses.uin-malang.ac.id/8061/

https://socs.binus.ac.id/2018/12/20/penyederhanaan-context-free-grammar/