METODE PADA PARSING

METODE PARSING

ada dua metode parsing yaitu :

• Parsing Top-down 

diberikan kalimat X sebagai input, parsing dimulai dari simbol awal S samapi kalimat X nyata (atau tidak nyata jika kalimay X memang tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan.

ada dua kelas metode parsing top-down, yaitu :

METODE BRUTE-FORCE (backup)
merupakan kelas metode parsing yang menggunakan produksi alternatif (jika ada), ketika hasil penggunaan sebuah produksi tidak sesuai dengan simbol input. penggunaan produksi sesuai dengan nomor urut produksi. 
Contoh :
diberikan Grammar G={ S -> mMp | mN, M->n|o, N-> oop | mpo}
x= moop

METODE RECURSIVE-DESCENT (tanpa Backup)

Merupakan kelas metode 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 metode recursive descent adalah : jika terdapat dua atulebih 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 rekursif kiri.

Contoh :
jika terdapat dua atau lebih produksi dengan ruas kiri yang sama maka karakter pertama dari semua ruas kanan produksi tidak boleh sama. ketentuan ini tidak melarang adanya produksi yang bersifat rekursif kiri. 

Diketahui Grammar G={ S -> kJ | l,J -> mSm | n}. gunakan metode recursive descent parsing untuk melakukan analisis sintaks  terhadap kalimat x=kmlm

1.

 2. 

 3.

 4. 

• Parsing Bottom-up

diberikan kalimat X sebagai input. parsing dimulai dari kalimat X yang nyata dari pembacaan semua leaf pohon parsing dari kiri ke kanan sampai tiba di simbol awal S (atau tidak sampai di S jika kalimat X memang tidak bisa diturunkan dari S). 

GRAMMAR PRESEDEN SEDERHANA (GPS)

Pengertian dasar:

Jika α dan x keduanya diderivasi dari simbol awal grammar tertentu, maka α disebut sentesial jika α ϵ (V^T)^*

Misalkan α = Q₁ β Q₂ adalah sentesial dari A ϵ V^N             

Dimana :

β  adalah frase dari sentesial α jika : S =>....=> Q₁ α Q₂ dan α =>...=> β  

β adalah simple frase dari sentesial α jika : S =>....=> Q₁ α Q₂ dan α => β

simple frase terkiri dinamakan handel

frase, simple frase, dan handel adalah string dengan panjang ≥ 0

 

Contoh :
Diketahui Grammar G={P -> rSr, S -> (T|q, T->Sq)}.
Dari tiga sentensial : rqr, r(Tr, r(Sq)r, tentukanlah handel dan relasi yang ada !