Makan ceri merah memberi Anda kemampuan untuk memakan hantu biru. Gagasan bahwa turunan dapat digunakan untuk membuat algoritme pencocokan ekspresi reguler hampir sama menggelikannya. Izinkan saya menjelaskan cara kerja algoritme ini dan hubungannya dengan Pac-Man.

Pada tahun 1964, Brzozowski menerbitkan makalah pertama tentang Turunan Ekspresi Reguler . Sejauh ini, ini adalah salah satu algoritme favorit saya. Menggunakan turunan dari ekspresi reguler, kita dapat mengimplementasikan algoritma untuk melakukan pencocokan ekspresi reguler. Algoritma ini sangat:

• sederhana
• fungsional
• mudah diperpanjang dengan operator Anda sendiri

Pada artikel ini, saya akan menunjukkan kepada Anda bagaimana kami dapat mencocokkan string dengan ekspresi reguler hanya dengan menggunakan dua fungsi murni dan beberapa analogi Pac-Man. Jika mau, Anda dapat menonton video berikut alih-alih membaca artikel karena mencakup materi yang sama:

Rekap Ekspresi Reguler

Pertama, mari lakukan tinjauan singkat ekspresi reguler untuk memastikan kita berada di halaman yang sama. Ekspresi a(a|b)*cocok dengan string yang dimulai dengan an a, yang diikuti oleh sejumlah a's dan b's.

• String abakan cocok a(a|b)*. Kami akan menunjukkan ini dengan hantu biru yang bisa dimakan.
• String aabbbajuga cocok a(a|b)*karena dimulai dengan an adan diikuti oleh beberapa as dan b.
• Selanjutnya, string actidak cocok a(a|b)*, karena regex tidak cocok dengan apa pun cdan regex kami tidak melakukan pencocokan substring apa pun. Kami akan menunjukkan ini menggunakan hantu merah yang mengejar Pac-Man.
• Terakhir, string bajuga tidak cocok a(a|b)*karena tidak dimulai dengan a.

Sekilas tentang Algoritma

Sebelum mempelajari detailnya, mari kita lihat gambaran umum tentang cara kerja algoritme ini. Saya telah membuat game Pac-Man yang aneh di mana Anda hanya bisa memakan hantu jika Anda memakan buahnya dalam urutan yang sesuai dengan regex. Pac-Man kami mewakili regex aba*. Ini memiliki rangkaian buah berikut untuk dimakan: apel, lalu pisang, dan kemudian apel: aba.

1. Saat kita mulai, hantu itu mengejar kita, dan ekspresi reguler yang tersisa untuk kita cocokkan adalah aba*.
2. Kita memakan apel pertama, dan ekspresi reguler yang tersisa untuk dicocokkan adalah ba*. Hantu itu masih mengejar kami karena buah yang kami makan selama ini, apel, tidak cocok dengan regex.
3. Selanjutnya, kita makan pisang. Regex yang tersisa untuk dicocokkan adalah a*. Sekarang hantu itu mulai kabur karena, secara teknis, absudah cocok aba*.
4. Kita dapat mencoba memakan hantu atau memakan apel lain, dalam hal ini ekspresi reguler yang tersisa untuk dicocokkan masih a*. Hantu itu masih kabur karena abajuga cocok dengan ekspresi reguler aba*.

Ada satu fungsi lagi yang bekerja di sini. Fungsi memeriksa apakah hantu mengejar Pac-Man atau apakah Pac-Man sudah cocok dengan regex dan mengejar hantu. Fungsi ini disebut fungsi nullable; itu memeriksa apakah regex yang tersisa cocok, cocok dengan string kosong. Itu bisa dilakukan karena jika regex yang tersisa cocok, cocok dengan string kosong, buah yang dimakannya pasti sudah cukup untuk memuaskan regex.

Algoritma Pencocokan Derivatif

