Recursive Descent Parsing

*bingung mau make icon apa buat RDP, alhasil gambar diatas deeh!! ^^v (gak penting juga sebenernya -,-)

mau nge share aja tentang RDP alias ~~Recursive Dewi Pertiwi~~, eeh salah! Recursive Descent Parsing, hehehehe ^^v mulaaii yuukk.....

apa ayooo Recursive Descent Parsing??

RDP itu salah satu bentuk parsing yang masuk dalem Top Down Parsing. dimana kita melakukan parsing secara menurun dari atas ke bawah. Parsing sendiri itu sebuah proses penentuan apakah sebuah string dari token dapat dihasilkan oleh sebuah grammar. dalam melakukan Parsing, kita menggunakan Parsing Tree seperti di bawah ini:

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:

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