People Innovation Excellence
 
Feature Image

Mengapa Perlu Menghilangkan Left-Recursive ketika menggunakan metode Top-Down Parsing?

Salah satu tahap pada proses kompilasi adalah sintaks analisis. Pengecekan terhadap grammar akan dilakukan pada tahapan ini. Untuk mengecek sebuah sintaks (string) sudah sesuai dengan aturan produksi yang ada maka kita dapat membuat parse tree dari string tersebut. Ada 2 macam metode untuk parsing, yaitu top-down parsing dan bottom-up parsing.  Ketika melakukan top-down parsing maka yang perlu diperhatikan adalah memastikan bahwa tidak ada left recursive pada aturan produksi yang dimiliki (grammar).

Top-Down parsing melakukan derivasi dengan cara left-most derivation. Dengan adanya grammar yang mengandung left-recursive, maka akan terjadi perulangan derivasi yang tidak menemukan titik henti. Untuk memberikan gambaran jelasnya maka mari kita lihat contoh dibawah ini.

Diberikan sebuah aturan produksi (Context Free Grammar) sebagai berikut:

S -> Sab | AbA

A -> a | b

Pada CFG diatas terdapat variabel S dan A sebagai variabel pemproduksi, sedangkan terminalnya adalah a dan b. S memiliki 2 aturan produksi, yaitu Sab atau AbA. Pada produksi S -> Sab mengandung left recursive. S memanggil dirinya sendiri namun terletak pada sebelah paling kiri dari aturan tersebut, sedangkan untuk aturan S -> AbA tidak mengandung left recursive ( S tidak memanggil dirinya sendiri).

Ketika kita ingin membuat parse tree untuk input ababb maka kita akan selalu memulai dari start symbol yang biasanya terletak dipaling atas dari grammar kita (Disini adalah S). Kemudian kita akan memanggil grammar yang pertama yaitu Sab, sehingga ketika digambarkan akan menjadi seperti dibawah ini.

Karena top-down parsing menerapkan left-most derivation, maka untuk langkah selanjutnya kita akan melakukan derivasi kembali untuk variabel S yang terletak dipaling kiri dari pohon tersebut. Ketika melakukan derivasi dari S kita memiliki 2 buah pilihan aturan lagi yaitu Sab dan AbA, dan kita memilih menggunakan aturan yang pertama Sab.  Hal ini akan terus berulang sampai derivasi berhasil menemukan karakter pertama dari input string yaitu ‘a’.

Bisa saja bila dengan metode parsing biasa (brute force) maka kita bisa memilih aturan produksi yang kedua (S -> AbA) untuk menghentikan perulangan tersebut. Akan tetapi bila hal tersebut dilakukan maka memungkinkan dibutuhkannya backtracking. Adapun menggunakan metode top-down parsing kita tidak akan melakukan backtracking, melainkan kita akan memilih aturan produksi yang akan digunakan berdasarkan parsing tabel yang akan dibuat. Oleh karena itu penting untuk menghilangkan left recursive jika menggunakan metode top-down parsing dikarenakan top-down parsing menerapkan left-most derivation.


Published at :
Written By
Novita Hanafiah., S.Kom., M.Sc
Lecturer of Computer Science | School of Computer Science

Periksa Browser Anda

Check Your Browser

Situs ini tidak lagi mendukung penggunaan browser dengan teknologi tertinggal.

Apabila Anda melihat pesan ini, berarti Anda masih menggunakan browser Internet Explorer seri 8 / 7 / 6 / ...

Sebagai informasi, browser yang anda gunakan ini tidaklah aman dan tidak dapat menampilkan teknologi CSS terakhir yang dapat membuat sebuah situs tampil lebih baik. Bahkan Microsoft sebagai pembuatnya, telah merekomendasikan agar menggunakan browser yang lebih modern.

Untuk tampilan yang lebih baik, gunakan salah satu browser berikut. Download dan Install, seluruhnya gratis untuk digunakan.

We're Moving Forward.

This Site Is No Longer Supporting Out-of Date Browser.

If you are viewing this message, it means that you are currently using Internet Explorer 8 / 7 / 6 / below to access this site. FYI, it is unsafe and unable to render the latest CSS improvements. Even Microsoft, its creator, wants you to install more modern browser.

Best viewed with one of these browser instead. It is totally free.

  1. Google Chrome
  2. Mozilla Firefox
  3. Opera
  4. Internet Explorer 9
Close