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 pohon
parsing 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.
2.
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
. Fungsi / prosedur ditulis untuk setiap non
terminal dari suatu produksi. Setiap fungsi/ prosedur akan melemparkan nilai
benar atau salah bergantung apakah fungsi tersebut mengenali substring yang
diterima sebagai ekspansi dari non terminal.