Archive for March 11th, 2014
Top-Down Parsing
Top-down parsing merupakan sebuah strategi untuk menganalisis data dari hipotesa umum struktur parse tree dan kemudian mempertimbangkan apakah struktur-struktur fundamental yang dikenal kompatibel dengan hipotesis. Contoh jenis parser yang menggunakan strategi parsing top-down adalah parser LL.
Mengapa Top – Down Parsing harus menghilangkan left-recursion & left-factoring?
Karena jika terdapat left-recursion dan left-factoring, akan terjadi ambiguitas pada saat top-down parser mencoba untuk mengurai input yang ambigu terhadap sebuah CFG dan juga memuungkinkan terjadinya looping terus menerus. Hal itu mungkin memerlukan beberapa langkah eksponensial untuk mencoba semua alternatif dari CFG untuk menghasilkan semua kemungkinan parse tree,, yang pada akhirnya akan membutuhkan ruang memori eksponensial (kompleksitas ruang bertambah). Dengan adanya ambiguitas, maka waktu pemrosesan menjadi lebih lama sehingga akan memunculkan masalah kompleksitas waktu.