METODE PARSING

Ada 2 metoda parsing : top-down dan bottom-up. 

Parsing top-down	:	Diberikan kalimat x sebagai input. Parsing dimulai dari simbol awal S sampai kalimat x nyata (atau tidak nyata jika kalimat x memang tidak bisa diturunkan dari S) dari pembacaan semua leaf dari pohon parsing jika dibaca dari kiri ke kanan.
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) .

Parsing Top-Down

Ada 2 kelas metoda parsing top-down, yaitu kelas metoda dengan backup dan kelas metoda tanpa backup. Contoh metoda kelas dengan backup adalah metoda Brute-Force, sedangkan contoh metoda kelas tanpa backup adalah metoda recursive descent.

a. 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.

Contoh Soal : 

Diberikan grammar G = {S → aAd|aB,  A → b|c,  B → ccd|ddc}. Gunakan metoda BruteForce untuk melakukan analisis sintaks terhadap kalimat x = accd.

Metoda Brute-Force tidak dapat menggunakan grammar rekursi kiri, yaitu grammar yang mengandung produksi rekursi kiri (left recursion) : A → A∝. Produksi rekursi kiri akan menyebabkan parsing mengalami looping tak hingga.

Contoh Soal : 

Diberikan grammar G = {S → aAc,  A → Abε}. Gunakan metoda Brute-Force untuk melakukan analisis sintaks terhadap kalimat x = ac.

Agar tidak menghasilkan looping tak hingga, grammar rekursi kiri harus ditransformasi.

Untuk contoh di atas transformasi berarti merubah produksi A → Ab menjadi A → bA.

b. Metoda Recursive-Descent

Recursive Descent Parser adalah salah satu cara mengaplikasikan bahasa bebas konteks untuk melakukan analisa sintaksis suatu source code. Ciri dari recursive descent parser yang menonjol adalah secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur (no backtrack).

Berbeda dengan mesin turing yang dapat maju dan mundur dalam melakukan parsing. Ciri lain dari recursive descent parser adalah sangat bergantung pada algoritma scan dalam mengambil token.

Syarat grammar yang dapat di-parse dengan RDP adalah :

• Context free grammar
• Tidak memiliki left recursion
• Menerapkan alternative aturan produksi yang terpanjang (bila terdapat dari satu alternative aturan produksi)

Kelemahan RDP:

• Mereka tidak secepat beberapa metode lain
• Sulit untuk memberikan pesan kesalahan yang baik
• Mereka tidak dapat melakukan parsing yang membutuhkan sembarangan  lookaheads panjang

Kelebihan RDP:

• Mereka sangat sederhana
• Mereka dapat dibangun dari recognizers hanya dengan melakukan beberapa tambahan pekerjaan-spesifik, membangun pohon parse

naah, sekarang kita coba mecahin kasus RDP......

Langkah RDP:

1. Jika produksi A mempunyai dua buah ruas kanan atau lebih maka produksi yang dipilih untuk digunakan adalah produksi dengan symbol pertama ruas kanannya sama dengan input yang sedang dibaca. Jika tidak ada produksi yang demikian maka dikatakan bahwa parsing tidak dapat dilakukan.
2. 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.

Soal 1:

Grammar G={S → aB | A, A → a, B → b | d}. Gunakan metode Recursive Descent Parsing untuk melakukan analisis sintaks terhadap kalimat x = ac!

Soal 2:

Grammar G={S → bA | c, A → dSd | e}. Gunakan metode Recursive Descent Parsing untuk melakukan analisis sintaks terhadap kalimat x = bdcd.

Parsing Bottom-Up 

Salah satu contoh menarik dari parsing bottom-up adalah parsing pada grammar preseden sederhana (GPS). Sebelum sampai ke parsing tersebut, akan dikemukakan beberapa pengertian dasar serta relasi yang ada pada GPS.

Pengertian Dasar

•      Jika α dan x keduanya diderivasi dari simbol awal grammar tertentu, maka α disebut sentensial jika α ∈ (V T VN)*, dan x disebut kalimat jika x ∈ (V T)*

•      Misalkan α = Q1β Q2  adalah sentensial dan A ∈ VN :

-  β adalah frase dari sentensial α jika : S ⇒ … ⇒ Q1A Q 2 dan A⇒ … ⇒ β

-  β adalah simple frase dari sentensial α jika : S ⇒ … ⇒ Q1A Q 2 dan A⇒ β

-  Simple frase terkiri dinamakan handel

-  frase, simple frase, dan handel adalah string dengan panjang 0 atau lebih..

Contoh Soal : 

(1)    I ⇒ I H       Hb adalah sentensial dan b adalah simple frase 

⇒ H H     (dibandingkan dengan Q1β Q2 maka Q1= H, β = b, dan Q 2 = ε)

⇒ 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 Q1β Q2 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.

Relasi Preseden dan Grammar Preseden Sederhana

•      Relasi preseden adalah relasi antara 2 simbol grammar (baik V T maupun  VN) dimana paling tidak salah satu simbol tersebut adalah komponen handel.

•      Misalkan S dan R adalah 2 simbol. Ada 3 relasi preseden yang : ←, ↔, dan →

 Perhatikan : komponen handel selalu ‘menunjuk’ yang simbol lainnya.

Contoh Soal :  

Diketahui grammar dengan G = {Z → bMb, M → (L a, L → Ma)}. Dari 3 sentensial : bab, b(Lb, b(Ma)b, tentukan handel dan relasi yang ada.

 •      Secara umum : jika A → aBc adalah sebuah produksi maka :

-  aBc adalah handel dari sentensial yang mengandung string “aBc”

-  relasi preseden antara a, B, dan c adalah : a ↔ B, B ↔ c

•      Dengan memperhatikan ruas kanan produksi yang ada serta berbagai sentensial yang dapat diderivasi dari Z maka semua relasi preseden tercantum dalam tabel berikut :

 Grammar G disebut grammar preseden sederhana, jika :

1.  paling banyak terdapat satu relasi antara setiap dua simbolnya

2.  tidak terdapat dua produksi produksi dengan ruas kanan yang sama

Parsing Grammar Preseden Sederhana Prosedur parsing :

1.   Buat tabel 3 kolom dengan label : sentensial dan relasi, handel, dan ruas kiri produksi.

2.   Tuliskan kalimat (atau sentensial) yang diselidiki pada baris pertama kolom pertama. 

3.   Dengan menggunakan tabel relasi preseden cantumkan relasi preseden antara setiap dua simbol yang bertetangga.

4.   Tentukan handel dari sentensial tersebut. Handel adalah string yang dibatasi “←“ terakhir dan “→ “ pertama jika dilakukan penelusuran dari kiri atau yang saling mempunyai relasi “↔“. Handel tersebut pastilah merupakan ruas kanan produksi, karena

itu tentukan ruas kiri dari handel tersebut.

5.   Ganti handel dengan ruas kiri produksinya. GOTO 3.

6.   Kalimat yang diselidiki adalah benar dapat diderivasi dari simbol awal jika kolom “ruas kiri produksi” menghasilkan simbol awal.