feegikvalencia

Top Down Parsing dapat dipandang sebagai :

• Usaha untuk mencari left-most derivation dari suatu input string
• Usaha untuk membangun parse tree dari suatu input string, dimulai dari root (top) sampai dengan leaves (bottom), dengan urutan pre-order.

Mengapa di dalam top–down parsing tidak boleh ada left–factoring atau left–recursive?

Di dalam top-down parsing tidak boleh ada left-recursive karena grammar yang mengandung left-recursive dapat mengakibatkan loop tak berhingga. Selain itu, suatu top-down parsing yang memerlukan backtracking (membaca input berulang kali) itu tidak efisien.

Contoh grammar yang memiliki loop tak berhingga:

Sedangkan adanya left–factoring pada top-down parsing akan menimbulkan ambiguitas. Ambiguitas terjadi  ketika dua aturan untuk non-terminal memiliki sisi kanan yang dimulai dengan simbol yang sama, sehingga kita tidak bisa memprediksi grammar mana yang akan digunakan.

Contoh grammar yang bersifat ambigu:

Misalnya :

Grammar :

S ->iEtS | iEtSeS | a

E ->b

Dituliskan menjadi :

S ->iEtSS’ | a

S’->  ε | eS

E -> b

www.binus.ac.id