Kelompok 6
1501150303 – Alfon Lavinski
1501143191 – Ricky Santoso
1501183996 – Putu Ayu Zaskya Shavitri
1501153072 – Michael Alfred Wilson
Dalam pengerjaan top-down parsing kita perlu melakukan eliminasi left recursive dan left-factoring. Namun, pernakah terlintas dalam pikiran teman-teman, untuk apa eliminasi ini penting dilakukan?
Dalam artikel kali ini kami akan mencoba menjelaskan mengapa penting untuk melakukan eliminasi tersebut.
Eliminasi left-recursive
Kita harus melakukan eliminasi left-recursive karena metode top-down parsing tidak dapat menangani left-recursive grammar yang menyebabkan terjadinya infinite loop.
Infinite loop terjadi akibat hasil produksi yang didapat merupakan variabel produksi yang sama dan hal ini terjadi berulang – ulang kali dan tidak akan mencapat terminal. hal inilah yang menyebabkan mengapa left-recursive harus dihilangkan.
Contoh grammar dengan left recursif:
B -> Bα | β
Eliminasi left-factoring
Left-factoring berguna untuk menghasilkan grammar yang sesuai untuk top-down parsing.
Hal ini dilakukan karena ketika grammar menghasilkan beberapa produksi alternatif yang dapat men-expand non-terminal, parser akan bingung untuk memilih hasil produksi yang mana karena ambigu.
Maka kita dapat menulis ulang hasil produksi sampai inputan yang diterima sesuai.
Contoh : B -> αβ1 | αβ2
Dari contoh diatas maka kita akan bingung harus men-expand ke αβ1 atau αβ2
Sumber:
http://www.slideshare.net/hussiensharaf/cs419-lec10-left-recursion-and-left-factoring-31452912
http://www.cs.virginia.edu/~cs415/reading/RemovingLeftRecursion.pdf