Context Free Grammar (CFG)

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:

• α → V
• β → (V + T)*

CFG perlu untuk disederhanakan dengan supaya tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.

Contoh Penyederhanaan CFG

Misalnya ada Context Free Grammar (CFG) dengan aturan produksi sebagai berikut:

• S ➝ AA | C | bd
• A ➝ Bb | ε
• B ➝ AB | d
• C ➝ de
• D ➝ ε

Catatan: \” | \” dibaca atau.

Untuk menyederhanakan aturan produksi Context Free Grammar (CFG) di atas, dilakaukan 3 langkah secara berurutan

• Penghilangan produksi ε.
• Penghilangan produksi unit.
• Penghilangan produksi useless.

1. Penghilangan produksi ε pada Context Free Grammar

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.

Penghilangan

• S ➝ AA | C | bd
• A ➝ Bb | ε
• B ➝ AB | d
• C ➝ de
• D ➝ ε

D nullable serta D ➝ ε satu-satunya produksi dari D, maka variabel D bisa ditiadakan.

Penggantian

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

• S ➝ A | AA | C | bd
• A ➝ Bb
• B ➝ B | AB | d
• C ➝ de

2. Penghilangan produksi unit pada Context Free Grammar

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:

• S ➝ A | AA | C | bd
• A ➝ Bb
• B ➝ B | AB | d
• C ➝ de

Penghilangan

Penghilangan produksi unit dimulai dari bawah. Oleh karena itu, B ➝ B dihilangkan karena rekrusif (berulang).

Penggantian

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

• S ➝ Bb | AA | de | bd
• A ➝ Bb
• B ➝ AB | d
• C ➝ de

3. Penghilangan produksi useless pada Context Free Grammar

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).

• S ➝ Bb | AA | de | bd
• A ➝ Bb
• B ➝ AB | d
• C ➝ de

Karena tidak ada aturan produksi yang mengarah ke produksi C maka C dihilangkan.

Setelah selesai dilakukan penghilangan dan penggantian maka hasil akhirnya adalah

• S ➝ Bb | AA | de | bd
• A ➝ Bb
• B ➝ AB | d

Kesimpulan

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:

• S ➝ AA | C | bd
• A ➝ Bb | ε
• B ➝ AB | d
• C ➝ de
• D ➝ ε

Aturan produksi setelah disederhanakan:

• S ➝ Bb | AA | de | bd
• A ➝ Bb
• B ➝ AB | d

Referensi

• Wikipedia

Materi-materi yang Masih Berkaitan

• Membuat Pohon Penurunan dari CFG

Materi Induk

• Teknik Informatika
• Teori Bahasa dan Otomata