İki düzenli ifadenin farkını ve kesişimini hesaplama

 (phylactery.org)
2 puan yazan GN⁺ 2023-09-12 | 1 yorum | WhatsApp'ta paylaş
  • Düzenli ifadeleri bir string kümesi gibi karşılaştırmak gerektiğinde antimirov, iki ifade α ve β arasındaki kapsama ilişkisini, eşdeğerliği, kesişimi ve fark kümesini tek ekranda hesaplar
  • Sonuç alanı tümleyen ve ilişki ifadelerini birlikte gösterir; ~α, α < β, α = β, α & β, α ^ β, α - β gibi işlemler incelenebilir
  • Ayrı bir string s girildiğinde s ∈ α, s ∈ β ile her düzenli ifadenin eşleşip eşleşmediği anında doğrulanabilir
  • Sözdizimi ., birleştirme, seçim |, tekrar *·+·?·{n}·{m,n}, karakter grupları, olumsuz karakter grupları, escape ve UTF-16 Unicode escape dizilerini destekler
  • Anchor'lar, sıfır genişlikli assertion'lar, backreference'lar, alt grup çıkarma, arama/kısmi eşleşme, büyük-küçük harf duyarsızlığı gibi davranış değiştiren özellikler desteklenmez

Düzenli ifade karşılaştırması ve küme işlemleri

  • Giriş alanı iki düzenli ifade α ve β alır
  • Çıktı, iki düzenli ifadenin tümleyenini ve ilişki/küme işlemlerini birlikte gösterir
    • ~α, ~β: her düzenli ifadenin tümleyeni
    • α < β, α = β, α > β: iki düzenli ifade arasındaki kapsama ilişkisi ve eşdeğerlik
    • α & β: kesişim
    • α ^ β: simetrik fark
    • α - β: fark kümesi
  • String s girildiğinde s ∈ α, s ∈ β biçiminde her düzenli ifadeye ait olup olmadığı kontrol edilebilir
  • Her düzenli ifadenin boyutu ve DFA durum sayısı da gösterilir
    • Örnek ekranda |α| = 1, |β| = 1
    • Örnek ekranda dfa(α) ve dfa(β) ayrı ayrı 1 duruma sahiptir

Desteklenen düzenli ifade sözdizimi

  • Temel işleçler tek karakter, birleştirme, seçim ve tekrarı kapsar
    • .: herhangi bir tek karakterle eşleşir
    • xy: x sonrasında y ile eşleşen birleştirme
    • x|y: x veya y ile eşleşir
    • x*: 0 veya daha fazla tekrar
    • (xyz): gruplama
    • (): boş string ile eşleşen boş düzenli ifade
  • Sık kullanılan tekrar kısaltmaları da desteklenir
    • x+: 1 veya daha fazla tekrar, xx* ile eşdeğerdir
    • x?: isteğe bağlı eşleşme, (x|) ile eşdeğerdir
    • x{n}: x ifadesini n kez birleştirir
    • x{m,n}: x ifadesini en az m, en çok n kez birleştirir
  • Karakter kümeleri ve escape kullanımı şu biçimleri destekler
    • [a-z0-9]: grup içindeki tek bir karakterle eşleşir
    • [^a-z0-9]: grup içinde olmayan tek bir karakterle eşleşir
    • \\c: özel karakter c için escape
    • \\u001a: karşılık gelen UTF-16 karakteriyle eşleşir
    • Bunun dışında a, b, c gibi karakterler kendileriyle eşleşir

