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 :

1. Backtrack/ Backup           : Brute Force
2. No Backtrack                : Recursive Descent Parser

Di dalam pencarian Top–Down Parsing, terdapat beberapa permasalah yang mungkin akan ditemui :

1. Left Recursion
2. Left Recursive

Left Recursion

Sebuah grammar dikatakan bersifat left recursion apabila grammar tersebut 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 :

A → αβ₁ | αβ₂

Grammar tersebut diubah menjadi :

A → αA’

A’ → β₁ |β₂

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 αβ_2.

Demikian penjelasan singkat mengenai Top-Down Parsing, good luck! 😀

http://binus.ac.id