Top-Down Parsing adalah sebuah metode dimana metode ini melakukan penelusuran dari root ke leaf atau dari simbol awal ke terminal.
Metode Top-Down Parsing ini meliputi :
- Backtrack/ Backup : Brute Force
- No Backtrack : Recursive Descent Parser
Di dalam pencarian Top–Down Parsing, terdapat beberapa permasalah yang mungkin akan ditemui :
- Left Recursion
- Left Recursive
Left Recursion
Sebuah grammar dikatakan bersifat left recursion apabila grammartersebut mengandung suatu nonterminal dan derivasinya.
Contoh : A → Aα
Metode Top-Down Parsing tidak bisa menangani grammar yang mengandung left recursive, sehingga left recursive perlu dihilangkan. Di bawah ini akan dijelaskan bagaimana cara menghilangkan left recursive.
Contoh 2 : A → Aα|β
Maka, A → βA’
A’ → αA’ | ε
Mengapa dalam metode Top Down Parsing tidak boleh terdapat left recursive?
Karena left recursive menyebabkan parsing mengalami looping tak hingga.
Left Factoring
Grammar dapat dikatakan left factoring apabila terdapat produksi yang berbentuk seperti di bawah ini :
Contoh 3 :
Grammar tersebut diubah menjadi :
A → αA’
A’ → β1 |β2
Adanya left factoring ini menyebabkan grammar menjadi ambigu karena tidak jelas yang mana dari dua produksi alternatif yang bisa digunakan untuk memperluas nonterminal A. Dari contoh soal di atas, kita tidak tahu mau menelusuri A ke 
atau ke 
.
Demikian penjelasan singkat mengenai Top-Down Parsing 🙂
Recent Comments