CFG ( Context Free Grammar )
CFG / Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :
a → b
batasannya hanyalah ruas kiri (a) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :
B → CDeFg
D → BcDe
Tata bahasa bebas konteks ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

PARSING
CFG menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.
Contoh, terdapat CFG dengan aturan produksi sebagai berikut dengan simbol awal S :
S → AB
A → aA | a
B → bB | b
Maka jika kita ingin mencari gambar pohon penurunan dengan untai : ‘aabbb’ hasilnya adalah seperti di bawah :
A

A A

a A b B
|
a b B
|
b

Proses penurunan / parsing bisa dilakukan dengan cara sebagai berikut :
 Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang di perluas terlebih dahulu.
 Penurunan terkanan ( rightmost derivation ) : simbol variabel terkanan yang diperluas terlebih dahulu.
Misal : Tata bahasa sbb :
S → aAS | a
A → SbA | ba
Untuk memperoleh untai ‘aabbaa’ dari tata bahasa diatas dilakukan dengan cara :
• Penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa
• Penurunan terkanan : S => aAS => aAa => aSbAa => aAbbaa => aabbaa

AMBIGUITAS
Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai.
Misalkan terdapat tata bahasa sebagai berikut :
S → A | B
A → a
B → a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :
• S => A => a
• S => B => a

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS ( CFG )
Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi tak berarti.
Missal :
S → AB | a
A → a
Kelemahanya adalah aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan.
Penyederhanaan tata bahasa bebas konteks dapat di lakukan dengan 3 cara :
1. Penghilangan produksi useless
2. Penghilangan produksi unit
3. Penghilangan produksi Є

1. Penghilangan Produksi Useless
Definisi sbb:
• Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal sehingga produksi itu redundan.
Contoh :
S → aSa | Abd | Bde
A → Ada
B → BBB |a

 Langkah penyederhanaannya :
• Hilangkan aturan yang tidak menuju terminal.
• Hapus anggota S yang mengandung simbol himpunan ke terminal yang tidak berguna
• Hilangkan Redundan ( Anggota yang tidak ada di S dan Sebaliknya )

 Maka, hasil penyederhanaanya adalah sbb :
S → aSa | Bde
B → BBB | a
Contoh lain :
S → Aa | B
A → ab | D
B → b | E
C → bb
E → aEa
Produksi yang useless adalah :
A → D
C → bb
E → aEa
B → E
Hasil akhir dari penyederhanaanya adalah :
S → Aa | B
A → ab
B → b

2. Penghilangan Produksi Unit
Definifi produksi unit adalah produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan : A → B, C → D. Keberadaanya membuat tata bahasa memiliki kerumitan yang tak perlu, maka bisa dihilangkan.

Langkah penyederhanaanya :
• Jabarkan masing-masing himpunan
• Sederhanakan ruas kiri dan kanan yang hanya berupa variabel simbol sama
• Hapus simbol variabel yang tidak berguna / tidak mempunyai turunan
Contoh suatu CFG sbb :
S → Sb
S → C
C → D
C → ef
D → dd
Jabarkan penurunan masing – masing himpunan :
C → D => C → dd
S → C => S → dd | ef

Maka hasilnya adalah sbb :
S → Sb
S → dd | ef
C → dd
C → ef
D → dd

3. Penghilangan Produksi Empty ( Є )
Definisi produksi empty adalah produksi kosong, (dengan bentuk α → Є) penghilangan dapat dilakukan dengan penggantian produksi yang memuat variabel yang menuju ke Є.

Langkah Penyederhanaannya :
• Hilangkan simbol yang terdapat empty ( Є ) dalam himpunan produksi
• Simbol variabel tidak di hapus jika terdapat cabang terminal / variabel yang saling berhubungan
• Buat himpunan dengan simbol yang dihilangkan dan yang tidak
Contoh :
S → bcAd
A → e
Maka variabel A bisa di hilangkan, sehingga menjadi :
S → bcd
 Kasus lain :
S → bcAd
A → bd | Є
 Maka hasilnya akan menjadi :
S → bcAd | bcd
A → bd
Karena A → Є bukan satu-satunya produksi dari A

