Menghitung perbedaan dan irisan dua ekspresi reguler

 (phylactery.org)
2 poin oleh GN⁺ 2023-09-12 | 1 komentar | Bagikan ke WhatsApp
  • Saat perlu membandingkan ekspresi reguler seperti himpunan string, antimirov dapat menghitung relasi inklusi dan kesetaraan antara dua ekspresi α dan β, serta irisan dan selisihnya dalam satu layar
  • Area hasil menampilkan komplemen dan relasi sekaligus, sehingga Anda dapat memeriksa operasi seperti ~α, α < β, α = β, α & β, α ^ β, α - β
  • Jika memasukkan string terpisah s, Anda bisa langsung memverifikasi apakah masing-masing ekspresi reguler cocok melalui s ∈ α dan s ∈ β
  • Sintaksnya mendukung ., konkatenasi, pilihan |, pengulangan *·+·?·{n}·{m,n}, grup karakter, grup karakter negasi, escape, dan escape Unicode UTF-16
  • Fitur pengubah perilaku seperti anchor, zero-width assertion, backreference, ekstraksi subgrup, pencarian/pencocokan parsial, dan pengabaian huruf besar-kecil tidak didukung

Perbandingan ekspresi reguler dan operasi himpunan

  • Area input menerima dua ekspresi reguler α dan β
  • Output menampilkan komplemen serta operasi relasi dan himpunan dari kedua ekspresi reguler sekaligus
    • ~α, ~β: komplemen dari masing-masing ekspresi reguler
    • α < β, α = β, α > β: relasi inklusi dan kesetaraan antara dua ekspresi reguler
    • α & β: irisan
    • α ^ β: beda simetris
    • α - β: selisih
  • Jika memasukkan string s, Anda dapat memeriksa apakah string tersebut termasuk ke masing-masing ekspresi reguler dalam bentuk s ∈ α, s ∈ β
  • Ukuran tiap ekspresi reguler dan jumlah status DFA juga ditampilkan
    • Pada layar contoh, |α| = 1, |β| = 1
    • Pada layar contoh, dfa(α) dan dfa(β) masing-masing memiliki 1 status

Sintaks ekspresi reguler yang didukung

  • Operator dasar mencakup karakter tunggal, konkatenasi, pilihan, dan pengulangan
    • .: mencocokkan satu karakter apa pun
    • xy: konkatenasi yang mencocokkan x lalu y
    • x|y: mencocokkan x atau y
    • x*: pengulangan 0 kali atau lebih
    • (xyz): pengelompokan
    • (): ekspresi reguler kosong yang mencocokkan string kosong
  • Bentuk singkat pengulangan yang umum juga didukung
    • x+: pengulangan 1 kali atau lebih, setara dengan xx*
    • x?: pencocokan opsional, setara dengan (x|)
    • x{n}: mengonkatenasikan x sebanyak n kali
    • x{m,n}: mengonkatenasikan x minimal m kali dan maksimal n kali
  • Himpunan karakter dan escape dapat menggunakan bentuk berikut
    • [a-z0-9]: mencocokkan satu karakter dalam grup
    • [^a-z0-9]: mencocokkan satu karakter yang tidak ada dalam grup
    • \\c: escape karakter khusus c
    • \\u001a: mencocokkan karakter UTF-16 yang sesuai
    • Selain itu, karakter seperti a, b, c mencocokkan dirinya sendiri

Fitur yang tidak didukung

  • antimirov berfokus pada penanganan ekspresi reguler sebagai objek operasi himpunan, sehingga fitur berikut dikecualikan
    • Anchor ^, $
      • Namun, ^ dan $ tetap harus di-escape
    • Zero-width assertion, misalnya (?=...), (?<=...)
    • Backreference, misalnya \\1, \\2
    • Ekstraksi subgrup
    • Pencarian atau pencocokan parsial
    • Flag lain yang mengubah perilaku, seperti pengabaian huruf besar-kecil
  • Informasi lebih lanjut dapat dilihat di non/antimirov

Bacaan terkait

