teko kenapa top down parser tidak bisa menghandle left factoring dan left recursive

Kenapa harus menghilangkan Left Recursive dan Left Factoring dalam Top Down Parsing?

Left Factoring

Left Factoring yaitu dalam sebuah aturan produksi yang memiliki ruas kiri yang sama tidak boleh ada alternatif penurunan (ruas kanan) yang diawali simbol yang sama.

contoh :

A -> αβ1 | αβ2

kita tidak tahu mau menelusuri ke αβ1 atau αβ2

tidak jelas yang mana dari 2 produksi alternatif untuk digunakan untuk menjelajah dari nonterminal A. Karena tidak jelas, maka peraturan tidak bisa di-aplikasikan

Left Recursive

katakanlah kita punya
A -> Aa | b

Saat kita menjelajah A, kita harus pergi menelusuri A, tapi untuk melakukan itu, kita harus menjelajahi A lagi, dan untuk itu kita harus menjelajahi A lagi, dan akhirnya mengulang hingga tak terhingga.
Jadi, pada akhirnya A tidak akan ketemu, infinite looping.

Kebanyakan top-down parser tidak men-support left recursive,
walaupun beberapa teknik rumit top-down bisa menghandle left recursive. Teknik rumit dimana top-down parser bisa menghandle left-recursive bisa ditemukan pada contoh di buku-buku di bawah ini:
[1]: Richard A. Frost and Rahmatullah Haﬁz. A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time. SIGPLAN Notices, 41(5):46–54, 2006.
[2]: R. Frost, R. Haﬁz, and P. Callaghan, Modular and efﬁcient top-down parsing for ambiguous left-recursive grammars. ACL-IWPT, pp. 109 – 120, 2007.

Sumber :

http://www.slideshare.net/hussiensharaf/cs419-lec10-left-recursion-and-left-factoring-31452912

http://stackoverflow.com/questions/22130878/why-top-down-parser-cannot-handle-left-recursion

http://elib.unikom.ac.id/files/disk1/536/jbptunikompp-gdl-arifanihel-26787-7-unikom_a-i.pdf

Backlink : www.binus.ac.id