Artinya, kita hanya memerlukan dua fungsi untuk menulis algoritme pencocokan turunan:

1. fungsi turunan
2. fungsi nullable

Satu di Golang untuk programmer penting:

dan satu lagi di Haskell untuk pemrogram fungsional:

Kedua fungsi ini setara dan hanya ditulis dalam gaya pemrograman yang berbeda. Dalam kode Haskell, yang foldljuga disebut lipat ke kiri atau kurangi dalam bahasa lain, melakukan perulangan for untuk Anda. Selain itu, di Haskell, kita tidak memerlukan koma untuk meneruskan parameter ke fungsi; karena aplikasi fungsi adalah operasi yang paling umum dalam bahasa pemrograman fungsional, kami menggunakan ruang untuk membatasi parameter.

Sekarang, mari selami lebih dalam cara mengimplementasikan fungsi nullable dan turunan.

Penyimpangan Cerita Asal Pac-Man

Tapi sebelum kita melakukan itu, saya tidak tahu apakah Anda pernah bertanya-tanya tentang kisah asal usul Pac-Man. Saya berpendapat tidak ada tong limbah nuklir tempat Pac-Man jatuh, sehingga Pac-Man mendapatkan kekuatan untuk memakan hantu. Logikanya jauh lebih sederhana.

Pac-Man adalah buah! Saat Pac-Man memakan buah lain, Pac-Man menjadi kanibal. Jadi jika Anda pernah dikejar oleh hantu, Anda harus makan daging manusia, dan hantu itu harus, setidaknya untuk sementara, mulai melarikan diri dari Anda. Sekarang, saya sendiri belum mencobanya, tetapi logikanya sepertinya masuk akal.

Ini menjelaskan mengapa zombie selalu mengejar manusia. Seperti yang pernah dikatakan David Attenborough:

“Zombie yang mengejar kita, mereka sendiri dikejar oleh hantu yang tidak bisa kita lihat. Setelah zombie memakan sebagian dari daging manusia kita, Anda akan melihat mereka menunjukkan perilaku aneh mengunyah di udara, ini adalah zombie yang memakan hantu yang mengejarnya sebelumnya.

Operator Dasar

Implementasi fungsi nullable dan turunan mengharuskan kita terlebih dahulu menentukan operator dasar yang tersedia dalam ekspresi reguler kita.

Kita dapat menganggap ekspresi reguler sebagai mendeskripsikan sekumpulan string.

• Ini berarti bahwa set kosong mewakili operator yang tidak cocok dengan string.
• String kosong mewakili satu set string tunggal yang hanya cocok dengan string kosong.
• Karakter juga mewakili satu set tunggal yang hanya cocok dengan satu karakter a.
• Kami kemudian dapat menggabungkan ekspresi reguler dasar ini menggunakan operator seperti: or, concatenationdan Kleene star, di mana rdan smewakili dua ekspresi reguler yang kami gabungkan.

Fungsi Nullable

Kita bisa mulai dengan fungsi nullable. Mari kita lihat beberapa contoh dan cari tahu ekspresi reguler mana yang cocok dengan string kosong untuk mendapatkan wawasan tentang bagaimana fungsi ini diimplementasikan.

• a*cocok dengan string kosong karena nol atau lebih termasuk nol.
• (a*|b)cocok dengan string kosong sejak sisi kiri atau cocok dengan string kosong.
• abtidak cocok dengan string kosong, karena hanya cocok dengan stringab
• ab*juga tidak cocok dengan string kosong, karena ab*memerlukan string yang dimulai dengan ana
• (a|b)tidak cocok dengan string kosong, karena sisi kiri maupun kanan tidak orcocok dengan string kosong.

Berikut adalah implementasi dari fungsi nullable. Sisi kiri mewakili nilai yang diteruskan ke fungsi, dan sisi kanan mewakili implementasi fungsi dalam kasus tersebut. Hantu merah melambangkan palsu, dan hantu biru melambangkan benar:

