Pembahasan Metode Parsing

Pembahasan Metode Parsing

Parsing adalah grup dari subrutin

yang mengkonversikan token stream ke parse tree. Parse tree adalah representasi struktural dari sebuah kalimat yang di parse.

Pengertian parsing secara umum adalah sebuah proses penentuan apakah sebuah string dari token dapat dihasilkan oleh sebuah grammar.

Sedangkan parsing pada proses sebuah query adalah merupakan tahapan dimana sintaks-sintaks dari query akan dicek untuk menentukan apakah query tersebut sudah dirumuskan sesuai dengan aturan-aturan sintaks (aturan-aturan grammar) dari bahasa query.

Setelah mengalami proses parsing di dalam parser, maka query tersebut kemudian diproses di dalam optimizer untuk mendapatkan rencana eksekusi. Proses parsing merupakan tahapan analisis sintaksis yang berguna untuk memeriksa urutan kemunculan token.

Di dalam mengimplementasikan sebuah metode parsing ke dalam program perlu diperhatikan tiga hal, yaitu :

  1. Rentang waktu eksekusi
  2. Penanganan kesalahan
  3. Penanganan kode

Salah satu dari metode parsing adalah metode top down. Metode ini melakukan penelusuran dari root/  puncak menuju ke leaf/ daun (simbol awal sampai simbol terminal). Metode top down sendiri meliputi :

  1. Backtrack/ backup : Brute Force

Metode ini akan memilih aturan produksi mulai dari kiri, dan melakukan expand semua non terminal pada aturan produksi sampai yang tertinggal adalah simbol terminal. Kemungkinan pertama string masukan sukses di-parsing, bisa juga bila terjadi expansi yang salah untuk suatu simbol variabel maka akan dilakukan backtrack. Algoritma ini membangun pohonparsing yang top down, yaitu mencoba segala kemungkinan untuk setiap simbol non terminal.

Kelemahan dari metode Bruce Force adalah:

  1. Mencoba untuk semua aturan produksi yang ada sehingga menjadi lambat (rentang waktu eksekusi tidak jelas)
  2. Menyulitkan untuk melakukan pemulihan kesalahan
  3. Memakan banyak memori karena perlu mencatat (backup) lokasi  backtrack.
  1. No backtrack: Recursive Descent Parser

Metode ini adalah salah satu cara mengaplikasikan bahasa bebas konteks untuk melakukan analisis sintaksis suatu source code.

Di sini simbol terminal maupun simbol variabelnya bukan karakter tetapi berupa besaran leksik sebagai simbol terminalnya dan besaran sintaks sebagai simbol variabelnya. Ciri dari metode ini adalah secara rekursif menurunkan semua variabel dari awal sampai bertemu terminal dan tidak pernah mengambil token secara mundur (no backtrack).

Ciri lain dari metode adalah dia sangat bergantung pada algoritma scan dalam mengambil token.

Untuk mengimplementasikan aturan-aturan produksi memakai teknik Recursive Descent Parser digunakan aturan sebagai berikut : 

  1. Semua simbol variabel dijadikan prosedur / fungsi.
  2. Jika bertemu simbol terminal pada aturan produksi, maka prosedur scan dipanggil.
  3. Jika  bertemu simbol variabel pada aturan produksi., maka prosedurnya dipanggil.
  4. Penelusuran bersifat top down mengikuti sintaks sesuai pola  yang tertera pada diagram sintaks.
  5. Karena memakai prosedur yang rekursif maka dipakai recursive stacking yang hampir sama dengan metode top down parsing  dengan brute force.
  6. Urutan produksi direalisasikan dengan menggunakan urutan dari pemanggilan fungsi / prosedur

Baca Juga :