CONTEXT-FREE GRAMMAR (CFG) DAN PARSING
Bentuk umum produksi CFG adalah :
a ® b, a Î V, b Î (V½V)*
Analisis sintaks :
Penelusuran sebuah kalimat (sentensial) sampai pada simbol awal grammar. Analisis sintaks dapat dilakukan melalui derivasi atau parsing. Penelusuran melalui parsing menghasilkan pohon sintaks.
Contoh :
Diketahui grammar G = {I ® H½I H½IA, H ® a½b½c½…½z, A ® 0½1½2½…½9}
dengan I adalah simbol awal.
Berikut ini kedua cara analisa sintaks untuk kalimat x23b.
cara 1 (derivasi)
I Þ IH
Þ IAH
Þ IAAH
Þ HAAH
Þ xAAH
Þ x2AH
Þ x23H
Þ x23b
cara 2 (parsing)
I

I H
|
I A b
|
I A 3
| |
H 2
|
X

Contoh :
Diketahui grammar G = {S ® SOS½A , O ® *½+, A ® 0½1½2½…½9}
Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut :

S S
| |
S O S S O S
| | | | | |
A * S O S S O S + A
| | | | | | | |
2 A + A A * A 7
| | | |
3 7 2 3

Sebuah kalimat yang mempunyai lebih dari satu pohon sintaks disebut kalimat ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut grammar ambigu.

Metoda Parsing
Ada 2 metoda parsing : top-down dan bottom-up.
 Parsing top-down :
Parsing dimulai dari simbol awal S sampai kalimat x
 Parsing bottom-up :
Parsing dimulai dari kalimat x sampai simbol awal S

Parsing Top-down
 Ada 2 kelas metoda parsing top-down :
1. kelas metoda dengan backup,
Contoh: metoda Brute-Force
2. kelas metoda tanpa backup
Contoh: metoda recursive descent.
 Metoda Brute-Force
Kelas metoda dengan backup, termasuk metoda Brute-Force, adalah kelas metoda parsing yang menggunakan produksi alternatif, jika ada, ketika hasil penggunaan sebuah produksi tidak sesuai dengan simbol input. Penggunaan produksi sesuai dengan nomor urut produksi.
 Metoda Recursive-Descent
 Kelas metoda tanpa backup, termasuk metoda recursive descent, adalah kelas metoda parsing yang tidak menggunakan produksi alternatif ketika hasil akibat penggunaan sebuah produksi tidak sesuai dengan simbol input. Jika produksi A mempunyai dua buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah produksi dengan simbol pertama ruas kanannya sama dengan input yang sedang dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak dapat dilakukan.
 Ketentuan produksi yang digunakan metoda recursive descent adalah : Jika terdapat dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari semua ruas kanan produksi tersebut tidak boleh sama. Ketentuan ini tidak melarang adanya produksi yang bersifat rekursi kiri.

Parsing Bottom-Up
 Salah satunya adalah grammar preseden sederhana (GPS).
 Pengertian Dasar
 Jika a dan x keduanya diderivasi dari simbol awal grammar tertentu, maka a disebut sentensial jika a Î (V½ V)*, dan x disebut kalimat jika x Î (V)*
 Misalkan a = Q1b Q2 adalah sentensial dan A Î VN :
– b adalah frase dari sentensial a jika : S Þ ¼ Þ Q1 a Q2 dan a Þ ¼ Þ b
– b adalah simple frase dari sentensial a jika : S Þ ¼ Þ Q1 a Q2 dan a Þ b
– Simple frase terkiri dinamakan handel
– frase, simple frase, dan handel adalah string dengan panjang ≥ 0

Contoh:
(1) I ⇒ I H Hb adalah sentensial dan b adalah simple frase
⇒ H H (dibandingkan dengan Q1 β Q 2 maka Q1 = H, β = b, dan Q2 = ε)
⇒ H b Perhatikan : simple frase (b) adalah yang terakhir diturunkan
(2) I ⇒ I H Hb adalah sentensial dan H adalah simple frase
⇒ I b (dibandingkan dengan Q 1 β Q 2 maka Q1 = ε, β = H, dan Q 2 = b)
⇒ H b Perhatikan : simple frase (H) adalah yang terakhir diturunkan
Sentensial Hb mempunyai dua simple frase (b dan H), sedangkan handelnya adalah H.