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 parsingmerupakan 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.