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’ → e | eS
E → b
Leave a Reply