Teknik Kompilasi - Metode Recursive-Descent

Apa itu Recursive Descent Parsing ??

RDP itu salah satu bentuk parsing yang masuk dalam 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:

Gambar 1. Contoh bentuk Parsing Tree

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 aturan alternatif produksi yang terpanjang (bila terdapat dari satu aturan alternatif 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

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.

Contoh Soal :

Contoh 1.

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