Aplikasi Pemanfaatan Context Free Grammar

Context Free Grammar atau yang biasa disingkat CFG merupakan tata bahasa formal di mana setiap aturan produksi adalah dalam bentuk A → B dimana A adalah pemroduksi dan B adalah hasil produksi . Batasannya hanyalah ruas kiri adalah sebuah simbol variabel dan ruas kanan dapat berupa terminal, simbol, variabel ataupun ε. Sehingga, dapat disimpulkan bahwa Context Free Grammar merupakan tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya. Contoh aturan produksi yang termasuk CFG seperti berikut :

1. X → bY | Za
2. Y → aY | b
3. Z → bZ | ε

CFG juga merupakan tata bahasa yang mempunyai tujuan sama seperti tata bahasa reguler yaitu untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

Untuk menggambarkan simbol-simbol variabel menjadi simbol terimnal ialah dengan menggunakan pohon penurunan atau yang biasa disebut dengan derivation tree/parse tree dimana cara ini berarti setiap simbol variabel akan diturunkan menjadi terminal sampai tidak ada yang bisa tergantikan.

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

1. S → aAB
2. A → bBb
3. B → A | λ

Maka, pohon penurunannya seperti ini :

Suatu context-free grammar (CFG) G bersifat ambigu jika sejumlah string w ∈ L(G) berasal dari dua atau lebih pohon turunan. Dengan kata lain, Suatu context-free grammar G bersifat ambigu jika sejumlah string w ∈ L(G) memiliki :

1. Dua atau lebih turunan kiri (leftmost derivation).
2. Dua atau lebih turunan kanan (rightmost derivation).

Keambiguan untuk sebuah bahasa pemrograman merupakan sesuatu yang cukup buruk, oleh karena itu seorang programmer harus dapat menghindari keambiguan.

Penyederhanaan Context Free Grammar

Penyederhanaan tata bahasa bebas konteks dilakukan sebagai pembatasan sehingga nantinya tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi yang tak berarti . contohnya. Terdapat tata bahasa bebas konteks dengan aturan produksi :

1. S → A
2. A → B
3. B → C
4. C → D
5. D → a | A

Dari aturan produksi di atas, path yang dilalui dirasa terlalu panjang, dan D → A menyebabkan kerumitan atau redundant. Dengan begitu hal tersebut perlu disederhanakan. Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan :

1. Penghilangan produksi useless
   Produksi useless didefinisikan sebagai produksi yang memuat variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya. Produksi ini tidak berguna karena bila diturunankan tidak akan pernah selesai (masih ada symbol variabel yang tersisa), sehingga produksi itu berlebihan.
2. Penghilangan produksi unit
   Produksi unit adalah produksi dimana ruas kiri dan ruas kanan aturan produksi hanya berupa satu simbol variabel
3. Penghilangan produksi ε
   Produksi ε adalah produksi dalam bentuk α→ε (nullable). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε.

Aplikasi Context Free Grammar

Terinspirasi dari bahasa natural manusia, ilmuwan-ilmuwan ilmu komputer yang mengembangkan bahasa pemrograman, turut serta memberikan tata bahasa secara formal. Tata bahasa ini diciptakan secara bebas konteks dan disebut CFG (Context Free Grammar). Semula CFG ditemukan untuk membantuk menspesifikasikan bahasa manusia dan ternyata sangat cocok untuk mendefinisikan bahasa komputer, memformulasikan pengertian parsing, menyederhanakan penerjemahan bahasa komputer dan aplikasi-aplikasi pengolahan string lainnya. Context Free Grammar digunakan untuk menspesifikasikan struktur sintaks bahasa pemrograman serta beragam basis data.

CFG juga berupa sekumpulan berhingga variabel yang juga disebut nonterminal atau kategori sintaks, dimana masing-masing merepresentasikan bahasa. Bahasa-bahasa yang direpresentasikan dengan variabel-variabel itu dideskripsikan secara rekursif dalam bentukan lain dan simbol-simbol primitif disebut terminal. Aturan-aturan yang berhubungan dengan variabel-variabel itu disebut produksi.

Contoh penggunaan Context Free Grammar adalah pada dokumen HTML yang selalu menyertakan tag-tag berpasangan secara lengkap. Contoh pada struktur HTML sebagai berikut:

Setiap tag selalu berpasangan dengan tag yang sama namun dengan panembahan "/" di depannya. Pola-pola ini serupa pasangan kurung. Dengan demikian, pengenalan string-string yang termasuk dalam Context Free Grammar (CFG) merupakan salah satu tugas yang dilakukan web browser.