TM2 Teknik Kompilasi

Posted March 12th, 2014 by agungroyat

Mengapa top down parsing harus menghilangkan left recursion dan left factoring?

Alasan:

Top-Down Parsing merupakan salah satu metode yang digunakan untuk mencari leftmost derivation pada input suatu string. Selain itu, Top-Down Parsing juga dapat digunakan untuk membuat pars tree dari suatu input string yang dimulai dari root sampai dengan leaves dengan urutan preorder.

Ada 2 hal yang perlu diperhatikan pada Top-Down Parsing. Pertama, left recursive harus dihilangkan karena terdapat Metode Brute-Force. Ciri pada metode tersebut antara lain seperti memilih aturan produksi mulai dari kiri, meng-expand simbol non terminal hingga terminal. Sehingga apabila terjadi kesalahan, dalam hal ini string yang tidak sesuai maka dilakukan backtrack. Salah satu kelemahan yang ditemukan pada Metode Brute-Force adalah mencoba semua aturan produksi yang ada sehingga menjadi lambat. Hal tersebut menyebabkan grammar yang memiliki left recursive (rekursif kiri) mengalami loop secara terus-menerus. Kedua, berkaitan dengan left factoring. Left factoring dapat menghasilkan suatu grammar yang ambigu (ambiguity). Suatu kalimat disebut ambigu apabila terdapat lebih dari 1 pohon sintaks yang dapat dibentuk oleh kalimat tersebut.

www.binus.ac.id