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
Kelompok 10 :
Vebyana- 1501148122
Feegi Kasah Valencia-1501142314
Herlina Astari -1501155506
Sarah Fitria – 1501152870
Haris Winoto – 1501188611