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

Pohon Penurunan

Pohon Penurunan berguna untuk menggambarkan bagaimana memperoleh suatu string/untai dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal.

Untuk membuat pohon penurunan yang sempurna, kita harus menurunkan setiap simbol variabel yang ada menjadi simbol terminal.

Contoh:

• S → AB (kita baca S menghasilkan AB).
• A → aA | a (kita baca A menghasilkan aA atau a).
• B → bB | b (kita bacaB menghasilkan bB atau b).

S merupakan simbol awal.

Bagaimana pohon penurunan untuk mendapatkan untai \’aabbb\’?

Langkah Pertama

Kita turunkan simbol S sebagai simbol awal sesuai dengan turunannya, yaitu menjadi AB .

Langkah Kedua

Kita harus mencari dua simbol a terminal (aa). Untuk mencarinya variabel A harus kita turunkan karena variabel A memiliki dua turunan, yaitu aA dan a maka kita harus memilih turunan aA supaya kita dapat mencari simbol terminal a kedua.

Langkah Ketiga

Setelah kita berhasil menurunkan satu simbol terminal a, selanjutnya variabel A yang tersisa kita turunkan menjadi terminal a supaya pencarian tidak mengalami perulangan.

Langkah Keempat

Setelah dua simbol terminal a (aa) sudah kita temukan, langkah selanjutnya adalah mencari tiga simbol terminal b (bbb). Maka seperti mencari variabel A tadi, variabel B harus kita turunkan menjadi bB.

Langkah Kelima

Karena masih tersisa dua simbol terminal b yang harus kita cari, maka variabel B harus kita turunkan kembali menjadi bB.

Langkah Keenam

Terakhir, setelah dua simbol terminal b kita temukan, maka langkah terakhir adalah menurunkan variabel B menjadi terminal b.

Referensi

• Wikipedia

Materi-materi yang Masih Berkaitan

• Menyederhanakan CFG
• Menggunakan Algoritma CYK untuk Membuktikan CFG

Materi Induk

• Teknik Informatika
• Teori Bahasa dan Otomata