• Set kosong tidak cocok dengan string kosong karena tidak cocok dengan string apa pun.
• String kosong cocok dengan string kosong karena hanya cocok dengan string kosong.
• Karakter atidak cocok dengan string kosong karena hanya cocok dengan karakter a.
• Jika kita memiliki logika or, kita harus memeriksa kedua sisi. Jika salah satu cocok dengan string kosong, maka logis orcocok dengan string kosong.
• Agar concatenationdari dua ekspresi reguler cocok dengan string kosong, keduanya harus cocok dengan string kosong.
• Dan terakhir, jika kita memiliki zero or moresesuatu, maka itu termasuk nol, yang artinya selalu cocok dengan string kosong.

1. Operator teratas kami adalah orthis berarti kami harus memeriksa nullability dari sisi kiri dan kanan: bdan a*.
2. Kami memeriksa dan melihat bahwa karakter bdi sisi kiri tidak dapat dibatalkan: false.
3. Kemudian kami memeriksa dan melihat bahwa a*di sisi kanan adalah nullable: true.
4. Sekarang kami kembali falsedan truekami bisa ormendapatkannya true.

Latihan yang dapat dibatalkan

Coba telusuri implementasinya dan periksa apakah ekspresi reguler berikut dapat dibatalkan. Anda dapat mengkliknya untuk memeriksa jawaban Anda:

1. sebuah
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

Sebelum kita melihat implementasi fungsi, mari kita lihat contoh turunannya. Di sini kita akan mengambil turunan dari beberapa ekspresi reguler, semuanya sehubungan dengan karakter a:

• Ekspresi reguler yang tersisa untuk dicocokkan setelah a*memakan aapel masih a*.
• Turunan dari ab*terhadap aadalah b*, karena kita telah mencocokkan awalannya a.
• Turunan dari (a|b)bterhadap aadalah b.
• Turunan dari b|(a*b)terhadap aadalah a*b. Yang kiri btidak cocok, jadi kami bisa membuangnya dan adikonsumsi oleh yang zero or more adi kanan.
• Selanjutnya, kita punya ab*, yang ini sedikit rumit. Setelah memakan apel, ekspresi reguler yang tersisa untuk dicocokkan adalah b(ab)*. Karena kami hanya cocok dengan a, kami mengharapkan untuk melihat setidaknya satu lagi b.

• Turunan dari himpunan kosong selalu merupakan himpunan kosong. Tidak ada cara untuk memulihkan karena set kosong tidak cocok dengan apapun.
• Turunan dari string kosong mengenai karakter apa pun adalah himpunan kosong. Itu tidak diharapkan cocok dengan karakter. Itu hanya akan cocok dengan string kosong.
• Turunan dari satu karakter ke karakter yang mirip (dalam hal ini, apple) adalah string kosong karena setelah dicocokkan dengan dirinya sendiri, yang tersisa untuk dicocokkan hanyalah string kosong.
• Turunan dari suatu karakter terhadap karakter lain yang tidak sama, dalam hal ini banana, adalah himpunan kosong karena kita belum mencocokkan karakter tertentu.
• Turunan dari suatu orekspresi adalah orturunan dari. Itu hanya mendorong masalah ke anak-anaknya.
• Turunan dari concatekspresi harus mempertimbangkan apakah dapat melewati ekspresi pertama. Itu hanya dapat melewati ekspresi pertama jika ekspresi pertama cocok dengan string kosong dan dapat dibatalkan. Jadi hal pertama yang kita lakukan adalah memeriksa ini. Mari kita pikirkan tentang kasus di mana ekspresi pertama tidak dapat dilewati ketika ekspresi rtidak dapat dibatalkan. Maka turunannya adalah turunan dari ekspresi pertama concatenateddengan ekspresi kedua s. Jika kita dapat melewati regex pertama, kita harus mempertimbangkan alternatif yang hanya merupakan turunan dari ekspresi kedua. Kami kemudian dapat ordua alternatif melompati rdan tidak melompati rdan mengembalikannya sebagai hasilnya.
• Akhirnya, kami memiliki staroperator. Ini cocok dengan ekspresi nol kali atau lebih. Karena kita sedang melewati karakter, ini bukan kasus nol. Jadi kita harus mempertimbangkan one or morekasusnya. Ini berarti kita harus mengambil turunan dari ekspresi di dalam stardan concatenatelagi dengan zero or moreekspresi.

