Mengapa dalam Top-Down Parsing harus menghilangkan left-recursion dan left-factoring?
Jawaban :
TOP-DOWN PARSING
Dapat dipandang sebagai :
- Usaha untuk mencari leftmost derivation dari suatu input string
- Usaha untuk membangun parse tree dari suatu input string, dimulai dari root (top) sampai dengan leaves (bottom), dengan urutan preorder.
Dalam parser top-down, Left-recursion dan left factor grammars tidak bekerja karena jika terdapat Left-recursion kita tidak tahu kapan recursionnya berhenti ( loop forever ) dan jika terdapat left factor, akan menghasilkan 2 atau lebih produksi ( ambiguitas ). Jadi sebelum melakukan Top-Down parsing, left-recursion harus dihilangkan (dieliminasi ) dan melakukan left factoring jika terdapat left factor grammar untuk mendapatkan grammar yang sesuai untuk parsing.
Contoh :
Pada grammar diatas tidak terdapat left-recursion, tetapi grammar tersebut memiliki left factor sehingga harus dilakukan left-factoring, menghasilkan :
Kelompok 7
1501145700- Rifan Wijaya
1501185156- Charles Kho
1501146893- Fery Kurniawan
1501148450- Felix Hendrian