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


No comments:

Post a Comment