Parsing Expression Grammar (PEG) pertama kali diperkenalkan oleh Bryan Ford pada tahun 2004 melalui paper-nya yang berjudul “Parsing Expression Grammars: A Recognition-Based Syntactic Foundation”. Alasan Ford memperkenalkan PEG adalah karena penggunaan CFG (context-free grammar) untuk mengekspresikan dan mem-parse bahasa berorientasi mesin dirasa sulit. Ini ada kaitannya dengan kemampuan generative grammar dalam mengekspresikan ambiguitas. Berhubung ambiguitas tadi merupakan salah satu permasalahannya, PEG pada akhirnya tidak memperkenalkan ambiguitas sama sekali. Akibatnya, PEG menggunakan prioritized choice yaitu mengambil pilihan pertama yang sesuai. Anggap saja ada tiga pilihan yang cocok dengan ekspresi yang kita tulis. Dalam hal ini PEG hanya akan mengambil pilihan pertama saja dan mengabaikan dua pilihan setelahnya.
Tulisan kali ini akan memberikan demonstrasi penggunaan PEG untuk mem-parse suatu string yang kemudian diubah bentuknya ke dalam structured form (bentuk yang terstruktur). Maksud dari structured form di sini adalah struktur data yang didukung oleh suatu bahasa pemrograman. Berhubung kita akan menggunakan PEG.js, maka kita akan mengubahnya ke dalam bentuk JavaScript object. Agar dapat memahami tulisan ini sepenuhnya, kamu harus mengerti bahasa pemrograman JavaScript dan juga sebaiknya kamu coba mencari materi mengenai CFG dan regular expression. Yah, setidaknya kamu harus mengerti dasar-dasar dari regular expression. Apabila kamu tertarik lebih jauh mengenai teori dari PEG, kamu bisa baca paper-nya Bryan Ford yang sudah saya cantumkan judulnya di atas.
Agar dapat mengikuti tulisan ini dengan baik, saya sarankan kamu mencoba PEG yang ditulis di tulisan ini. Kamu bisa membuka PEG.js Online kemudian menyalin grammar yang ada. Selanjutnya, kamu bisa mencoba memberikan input (masukan) untuk di-parse. Cobalah untuk memberikan input yang benar (valid) dan yang salah (invalid) kemudian lihat perbedaannya.
PEG vs PEG.js
Singkatnya, PEG.js menggunakan formalisme PEG dan menambahkan kemampuan untuk menulis sedikit kode JavaScript di dalamnya. Demikian itu, kita dapat memanipulasi bentuk returned value (sebut saja output) sesuai dengan yang kita inginkan. Lebih jelasnya kamu dapat mempelajari studi kasus di bawah.
Sebagai catatan, PEG menggunakan karakter / sebagai pengganti “atau” dari | milik CFG. Kemudian, PEG.js selalu menjadikan non-terminal paling atas sebagai starting point.
Studi Kasus: Aritmatika Sederhana
Anggap saja kita ditugaskan untuk mem-parse ekspresi aritmatika sederhana yang hanya terdiri dari operasi penjumlahan + dan pengurangan -. Sebelum kita coba menulis PEG-nya, kita lihat terlebih dahulu contohnya.
1+2+3-4+5
Setelah kita observasi, ternyata sebelah kiri dan kanan dari karakter + dan - adalah angka. Sekarang, kita punya dua entitas yang perlu kita perhatikan yaitu angka dan karakter operasinya. Kita definisikan dahulu kedua entitas tersebut menggunakan PEG.js grammar.
Angka = [0-9]+
Operasi = "+" / "-"
Kita mengetahui bahwa suatu ekspresi aritmatika dalam studi kasus ini terdiri dari Angka, Operasi, kemudian Angka lagi. Maka, kita tulis:
Ekspresi = Angka Operasi Angka
Angka = [0-9]+
Operasi = "+" / "-"
Apabila kita memberikan input 2-1, kita akan mendapatkan output (hasil parse) seperti di bawah.
[
[
"2"
],
"-",
[
"1"
]
]
Lantas, bagaimana caranya agar ekspresi 1+2+3-4+5 dapat di-parse? Coba kita uraikan. Ekspresi tersebut pada dasarnya Angka, Operasi, Angka, Operasi, Angka, dan seterusnya. Dapatkah kita ambil bentuk umumnya?
Sebelum kita cari bentuk umumnya, ada satu pertanyaan yang muncul. Apakah Angka saja dapat disebut sebagai ekspresi? Apakah angka 1234 tanpa ada operasi apapun dapat disebut sebagai ekspresi aritmatika? Saya pribadi akan menjawab iya sehingga kita dapat melihat uraian di atas menjadi Angka (Operasi (Angka (Operasi (Angka (...))))). Bagaimana? Sudah terlihat polanya? Sekarang, kita dapatkan:
Ekspresi = Angka (Operasi Ekspresi)*
Angka = [0-9]+
Operasi = "+" / "-"
Mengapa Angka (Operasi Ekspresi)*? Karakter * di sini memiliki arti nol atau lebih pola yang cocok itu valid. Sehingga, angka 1234 tanpa ada operasi apapun akan dianggap valid. Selanjutnya, apabila ada Operasi, maka selanjutnya harus ada Ekspresi. Kita tahu bahwa Angka saja dianggap valid oleh Ekspresi sehingga kita dapat melihatnya sebagai Angka (Operasi (Angka (Operasi Ekspresi)*)). Demikian itu, ekspresi 1+2+3 dapat dilihat sebagai Angka (Operasi (Angka (Operasi (Angka ())))).
Nah, dengan input 1+2+3-4+5, kita akan mendapatkan output:
[
[
"1"
],
[
[
"+",
[
[
"2"
],
[
[
"+",
[
[
"3"
],
[
[
"-",
[
[
"4"
],
[
[
"+",
[
[
"5"
],
[]
]
]
]
]
]
]
]
]
]
]
]
]
]
Output yang diberikan memiliki bentuk yang “ekstrim.” Sekarang kita coba lakukan format terhadap output-nya.
Ekspresi
= head:Angka tail:(Operasi Ekspresi)*
{ return [head].concat(tail.toString().split(',')); }
Angka
= [0-9]+ { return text(); }
Operasi
= ("+" / "-") { return text(); }
Output yang akan kita dapatkan berdasarkan grammar di atas adalah:
[
"1",
"+",
"2",
"+",
"3",
"-",
"4",
"+",
"5",
""
]
Menariknya, kita dapat langsung melakukan evaluasi di dalam PEG.js grammar. Sekarang, kita coba tambahkan non-terminal baru yaitu Start sebagai starting point juga sebagai tempat kita melakukan evaluasi. Sebagai informasi, kita juga dapat mendeklarasikan suatu fungsi JavaScript di PEG.js.
{
function int(x) {
return parseInt(x, 10);
}
}
Start
= eks:Ekspresi
{
let ans = int(eks[0]);
for (let opr = 1; opr < eks.length; opr += 2) {
const x = parseInt(eks[opr+1]);
switch (eks[opr]) {
case '+':
ans += x;
break;
case '-':
ans -= x;
break;
default:
}
}
return ans;
}
Ekspresi
= head:Angka tail:(Operasi Ekspresi)*
{ return [head].concat(tail.toString().split(',')); }
Angka
= [0-9]+ { return text(); }
Operasi
= ("+" / "-") { return text(); }
Apabila kita memberikan input 1+2+3-4+5, maka output yang akan kita dapatkan adalah 7. Selanjutnya, apa yang dapat kita lakukan? Kita dapat mengembangkan grammar yang ada misalnya agar dapat menerima input spasi (whitespace), mengatur precedence dengan tanda kurung ( & ), dan sebagainya.
Penutup
Part 1 dari tulisan “Eksplorasi Parsing Expression Grammar (PEG) dengan PEG.js” cukup sampai di sini. Kita sudah mencoba untuk mem-parse ekspresi aritmatika sederhana. Tujuan dari Part 1 ini adalah untuk memperkenalkan PEG.js sehingga contoh yang diberikan pun sederhana. Di Part 2 kita akan mencoba untuk mem-parse sesuatu yang lebih kompleks lagi.
See, ya~
Komentar
Posting Komentar
Aku berharap dapet komentar yang membangun.