CFG (Context Free Gammar )

Definisi

: 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 normalisasi

CFG kadang membuat aturan produksi menjadi lebih banyak dari sebelumnya. Teknik

normalisasi yang digunakan dalam makalah ini adalah CNF (Chomsky Normal Form).

Contoh desain CNF dari bahasa CFG, semisal CFGberikut:

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

Setelah terbentuk CFG yang telah dinormalkan secara CNF, dalam implementasi

parsing, terdapat algoritma yang berguna untuk menentukan apakah suatu untai ‘valid’,

atau dapat diciptakan dari aturan-aturan CFG yang ada. Salah satu algoritma yang dapat dipakai adalah Algoritma Cocke-Younger-Kasami (CYK). Algoritma ini menyelesaikan masalah analisa kembali sebuah sub-untai yang sama karena seharusnya analisa sub-untai independen terhadap parsing sub-untai yang diparsing setelahnya. Dengan Program Dinamis, independensi yang diinginkan dapat dicapai ketika parsing. Algoritma CYK termasuk dalam bidang Program Dinamis karena algoritma ini membangun tabel status dua dimensi ketika parsing dimana penentuan parsing selanjutnya diturunkan atau dihasilkan dari parsing sebelumnya, hingga akhir untai. Selain untuk mengetahui validitas untai dalam suatu CFG, algoritma CYK yang dimodifikasi dapat dipergunakan pula untuk membangun pohon parsing.

Diketahui grammar

 


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)

                                                    

Ambiguitas

Adalah sebuah kalimat yang mempunyai lebih dari satu pohon sintak dan grammar yang menghasilkan paling sedikit sebuah kalimat ambigu disebut

grammar ambigu.

grammar

Kalimat : 2*3+7 mempunyai dua pohon sintaks berikut