Langsung ke konten utama

Eksplorasi Parsing Expression Grammar (PEG) dengan PEG.js (Part 1)

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~

Label:

Komentar

Posting Komentar

Aku berharap dapet komentar yang membangun.

Postingan populer dari blog ini

Mempersiapkan Diri untuk Magang sebagai Software Engineer Backend di Unicorn Company

Siapa yang ga mau magang di unicorn   company  seperti Bukalapak, Tokopedia, Traveloka, atau bahkan decacorn company  seperti GO-JEK? Aku rasa kita sebagai anak informatika sepakat bahwa perusahaan tersebut merupakan dream company . Setidaknya sebagian besar dari kita merasa demikian. Yah, kalau sekelas Google dan kawan-kawannya sih you don't say  lah ya. Dalam hal ini kita fokus sama perusahaan yang ada di dalam negeri dulu deh. Pertanyaannya, persiapan seperti apa yang dapat mempermudah kita diterima magang di perusahan tersebut? Kita semua tau bahwa perusahaan ini bukan perusahaan biasa-biasa aja sehingga kita tau orang-orang yang mereka cari tentunya bukan yang biasa-biasa juga. Gimana sih caranya biar standout ? Perlu disadari bahwa perisapannya gabisa sebentar dan aku secara pasti ga tau kualifikasi paling minimumnya seperti apa. Semua yang aku tulis di sini lebih ke great to have . Setidaknya dari pengalamanku ini aku berhasil dapetin tempat magang. Kenap...
5 komentar
Baca selengkapnya

Bagaimana Rasanya Magang Sebagai Software Engineer di Tokopedia?

Aku merupakan mahasiswa tingkat tiga. Artinya, aku diharuskan untuk magang karena adanya mata kuliah Kerja Praktik di semester keenam. Setelah berpetualang mendaftar berbagai macam perusahaan termasuk Twitter, Google, Tokopedia, Traveloka, Bukalapak, dan sebagainya. Kini aku berakhir di Tokopedia sebagai Software Engineer Intern. Tentunya pengalaman semacam ini akan aku bagikan kepada teman-teman karena selain dapat memberikan gambaran mengenai apa saja yang akan dilakukan, tetapi ini juga dapat dijadikan semacam motivasi bagi teman-teman untuk bisa magang di Tokopedia. Ya, in short , fokus kita di tulisan ini adalah pengalamanku selama tiga bulan magang di Tokopedia. Sesi foto bersama peserta magang dari berbagai universitas. Onboarding Seperti biasa, onboarding merupakan sesi pertama yang akan kita jumpai. Pada sesi ini kita akan diberikan pengenalan mengenai aturan kerja di Tokopedia, memperkenalkan diri ke tim yang "mengadopsi" kita, dan arahan untuk mempelaj...
2 komentar
Baca selengkapnya

Merancang Sistem Baru sebagai Upaya untuk Meningkatkan Kredibilitas serta Transparansi Perhitungan Suara

Indonesia dalam beberapa hari terkahir ini diramaikan dengan isu-isu serangan siber dan hal-hal konyol lainnya. Tetiba banyak sekali hacker gadungan yang bermain hacker-hackeran . Semua ini dilatarbelakangi oleh kekhawatiran masyarakat yang merasa akan terjadinya kecurangan dalam pemilihan umum kali ini. Alih-alih ingin berkontribusi justru yang ada malah terlihat bodoh. Untuk mengurangi hal-hal bodoh seperti ini muncul kembali, ada baiknya kita memikirkan sistem baru yang dapat membungkam manusia-manusia semacam ini di Indonesia. Tak perlu yang canggih sekali, yang penting transparan. Well , actually , teknologi yang akan digunakan sudah cukup canggih jadi aku bisa bilang kalau sistem yang akan dibuat ini sudah cukup canggih dan tidak mudah untuk dijaili. Tulisan ini hanya akan membicarakan konsep. Implementasinya tentu di lain waktu saja bila memungkinkan bagiku untuk membuatnya. Kenali Sistem yang Ada Sebelum membicarakan rancangan sistem yang baru, kita perlu mengenali sist...
3 komentar
Baca selengkapnya