Top Down Parsing
Top down parsing melakukan parsing dari start simbol samapi dengan teriminal sehingga terbentuk parse tree dengan menggunakan left most derivation sehingga penurunan dilakukan dari simbol paling kiri terlebih dahulu baru dilanjutkan ke simbol selanjutnya (dari kiri ke kanan).
Didalam top down parsing, grammar yang mengandung left recursion dan left factoring tidak bisa ditangani oleh top down parsing, sehingga grammar tersebut harus diubah untuk menghilangkan left recursion dan left factoring.
Left recursion dan left factoring tidak dapat di tangani oleh Top down parsing karena :
1. Akan menyebabkan loop terus menerus.
Hal ini terjadi karena dengan left most derivation, maka simbol akan diturunkan dari kiri kekanan, sehingga ketika menemukan A->Aα . maka A akan diturunkan menjadi A kembali dan begitupun seterusnya sehingga akan menyebabkan looping teru menerus
Contoh :
A->Abcd
A->Abcdbcd
A->Abcdbcdbcd
Sehingga dapat terlihat bahwa A akan terus menghasilkan A yang akan menyebabkan loop terus menerus, dan loop terus menerus ini akan menyebabkan kompleksitas yang tinggi dan juga akan sangat membebani memori.
2. Tidak efisien
Hal ini disebabkan karena adanya backtracking yang terjadi pada left recursion. Backtracking adalah suatu kondisi dimana pembacaan inputan dilakukan secara beulang – ulang. Pembacaan berulang ini terjadi karena ketidak cocokan inputan atau kesalahan parsing. Kemudian dengan adanya left recursion, terjadi loop terus menerus yang akan mengurangi efesiensi memori dan waktu parsing.
Kelompok 5
Bernardus Robby 1501144332
Elisabeth Oktaviani 1501154516
I Kadek Mega Adi Utama 1501159170
Michael Chandra 1501146621