December 22, 2021
Context Free Grammar (CFG) atau Tata Bahasa Bebas Konteks adalah salah satu tata bahasa formal yang digunakan untuk spesifikasi sturuktur sintaks bahasa pemrograman serta basis beragam skemas spesifikasi translasi.
CFG menghasilkan bahasa yang dikenal oleh Non-Deterministic Push Down Automata.
Aturan produksi pada CFG, yaitu simbol sisi kiri hanya boleh memiliki 1 variabel non terminal (variabel) dan sisi kanan tidak memiliki batasan (bisa berisi ɛ, simbol terminal, simbol variabel, atau kombinasi ketiganya). Jika kita tuliskan maka aturan produksi dari Context Free Grammar adalah sebagai berikut:
CFG perlu untuk disederhanakan dengan supaya tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Misalnya ada Context Free Grammar (CFG) dengan aturan produksi sebagai berikut:
Catatan: \” | \” dibaca atau.
Untuk menyederhanakan aturan produksi Context Free Grammar (CFG) di atas, dilakaukan 3 langkah secara berurutan
Produksi ε adalah produksi dalam bentuk: α ➝ ε
Atau bisa dianggap sebagai produksi kosong (empty). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable.
D nullable serta D ➝ ε satu-satunya produksi dari D, maka variabel D bisa ditiadakan.
Namun, bila kasusnya A ➝ Bb | ε
A nullable, tapi A➝ ε bukan satu-satunya produksi dari A sehingga setelah dilakukan penghilangan, selanjutnya perlu diberlakukan penggantian supaya tidak merusak aturan produksi yang telah dibentuk.
Kita lihat kembali, produksi A juga digunakan dalam S ➝ AA dan B ➝ AB
Karena A sekarang ini tak utuh maka ada kemungkinan A juga hilang setelah ε dihilangakan.
Pada S ➝ AA ada kemungkinan A hilang maka dihasilkan S ➝ A | AA
Pada B ➝ AB ada kemungkinan A hilang maka dihasilkan B ➝ B | AB
Setelah selesai dilakukan penghilangan dan penggantian maka hasil akhirnya adalah
Produksi unit adalah produksi di mana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel.
Keberadaan produksi unit membuat tata bahasa memiliki kerumitan yang tak perlu.
Sebagai contoh:
Penghilangan produksi unit dimulai dari bawah. Oleh karena itu, B ➝ B dihilangkan karena rekrusif (berulang).
Karena S ➝ A | C yang mana A dan C juga memiliki aturan produksi maka A dan C pada S ➝ A | C diganti menjadi Bb dan de.
Setelah selesai dilakukan penghilangan dan penggantian maka hasil akhirnya adalah
Produksi useless didefinisikan sebagai produksi yang memuat symbol variabel yang tidak memiliki
penurunan yang akan menghasilkan terminal-terminal seluruhnya.
Produksi uselsess tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan (berlebih).
Karena tidak ada aturan produksi yang mengarah ke produksi C maka C dihilangkan.
Setelah selesai dilakukan penghilangan dan penggantian maka hasil akhirnya adalah
Begitulah cara menyederhanakan aturan produksi Context Free Grammar (CFG) atau Tata Bahasa Bebas Konteks, setelah melalui penghilangan produksi ε, penghilangan produksi unit dan penghilangan produksi useless.
Aturan produksi sebelum disederahanakan:
Aturan produksi setelah disederhanakan:
Materi-materi yang Masih Berkaitan
Materi Induk
![\"Cara](\"https://ziakode.com/wp-content/uploads/2021/12/Cara-Menyederhanakan-CFG-1.png\")
