MENGAPA DALAM MELAKUKAN TOP-DOWN PARSING HARUS DILAKUKAN PENGHILANGAN LEFT RECURSION TERLEBIH DAHULU DAN LEFT FACTORING?
Top Down Parsing
Merupakan suatu usaha untuk menemukan left most derivation dari sebuah string. Untuk melakukan top down parsing tersebut, terlebih dahulu harus dilakukan penghilangan bentuk rekursif kiri. selain itu perlu juga dilakukan left factoring untuk menghilangkan ambiguitas dari suatu string.
Left Recursion
Untuk melakukan top-down parsing , bentuk rekursif dari string harus dihilangkan. Hal ini harus dilakukan untuk menghindari terjadinya keadaan dimana tidak ditemukan terminal. Ini disebabkan oleh ekspansi variable yang dilakukan secara berulang-ulang.
Untuk sebuah top-down parser, setiap bentuk rekursif yang ada harus lah rekursif kanan. Untuk itu perlu dilakukan pengubahan dari bentuk rekursif kiri menjadi rekursif kanan.
Contoh : A -> Aa | bc | d
A -> bcA’ | dA’
A’-> aA’ | ε
Left Factoring
Left factoring merupakan pengubahan bentuk grammar untuk menghasilkan bentuk grammar yang sudah tidak ambigu. Maksudnya adalah sebuah string yang masih belum diketahui apakah string tersebut rekursif kiri atau bukan. Oleh karena itu dalam top down parsing perlu dilakukan left factoring untuk menghilangkan ambiguitas string yang akan di parsing.
Contoh: A -> Ab | Ac |d
A -> AA’ | d
A’ -> b | c