Desteklenmeyen özellikler

  • antimirov, düzenli ifadeleri küme işlemlerinin konusu olarak ele almaya odaklanır ve şu özellikleri dışarıda bırakır
    • Anchor'lar ^, $
      • Ancak ^ ve $ yine de escape edilmelidir
    • Sıfır genişlikli assertion örnekleri: (?=...), (?<=...)
    • Backreference örnekleri: \\1, \\2
    • Alt grup çıkarma
    • Arama veya kısmi eşleşme
    • Büyük-küçük harf duyarsızlığı gibi davranışı değiştiren diğer flag'ler
  • Daha fazla bilgi için non/antimirov sayfasına bakabilirsiniz

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-12
Hacker News yorumları

  • Regex’in ayrıştırma → NFA → DFA → minimal DFA sürecinden nasıl geçtiğini gösteren ve minimal DFA’dan LLVM IR/Javascript/WebAssembly çıktısı da üreten benzer bir web demosu yapmıştım
    http://compiler.org/reason-re-nfa/src/index.html

  • Bu kütüphane string sınıf hiyerarşileri oluşturmak için kullanılabilir; bunun sonucunda tipli string’lerden daha etkin biçimde yararlanılabilir
    Örneğin e-posta ve URL’lerin özel sözdizimleri vardır; değer uzayları boş olmayan tüm string’lerin bir alt kümesidir, boş olmayan string’ler de tüm string’lerin bir alt kümesidir
    Tip sistemi bir e-posta string’inin boş olmayan string’in alt tipi olduğunu bilirse, e-posta adresini boş olmayan string isteyen bir fonksiyona vermenin geçerli olduğuna karar verebilir
    Bu kütüphane böyle string tiplerinin tanımını ve hiyerarşisini doğrulamak için kullanılabilir; hiyerarşinin uygulanması ise dile göre alt sınıflama, trait sınırları vb. biçimlerde değişir

    • Etiketli birleşim tipleri olan dillerde bu yaklaşım sık kullanılır. Haskell tarzı sözde kod kabaca şöyle olurdu
      Address oluşturucusu dışa aktarılmaz, yalnızca tip dışa aktarılır; fromString :: Text -> Maybe Address içinde doğrulama yapılır ve geçersiz adresse Nothing döner
      Geçerliliği verinin içine karıştırmak yerine ayrı bir yoldan sinyal olarak iletmek gerekir; çıktı gerektiğinde de toText :: Address -> Text ile sarmalanmış değer geri alınır
    • E-posta adresi doğrulamak için regex kullanmamak daha iyi
      https://news.ycombinator.com/item?id=31092912
    • Geç yaz sabahında @ işaretinin solunda e-posta adresi olarak nelerin kabul edilip edilmediğine dalmak kadar tuhaf pek az şey vardır
      “Geçerli e-posta adresi”ni ifade etmeye çalışan her regex’in yanlış olduğunu varsayan basit sezgisel kural epey güvenlidir, ama bütün eğlenceyi de mahveder
    • “Değer uzayı” ile ne kastedildiğini merak ediyorum

  • Regex’ler, oldukça etkileyici ve karmaşık bir matematik teorisini değerli bir arayüzle paketlemenin iyi bir örneği
    Lineer cebir de benzer hissettiriyor

    • Uygun bir cisim verildiğinde matematiğin gerçekten büyük bir kısmının lineer cebire dönüştürülebilmesi beni hep şaşırtıyor
      Karmaşık düzlemdeki Möbius dönüşümü w=(az+b)/(cz+d) bile lineer cebire dönüştürülebilir
    • Genellikle bu tür durumlarda, temsilin hakikate daha da yaklaştığı anlamına gelir
      İyi arayüzlerin özünde bir değeri vardır; sonuç odaklı birçok insan bunu pek kabul etmez
    • Yanlış hatırlamıyorsam Conway’in https://store.doverpublications.com/0486485838.html kitabında lineer cebirle bağlantı geçiyordu. Sadece kabaca göz atmıştım

  • Bu harika sayfa, regex çiftleri arasındaki ikili ilişkileri hesaplıyor ve DFA’yı grafik olarak gösteriyor
    Regex’ler üzerinde gerçekleştirilen oldukça gayri basit işlemleri gerçekten etkileyici biçimde sergiliyor

    • Çok güzel, ama açıkçası artık regex olmaktan çıkaran özellikleri desteklememesi şaşırtıcı değil
      Yine de ^ ve $ ankrajlarının sorun olmayacağını sanmıştım

  • “regex filter numbers divisible by 3” ifadesini yapıştırınca sayfa tamamen dondu: 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])))+$
    Daha kısa bir ifade var mı merak ediyorum

    • Bu web sayfası, çok sayıda duruma sahip DFA üreten regex’lerde takılıyor
      Örneğin (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog gibi
    • Zaten sayfanın açıklamasına göre ankrajlar desteklenmiyor

  • Sözdizimsel olarak geçerli URL’ler ile e-posta adreslerinin kesişimini görmek istemiştim, ama aşağıdaki URL regex’ini tek başına girmek bile sayfanın işlemesi için çok uzun sürüyor
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Kaynak: https://stackoverflow.com/a/3809435/623763

    • (...){1,256} gibi ifadeler çok ağır; Scala JS kodu sonunda zaman aşımına uğruyor ya da tarayıcıyı öldürüyor
      Onu (...)+ ile değiştirince en azından benim ortamımda çalışıyor. (...){1,6} gibi küçük ifadeler muhtemelen sorun olmaz

  • Birleşim ve kesişimle üretilen regex’in özellikle kısa olmamasına şaşırdım, sonra hemen makul geldi
    Örneğin "y.+" ile ".+z" kesişimi "y.*z" gibi çok basit bir ifadeyle yazılabilir ve sayfa da eşdeğerliği doğruluyor. Ama araç yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* çıktısını veriyor
    Böyle bir sonucun çıkmasının nedenleri vardır elbette, ama karakter sayısı gibi bir kritere göre minimal regex üretmek muhtemelen çok daha zordur

    • Nedenlerden biri, ".+z" ifadesinin deterministik otomatona dönüştürüldükten sonra daha büyük ve dağınık hâle gelmesi olabilir

  • Daha önce bu kavramı kullanarak “IP RegEx filter” ayarının doğrulama mantığını yazmıştım
    Amaç, kullanıcıların IP filtresini regex ile ayarlamasını sağlamaktı. Pazarlama tarafı CIDR’ı anlamıyordu; Google Analytics yüzünden regex’i ise biliyorlardı
    Geçerli bir regex nasıl tanımlanabilirdi? “Tüm IPv4 adresleri” regex’iyle kesişimi boş olmamalı, aynı zamanda “tüm IPv4 adresleri” regex’ine de eşit olmamalıydı
    Filtrenin hiçbir işe yaramadığı yönündeki şikâyetlerin çoğunu engelledi, ama hatalı filtre girişlerinin kendisini engelleyemedi

    • Daha basit bir çözüm de mümkün olmaz mıydı? Filtre regex’ini doğrulamaya çalışmak yerine, örnek IP adresleri gösterilebilir ya da kullanıcıdan bir adres kümesi girmesi istenip hangi adreslerin eşleştiği, hangilerinin eşleşmediği gösterilebilirdi
      Bu, hatalı filtre sorununu ele almaya da yardımcı olurdu

  • Mobilde daha kullanışlı olması için regex giriş alanında otomatik önerileri kapatmak iyi olur
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Benzer iki 3’e bölünebilen sayı regex’i ile sayfayı test ettim; baştaki ve sondaki ^ ile $ kaldırıldığında bile sayfa dondu
    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])))*
    Son * işaretinin hemen öncesine kadar her şey parse ediliyor, ama * eklenir eklenmez tüm sayfa donuyor
    * olmadan, rakamları toplamı 3’e bölünebilen sayı parçalarını parse eden geçerli bir doğrulayıcı oluşturmuştu