1 komentar

 
GN⁺ 2023-09-12
Komentar Hacker News

  • Saya pernah membuat demo web serupa yang menunjukkan proses regex berubah dari parsing → NFA → DFA → DFA minimal, lalu dari DFA minimal menghasilkan LLVM IR/Javascript/WebAssembly
    http://compiler.org/reason-re-nfa/src/index.html

  • Library ini bisa dipakai untuk membuat hierarki kelas string, sehingga string bertipe dapat dimanfaatkan lebih aktif
    Misalnya, email dan URL memiliki tata bahasa khusus; ruang nilainya adalah subset dari semua string yang tidak kosong, dan string yang tidak kosong adalah subset dari semua string
    Jika type system mengetahui bahwa string email adalah subtype dari string yang tidak kosong, maka alamat email yang diberikan ke fungsi yang membutuhkan string tidak kosong dapat dianggap valid
    Library ini bisa digunakan untuk memverifikasi definisi dan hierarki tipe string semacam itu, sementara implementasi hierarkinya berbeda-beda di tiap bahasa, misalnya melalui subclassing, trait bound, dan sebagainya

    • Dalam bahasa yang memiliki tagged union type, pendekatan seperti ini sering dipakai. Pseudocode bergaya Haskell kira-kira seperti ini
      Konstruktor Address tidak diekspor, hanya tipenya yang diekspor; validasi dilakukan di dalam fromString :: Text -> Maybe Address, dan jika alamat tidak valid akan mengembalikan Nothing
      Validitas jangan dicampurkan ke dalam data; kirimkan sinyal lewat jalur terpisah, lalu saat perlu output, ambil kembali nilai yang dibungkus dengan toText :: Address -> Text
    • Sebaiknya jangan memakai regex untuk validasi alamat email
      https://news.ycombinator.com/item?id=31092912
    • Tidak banyak hal yang lebih aneh daripada menggali apa saja yang boleh dan tidak boleh ada sebagai alamat email di sisi kiri @ pada pagi hari di akhir musim panas
      Heuristik sederhana bahwa setiap regex yang mencoba merepresentasikan “alamat email yang valid” pasti salah memang cukup aman, tetapi itu merusak semua keseruannya
    • Saya penasaran apa maksud “ruang nilai”

  • Regex adalah contoh bagus dari teori matematika yang cukup keren dan kompleks yang dibungkus menjadi antarmuka yang bernilai
    Aljabar linear juga terasa mirip

    • Selalu menakjubkan bahwa dengan field yang tepat, begitu banyak matematika bisa berubah menjadi aljabar linear
      Bahkan transformasi Möbius pada bidang kompleks w=(az+b)/(cz+d) pun bisa diubah menjadi aljabar linear
    • Biasanya dalam kasus seperti itu, representasinya berarti makin mendekati kebenaran
      Antarmuka yang baik punya nilai intrinsik, tetapi banyak orang yang berorientasi hasil tidak terlalu mengakuinya
    • Kalau ingatan saya benar, sepertinya hubungan dengan aljabar linear dibahas dalam buku Conway ini: https://store.doverpublications.com/0486485838.html. Saya hanya pernah membacanya sekilas

  • Halaman keren ini menghitung relasi biner di antara pasangan regex dan menampilkan DFA sebagai graf
    Ini benar-benar mendemonstrasikan operasi-operasi yang cukup tidak trivial pada regex dengan sangat mengesankan

    • Sangat keren, tetapi secara ketat tidak mengherankan juga bahwa halaman ini tidak mendukung fitur-fitur yang membuatnya bukan lagi regex
      Meski begitu, saya kira anchor ^ dan $ tidak akan bermasalah

  • Saya mencoba menempelkan “regex filter numbers divisible by 3”, dan halamannya benar-benar macet: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    Saya penasaran apakah ada ekspresi yang lebih pendek

    • Halaman web ini macet pada regex yang membuat DFA dengan banyak state
      Contohnya seperti (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • Lagi pula, menurut penjelasan halaman tersebut, anchor memang tidak didukung

  • Saya ingin melihat irisan antara URL yang valid secara sintaksis dan alamat email, tetapi memasukkan regex URL di bawah ini saja membuat halaman butuh waktu terlalu lama untuk memprosesnya
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Sumber: https://stackoverflow.com/a/3809435/623763

    • Ekspresi seperti (...){1,256} sangat berat, dan kode Scala JS pada akhirnya akan timeout atau membuat browser mati
      Kalau itu diganti menjadi (...)+, setidaknya di lingkungan saya bisa berjalan. Ekspresi kecil seperti (...){1,6} sepertinya baik-baik saja

  • Saya sempat terkejut karena regex yang dihasilkan dari gabungan dan irisan tidak terlalu ringkas, tetapi segera bisa memahaminya
    Misalnya, irisan dari "y.+" dan ".+z" bisa ditulis dengan ekspresi yang sangat sederhana, yaitu "y.*z", dan kesetaraannya juga bisa dikonfirmasi lewat halaman tersebut. Namun alat ini menghasilkan yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*
    Pasti ada alasan mengapa hasil seperti ini muncul, tetapi kemungkinan menghasilkan regex minimal berdasarkan kriteria seperti jumlah karakter jauh lebih sulit

    • Salah satu alasannya mungkin karena ".+z" menjadi lebih besar dan berantakan setelah diubah menjadi automaton deterministik

  • Dulu saya pernah memakai konsep ini untuk menulis logika validasi pada pengaturan “IP RegEx filter”
    Tujuannya adalah memungkinkan pengguna mengatur filter IP dengan regex. Tim marketing tidak memahami CIDR, tetapi mereka tahu regex karena Google Analytics
    Bagaimana cara mendefinisikan regex yang valid? Irisannya dengan regex “semua alamat IPv4” tidak boleh kosong, dan pada saat yang sama juga tidak boleh sama dengan regex “semua alamat IPv4”
    Ini banyak mencegah keluhan bahwa filter tidak melakukan apa-apa, tetapi tidak mencegah input filter yang keliru itu sendiri

    • Mungkin ada solusi yang lebih sederhana? Daripada mencoba memvalidasi regex filter, cukup tampilkan contoh alamat IP, atau biarkan pengguna memasukkan sekumpulan alamat lalu tunjukkan alamat mana yang cocok dan mana yang tidak
      Ini juga membantu menangani masalah filter yang keliru

  • Agar lebih nyaman dipakai di mobile, sebaiknya matikan saran otomatis pada field input regex
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Saya menguji halaman dengan 2 regex untuk angka yang habis dibagi 3 yang serupa, dan meski ^ serta $ di kedua ujungnya dihapus, halaman tetap berhenti
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    Semuanya berhasil di-parse sampai tepat sebelum * terakhir, tetapi begitu * ditambahkan, seluruh halaman berhenti
    Tanpa *, halaman menghasilkan validator yang valid untuk mem-parse potongan angka yang jumlah digitnya habis dibagi 3