[tek.kompilasi|t.informatika|s-103|pert.8]

Untuk orang yang non ilmu komputer atau teknik informatika, istilah parsing merupakan istilah asing yang membuat dahi keriput. Bagaimana tidak, hanya menggunakan bahasa pemrograman saja sudah pusing, ini malah diminta membuat suatu bahasa pemrograman. Tapi perlu diingat, salah satu kewajiban pembelajaran adalah “apakah yang kita ajarkan sudah seharusnya yang kita ajarkan?”. Pertanyaan itu merupakan pertanyaan yang harus dijawab. Pertanyaan yang dikeluarkan oleh Mahatma Gandhi ketika India baru merdeka dan ingin segera bersaing dengan negara maju.

Grammar

Kembali ke proses pembuatan bahasa pemrograman. Sebelum bisa membuat suatu bahasa, perlu mengetahui cara kerja suatu bahasa. Bahasa bekerja mengikut grammar yang ada. Chomsky mengusulkan suatu context free grammar yang bebas dari linguistik lokal yang tidak beraturan. Sebagai contoh kita memiliki aturan grammar sebagai berikut:

Apa maksudnya? Di sini ada tiga aturan yang membolehkan pengguna mengoperasikan: 1) variabel ditambah variabel. Variabel di sini diistilahkan dengan non-terminal (bukan titik destinasi akhir), sementara terminal berupa konstanta atau operasi seperti tambah, kurang, kali dan bagi. 2) variabel dikalikan dengan variabel, serta 3) variabel diisi oleh konstanta. Secara singkat, notasi grammar di atas dapat ditulis dalam satu baris: E->E+E|E*E|id. Ekspresi di atas mengikut kaidah Backus Naur Form (BNF) yang terkenal untuk context free language.

Tugas bagian parsing adalah mengecek validitas operasi yang diberikan oleh pengguna apakah sudah sesuai dengan grammar yang ada atau tidak. Sebagai contoh user mengetikan persamaan matematis: E->x+y*z. Parsing akan mengecek apakah sudah sesuai atau tidak dengan grammar.

Shift and Reduce Parsing

Sesuai dengan namanya metode ini mengkombinasikan antara penggeseran dan pengurangan parsing. Contoh sebelumnya jika kita kerjakan maka otak kita lebih mudah mengerjakan lewat mekanisme ‘top down’ sambil melihat grammarnya. Dalam contoh di atas, ada penjumlahan (x+y) dan perkalian (dengan z). Dengan menggunakan left hand first diperoleh urutan berikut ini:

Perhatikan aturan grammar yang diterapkan di dalam kurung di samping kanan proses top-down. Pertama-tama digunakan aturan perkalian yang menghasilkan dua non-terminal E. E yang kanan dengan menerapkan rule no.3 diperoleh konversi dari E ke id (dalam hal ini z). Langkah berikutnya dengan menggunakan aturan no.1 dimana E menurunkan E+E (simbol -> diistilahkan turunan (derrive). Teruskan dengan menggunakan rule no. 3 akan merubah non-terminal menjadi terminal berturut-turut x dan y. Karena hasil akhir sama dengan soal, maka dapat dikatakan instruksi x+y*z dapat diterima parser.

Kita mungkin mudah mengerjakan dengan top-down method ini. Bagaimana dengan komputer? Tentu saja berbeda dengan otak kita. Untuk itulah metode shift and reduce layak diperhitungkan. Cara kerja shift and reduce adalah sebagai berikut:

• Tulis operasi yang akan dicek grammar-nya
• Lakukan operasi shift untuk memisahkan non-terminal/variabel yang akan diisikan id.
• Lakukan operasi reduce untuk mengganti variabel menjadi terminal.

Perhatikan 11 langkah di atas, yang merupakan tipikal operasi shift and reduce. Pada langkah pertama, instuksi akan siap-siap melakukan proses “shift” dimana x bergeser ke kiri. Selanjutnya, x yang telah berada di kiri dikonversi menjadi terminal/variabel E. Berikutnya langkah ke3 dan 4 dua buah proses shift yaitu untuk plus dan y dilanjutkan dengan reduce y menjadi terminal E. Langkah 8, 9, dan 10 bermaksud mereduksi instruksi mengikut grammar sehingga dihasilkan E yang artinya instruksi x+y*z dapat diterima (accepted). Berikutnya akan dicoba lewat perangkat lunak Lex and Yacc, khususnya bagian Yacc yang bertanggung jawab mengurusi Grammar.

Perhatikan saat kompilasi Yacc di bagian komentar. Tampak Yacc menunjukan 4 shift/reduce [1] yang konflik. Ini tipikal dari bagian pengecekan instruksi (dengan shift and reduce). Perhatikan di sini saya iseng mengganti “+” dengan “p” dan “-” dengan “m”. Kira-kira hasil bahasa pemrograman primitif sebagai berikut di bawah ini. Perhatikan, “p” bermakna plus dan “m” bermakna minus. Sekian, semoga bermanfaat.