Contoh turunan 1

Mari kita ambil turunan dari (ab)*terhadap a.

(ab)*adalah zero or moreekspresi, jadi kami melihat ke zero or moreaturan. Kami melihat ini membutuhkan turunan dari ekspresi di dalam star.

Ini adalah concatenationdari adan b. Jadi kami memeriksa apakah sisi kiri dapat dibatalkan, dan karakternya atidak dapat dibatalkan. Ini berarti kita tidak bisa melewatkannya. Kita harus mengambil turunan dari aterhadap a. Tapi itu adalah string kosong, jadi jika kita concatenatestring kosong dengan sisi kanan, yaitu b, kita dapatkan b.

Sekarang, kita kembali ke zero or more, ingat kita mengambil turunan dari abterhadap adan mendapatkan kembali b. Sekarang kita dapat menggabungkannya dengan (ab)*lagi dan kita mendapatkan b(ab)*.

Contoh turunan 2

Mari kita ambil turunan dari (a*ba)terhadap b.

• a*digabungkan dengan bajadi kita lihat aturan penggabungan.
• Kami memeriksa apakah sisi kiri a*dapat dibatalkan, yang memang demikian. Ini berarti kita dapat melewatkannya, yang juga berarti kita harus membuat ordua turunan.
• Sisi kiri berakhir tidak cocok, karena a*tidak cocok b.
• Untungnya kami memiliki alternatif file ba. Turunan dari baterhadap badalah dan a.

Saya telah melewatkan beberapa detail di sini. Anggap saja sebagai latihan untuk memeriksa pekerjaan saya dengan menelusuri sendiri fungsinya.

Latihan turunan

Coba telusuri penerapannya dan periksa apa turunan dari ekspresi reguler berikut sehubungan dengan b. Anda dapat mengkliknya untuk memeriksa jawaban Anda:

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅*b

Saya harap Anda sekarang mengerti mengapa memakan ceri merah memberi Anda kemampuan untuk memakan hantu biru dan bagaimana menerapkan pencocokan ekspresi reguler menggunakan algoritma turunan.

Kami telah membahas algoritme kerja dasar di sini, tetapi ada banyak cara untuk membuat algoritme ini menjadi lebih baik dengan tweak yang sangat kecil. Kami menipu dan mengabaikan aturan penyederhanaan dalam posting ini, menggunakannya tanpa menjelaskannya, yang akan menjadi sangat jelas jika Anda mengikuti latihan. Kami juga belum membahas bagaimana Anda dapat menggunakan memoisasi untuk membuat robot yang efisien dengan malas.

Kami juga dapat dengan mudah memperluas algoritme untuk menyertakan operator baru seperti, not, interleavedan bahkan mendukung Tata Bahasa Bebas Konteks. Saya akan membahas beberapa topik ini di artikel berikutnya .

Sementara itu, saya ingin melihat penerapan algoritme ini dalam bahasa pemrograman yang paling Anda sukai. Tolong kirimkan saya tautan di komentar.

Terima kasih

• Brink van der Merwe karena telah meluangkan waktu untuk menjelaskan algoritme ini kepada saya.

• Brzozowski, Janusz A. "Turunan dari ekspresi reguler." Jurnal ACM (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy, dan Aaron Turon. "Turunan ekspresi reguler diperiksa ulang." Jurnal Pemrograman Fungsional 19.2 (2009): 173–190.