Metode Parsing Top Down Brute-Force & Recursive-Descent

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

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

untuk lebih dimengerti kita lihat contoh aja ya.......

1.PARSING Down  Metode Brute-Force

Gunakan metode Brute Force untuk melakukan analisa terhadap kalimat

X = edok

      a. Penyelesaian pertama

      

•        Menggunakan Parse Tree

•        Menggunakan Derivasi

Maka tidak berhasil  menyelesaikan kalimat dengan Ook

 b.Penyelesaian kedua

•      Menggunakan Parse Tree

• Menggunakan Derivasi

Maka berhasil  menyelesaikan kalimat dengan OK

2. PARSING Down  Metode Recursive-Descent

Gunakan metode recursive descent untuk melakukan analisis sintak terhadap kalimat  X = amsal

 Penyelesaiannyaa...

•             Menggunakan Parse Tree

•        Menggunakan Derivasi

Maka Parsing Gagal  hal ini karena S tidak mengandung sal melainkan sol dan tol