Pertanyaan :
Mengapa harus menghilangkan left recursive dan left factoring dalam melakukan top-down parsing?
Jawaban :
a) Karena top-down parser tidak dapat menangani left-recursive grammars, hal ini dikarenakan left-recursive grammars dapat membawa parser menuju non-terminal, singkatnya parser tidak dapat menemukan ujung dari variable karena terus menelusuri rekursi.
Untuk semua rekursi yang ada harus rekursi yang benar yaitu tidak menghasilkan left-recursion, sehingga dapat mencegah terjadinya infinite-recursive. Selain itu, pembuangan left-recursive juga berguna untuk mengurangi kemungkinan untuk terjadinya backtracking.
b) Pembuangan left factoring diharuskan untuk menghilangkan ambiguitas pada saat parser, untuk lebih jelasnya mari kita lihat gambar dibawah ini.
Dengan melakukan left factoring maka parser dapat menentukan pilihan yang benar tanpa membuang-buang langkah untuk melakukan cek dan backtracking.
Source :
http://www.computing.dcu.ie/~davids/courses/CA448/CA448_Top_Down_Parsing_2p.pdf
https://www.cs.umd.edu/class/spring2009/cmsc430/lectures/lec05.pdf
