CFG adalah singkatan dari tata bahasa bebas konteks. Ini adalah tata bahasa formal yang digunakan untuk menghasilkan semua kemungkinan pola string dalam bahasa formal tertentu.
Context Free Grammar (CFG) digunakan untuk mendeskripsikan bahasa bebas konteks. Tata bahasa bebas konteks adalah sekumpulan aturan rekursif yang digunakan untuk menghasilkan pola string. Tata bahasa tanpa konteks dapat mendeskripsikan semua bahasa reguler dan lainnya, tetapi tidak dapat mendeskripsikan semua kemungkinan bahasa.
Context Free Grammar dipelajari di bidang ilmu komputer teoretis, desain penyusun, dan linguistik. CFG digunakan untuk mendeskripsikan bahasa pemrograman dan program pengurai dalam kompiler dapat dihasilkan secara otomatis dari tata bahasa bebas konteks.
Tata bahasa tanpa konteks memiliki komponen berikut:
- Seperangkat simbol terminal yang merupakan karakter yang muncul dalam bahasa / string yang dihasilkan oleh tata bahasa. Simbol terminal tidak pernah muncul di sisi kiri aturan produksi dan selalu ada di sisi kanan.
- Satu set simbol nonterminal (atau variabel) yang merupakan placeholder untuk pola simbol terminal yang dapat dihasilkan oleh simbol nonterminal. Ini adalah simbol yang akan selalu muncul di sisi kiri aturan produksi, meskipun mereka dapat dimasukkan di sisi kanan. String yang dihasilkan CFG hanya akan berisi simbol dari kumpulan simbol nonterminal.
- Seperangkat aturan produksi yang merupakan aturan untuk mengganti simbol nonterminal. Aturan produksi memiliki bentuk sebagai berikut: variabel \ rightarrow → string variabel dan terminal.
- Simbol awal yang merupakan simbol nonterminal khusus yang muncul di string awal yang dihasilkan oleh tata bahasa.
Bentuk umum produksi CFG adalah :
Analisis sintaks adalah penelusuran sebuah kalimat (atau sentensial) sampai pada simbol awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing. Penelusuran melalui parsing menghasilkan pohon sintaks.
Secara formal, CFG didefinisikan CFG G = (V,T,P,S) dimana V adalah daftar variabel produksi, T adalah daftar simbol atau terminal yang dipakai dalam CFG, P adalah aturan produksi CFG, S adalah variabel start aturan produksi CFG dapat ‘dinormalkan’dengan pola tersendiri supaya tidak ambigu dan lebih sederhana, meskipun normalisasiCFG kadang membuat aturan produksi menjadi lebih banyak dari sebelumnya. Tekniknormalisasi yang digunakan dalam makalah ini adalah CNF (Chomsky Normal Form)
Contoh desain CNF dari bahasa CFG, semisal CFG berikut:
S -> aA | bB (1)
A-> Baa|ba
B -> bAA|ab
CFG (1) tersebut ekivalen dengan CFG dibawah ini,dimana symbol terminal memiliki variabel produksi tersendiri:
S -> DA | EB (2)
A -> BDD | ED
B -> EAA | DE
D -> a
E -> b
CNF yang dihasilkan dari CFG (2) diatas ialah:
S -> DA | EB (3)
A -> BF | ED
B -> EH | DE
F -> DD
H -> AA
D -> a
E -> b
Contoh Pengaplikasian Context Free Grammar
- JAVA
- C++
referensi