Show HN: Metin düzenleme için Transductive düzenli ifadeler

 (github.com/c0stya)
1 puan yazan GN⁺ 2025-02-09 | 1 yorum | WhatsApp'ta paylaş
  • TRRE, düzenli ifadelere metin dönüşümlerini doğrudan ifade eden : operatörünü ekleyen bir dil uzantısıdır; bunu denemek için grep -E benzeri CLI aracı trre olarak sunuluyor
  • Temel biçim, a:b gibi bir giriş desenini çıkış desenine dönüştüren transductive pair’dir; silme x:, ekleme ise :x şeklinde boş string ile yapılan dönüşüm olarak ifade edilir
  • Normal düzenli ifadelerdeki gibi alternation, tekrar ve karakter aralığı dönüşümleri kullanılabilir; cat:dog, [a:A-z:Z] ve Caesar cipher gibi örnekler içerir
  • İç uygulama, normal düzenli ifadelerdeki FSA yerine giriş-çıkış çiftlerini işleyen bir Finite State Transducer(FST) kurar; deneysel on-the-fly determinization desteği de vardır
  • Şu anda önceden derlenmiş binary yok; elle derlemek gerekiyor. DFT’nin kararlı hâle getirilmesi, tam Unicode desteği, ERE özelliklerinin tamamlanması ve verimli aralık işleme gibi konular TODO olarak duruyor

TRRE’nin çözmeye çalıştığı sorun

  • Normal düzenli ifadeler, metinde desen bulmak için kullanışlıdır; ancak metin düzenlemede grup işleme mantığı sonradan yapılan işleme gibi çalıştığı için karmaşıklaşabilir
  • TRRE, desen eşleştirme ile metin değiştirmeyi aynı ifadenin içine koymak için düzenli ifade dilini genişletir
  • Temel sözdizimi pattern-to-match:pattern-to-generate biçimindedir; en basit örnek a:b olup ayı bye dönüştürür
  • CLI aracı trre, bu kavramı gösteren bir uygulamadır ve grep -Eye benzer bir hisle çalışır

Temel dönüşüm sözdizimi

  • String değiştirme cat:dog şeklinde yazılır
    • echo 'cat' | ./trre 'cat:dog', dog çıktısı verir
    • (c:d)(a:o)(t:g) gibi karakter bazlı dönüşümle de aynı sonuç üretilebilir
  • sed gibi bir string içindeki tüm eşleşmeleri değiştirmek için kullanılabilir
    • Mary had a little lamb. üzerinde lamb:cat uygulanırsa sonuç Mary had a little cat. olur
  • Silme, sağ taraf boş bırakılarak string_to_delete: biçiminde ifade edilir
    • (x:)or, xor içinden xi kaldırıp or üretir
    • a:, varsayılan scan mode’da tüm aları boş sembole dönüştürerek siler
    • [aie]: gibi köşeli parantez ifadesi kullanılarak birden çok karakter silinebilir
  • Ekleme, sol taraf boş bırakılarak :string_to_insert biçiminde ifade edilir
    • (:x)or, or önüne x ekleyip xor üretir
    • had a (:little )lamb, bağlam içinde little ekler

Düzenli ifadeler üzerinde dönüşüm

  • TRRE, normal düzenli ifadelerdeki gibi | ile alternation destekler
    • (c:b)at|(d:h)og, cat dogu bat hoga dönüştürür
  • Tekrar operatörleri de dönüşümlere uygulanabilir
    • (cat:dog)*, catcatcati dogdogdoga dönüştürür
    • Varsayılan scan mode’da yalnızca cat:dog da tekrar tekrar uygulanarak aynı sonucu üretebilir
  • Sol desende tekrar kullanıldığında birden fazla giriş tüketilip tek bir çıkışa dönüştürülebilir
    • (cat)*:dog, catcatcati doga dönüştürür
  • Sağ desende * veya + kullanmak sonsuz döngüye yol açabilir
    • :a* gibi ifadelerden kaçınılmalıdır
    • Sonlu tekrar gerekiyorsa :(repeat-10-times){10} gibi tekrar sayısı belirtilir

Aralık dönüşümü ve üreticiler

  • Karakter aralığı dönüşümü [a:A-z:Z] şeklinde yazılır
    • regular expressions, REGULAR EXPRESSIONSa dönüştürülebilir
  • Caesar cipher örneği içerir
    • [a:b-y:zz:a], caesar cipherı dbftbs djqifse dönüştürür
    • [a:zb:a-z:y], bunu tekrar caesar ciphera geri çevirir
  • generator gibi tek bir girişten birden fazla çıkış da üretilebilir
    • Varsayılan olarak mümkün olan ilk eşleşme kullanılır
    • -a seçeneği kullanılırsa mümkün olan tüm çıktılar üretilir
  • Örnek olarak boş girdiye :(0|1){3} uygulanırsa 000dan 111e kadar 3 bitlik ikili diziler üretilebilir
  • :(0|1){,3}? ile -ma birlikte kullanılırsa uzunluğu 3 veya daha az olan alt küme biçimli çıktılar üretilir

Dil spesifikasyonu ve operatör önceliği

  • Gayriresmî olarak TRRE, pattern-to-match:pattern-to-generate çiftleriyle tanımlanır
  • Soldaki pattern-to-match bir string veya düzenli ifade olabilir
  • Sağdaki pattern-to-generate genellikle string’dir, ancak düzenli ifade de olabilir
  • : operatörü şu anda ilişkisiz/non-associative kabul edilir; TRRE:TRRE biçimine sözdizimsel olarak izin verilmez
    • Bu biçim, TRRE’nin tanımladığı ilişkinin bileşimi gibi doğal bir anlama sahip olsa da karmaşıklığı artırabileceği için şimdilik dışarıda bırakılmıştır
  • Operatör önceliği yüksekten düşüğe şöyledir
    • Escape karakteri \
    • Köşeli parantez ifadesi []
    • Gruplama ()
    • Tekrar * + ? {m,n}
    • Birleştirme
    • Transduction :
    • Alternation |

Modlar ve greediness

  • trre iki modu destekler
    • Scan Mode: Varsayılan moddur; dönüşümleri sırayla uygular
    • Match Mode: -m bayrağıyla kullanılır ve tüm string’in ifadeyle eşleşip eşleşmediğini kontrol eder
  • -a seçeneği mümkün olan tüm çıktıları üretir
  • ? değiştiricisi *, +, {,} operatörlerini non-greedy hâle getirir
    • <(.:)*>, <cat><dog> girdisinde <> çıktısı verir
    • <(.:)*?>, aynı girdide <><> çıktısı verir
  • Etiketlerin veya parantezlerin içeriğini değiştiren örnekler de bulunur
    • <(.*?:cat)>, <dog> <mouse>u <cat> <cat>e dönüştürür

FST tabanlı uygulama ve determinization

  • TRRE içeride bir Finite State Transducer(FST) kurar
  • FST, normal düzenli ifadelerde kullanılan Finite State Automaton(FSA) ile benzerdir; ancak basit string’ler yerine giriş-çıkış çiftlerini işler
  • TRRE’nin temel farkları şunlardır
    • İki düzenli dil arasında ikili ilişki tanımlar
    • Çıkarım için FSA yerine FST kullanır
    • Performans için deneysel on-the-fly determinization destekler
  • Normal regex motorlarında determinization, non-deterministic automata’yı deterministic automata’ya dönüştürerek giriş string’i uzunluğuna göre doğrusal zamanda çıkarımı mümkün kılar
  • TRRE’de de benzer bir yaklaşım mümkündür; ancak tüm non-deterministic transducer’lar NFT deterministic transducer DFT’ye dönüştürülemez
    • Aynı giriş etiketine sahip iki “bad” cycle varsa durum üretimi sonsuz döngüye girebilir
    • Bu tür döngüleri algılamanın yöntemleri vardır, ancak maliyetlidir

Performans ve kurulum durumu

  • Temel non-deterministic sürüm için basit değiştirmede sedden biraz yavaş bir örnek verilmiştir
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • Karmaşık işlerde deterministic sürüm trre_dft için sedden hızlı bir örnek vardır
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • Önceden derlenmiş binary’ler henüz sağlanmıyor
  • Kurulum, depoyu klonladıktan sonra make && sh test.sh ile derleyip test etme şeklindedir
  • TODO’da şu maddeler duruyor
    • Kararlı DFT sürümü
    • Tam Unicode desteği
    • ERE özelliklerinin tamamlanması
      • [] içinde olumsuzlama ^
      • Karakter sınıfları
      • $^ anchor sembolleri
    • Verimli aralık işleme

Referans alınan yaklaşımlar

İlgili okumalar

1 yorum

 
GN⁺ 2025-02-09
Hacker News yorumları

  • Bu projenin nereye gideceğini merak ediyorum. Ancak operatör önceliği doğal gelmiyor; bu başlıktaki başkaları da benzer hissetmiş gibi
    cat:dog ifadesinin doğal olarak ca(t:d)og değil, (cat):(dog) ile aynı olması beklenir

    • Birçok açıdan ilginç bir fikir
      cat:dog ifadesinin (cat):(dog) değil de ca(t:d)og gibi yorumlanması beni de şaşırtmıştı; ama herkesin regex’i biraz yanlış kullandığını düşününce anlam kazandı. Regex’i “aslında” bir eşleştirici değil, dize üreteci olarak görmek daha doğru; bu yüzden cat|dog biçimsel olarak {catog,cadog} gibi bir kümeye açılıyor diye düşünülebilir
      Eşleştirmede bu dize kümesini daha büyük bir metin içinde alt dize olarak eşleştirmek yeterli. Sorun şu ki gerçek regex motorlarının çoğu böyle çalışmıyor; beklentilere uymak veya verimlilik için türlü tuhaf davranışlar sergiliyorlar
      Çeşitli regex araçlarını denediğinizde (cat)|(dog) veya (cat)|(dog)|(ca[td]og) gibi varyasyonlar çıkıyor. Bu yüzden daha biçimsel bir bakış açısından cat:dog ifadesinin (cat):(dog) değil ca(t:d)og üretmesi doğru görünüyor. Ama onlarca yıl regex’i kullanıcı beklentilerine uydurulmuş bir eşleştirme aracı olarak kötüye kullandığımız için artık herkes değiştirmek istediği ifadeyi paranteze alıyor
      Bu öneri ilginç ve iyi tasarlanmış, ama sonuçta regex’i asıl üreteç modeline geri döndürmeye çalışıyormuş gibi hissettiriyor. Sorun sözdiziminden çok araç tarafına daha yakın
      Eskiden bu alana yakın işler yapmıştım; regex’i dize kümeleri üreteci olarak hiç düşünmediyseniz burada kurcalayabilirsiniz: https://onlinestringtools.com/generate-string-from-regex
      Yalnız bu tür üretim araçlarının davranışı da çok spesifik. Benim kullandığım araçlarda, closure vb. için kısıtlar belirleyerek üreteci sınırlamanın çeşitli yolları vardı
    • Geri bildirim için teşekkürler; öncelik konusunda ben de düşünüyorum, değişebilir
      Birleştirmenin arkasına atarsak başka sorunlar çıkabilir. Örneğin birleşmeli olmayan : için cat:dog:mouse belki geçersiz olmalı; bunu nasıl ele alacağımdan emin değilim
      Mevcut sürümde epsilon, yani boş dize ekliyor. Örneğin birer karakter atlayarak silmek için teknik olarak .(.:eps) olan ..: çalıştırılabilir
      echo 'abcde' | ./trre '..:' çıktısı 'ace' olur
      Aslında : birleşimi, düzenli ilişkilerin bileşimi anlamına da gelebilir; ama şu an bunun fazla karmaşık olduğunu düşündüm
    • Aralık dönüştürmeleri de benzer. [a:A-z:Z] yerine [a-z:A-Z] daha iyi; [a:b-y:zz:a] yerine de [a-y:b-z;z:a] gibi bir biçim önermek isterim

  • Sonlu durum dönüştürücüleri ve ilgili araçlarla ilgileniyorsanız XFST’ye (Xerox Finite-State Transducer) bakmaya değer. Hesaplamalı dilbilim uygulamalarında 20 yılı aşkın süredir kullanılıyor
    PARC’tan Finlandiyalı bir araştırmacı UT’deki bir derse gelip FST ile Fince morfolojisinin nasıl işlendiğini göstermişti; dışarıdan bakınca bile oldukça etkileyici bir işti

    • Ben de bundan bahsedecektim. Kaplan makalesinin bağlantısı: https://aclanthology.org/J94-3001.pdf
      PARC’ta yapılan çalışmayı anlatıyor
    • http://hfst.github.io/ XFST’nin modern açık kaynaklı sürümü. foma ve OpenFst’yi kapsıyor; trre’nin yaptığı işlerin neredeyse tamamını ve daha fazlasını yapabiliyor olmalı
    • Pynini de ilginizi çekebilir. OpenFst için bir Python sarmalayıcısı ve üzerine pek çok kullanım kolaylığı eklenmiş bir araç
      OpenFst, dönüştürücüler için gerçekten harika bir kütüphane. Johns Hopkins ve benzeri yerlerde ödev formatında hazırlanmış Pynini kullanım örneği eğitimleri de fena değil
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Standart regex’e alternatif arıyorsanız, özellikle grup mantığı zor geliyorsa veya bakımı yapılabilir ifadeler istiyorsanız Rosie Pattern Language size uygun olabilir
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Harika. 1997 civarında bilgisayar bilimleri Diplom tezimi sonlu durum dönüştürücüleri üzerine yazmıştım; beklediğimden çok daha az önemsizdi
    Görev, mümkün olan durumlarda bileşimi ve DFA’yı uygulamaktı; bileşik dönüştürücüler de dahildi. Konu “sonlu durum dönüştürücülerinin cebiri”ydi ve kullanım örneği morfolojiydi. Konu fazlasıyla hafife alındığı için ortalarda bir yerde bitirmek zorunda kalmıştım. O yüzden saygılar
    Sözdizimiyle ilgili olarak, gerçekten : işaretinin birleştirme ab’den daha sıkı bağlanmasını isteyip istemediğinizi merak ediyorum

    • 2000’lerin başında biyoinformatikte OpenFST kullanmıştım. Kurcalaması eğlenceliydi ama yaptığım iş için sonunda yararlı olmadı
      20 yıl sonra projenin hâlâ sürdüğünü görmek güzel: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • Mezun olup olmamayı fiilen “regex’i yeterince sert şekilde ele alabiliyor musun” sorusuna bağlamak inanılmaz cesur bir seçim
    • Doğru. Dönüştürücüler çok eski bir konu. Nedense regex gibi belirli bir dille güçlü biçimde ilişkilendirilmemişler
      : işaretinin birleştirmeden daha sıkı bağlanması gerekip gerekmediğinden hâlâ emin değilim. Yaklaşık 100 örneğe baktım ve mevcut yolun, yani : işaretinin . işaretinden daha düşük öncelikte olmasının daha doğal olduğunu düşündüm; ama kodda bunu değiştirmek kelimenin tam anlamıyla tek bir sayıyı değiştirmekten ibaret. Bu yüzden buraya koydum; gerçek geri bildirime ihtiyacım var

  • Bir tür yapısal değiştirme yapmaya çalıştığınız anda bu yaklaşım yeterli görünmüyor. Örneğin s/"([^"]*)"/'$1'/ gibi bir şey yapmak istediğiniz zamanlar oluyor
    Buna ek olarak, [^"] içindeki ['] ile eşleşenleri \' ile değiştirebilse daha da kullanışlı görünür
    Daha genel olarak, regex eşleşme sonucu için fiilen bir parse tree tanımladığına göre, o ağaç üzerinde daha genel dönüşümler yapabilmek faydalı olurdu

    • Doğru anladıysam şu ttre ifadesi istediğinizi yapıyor:
      ":'(':(\\')|[^"'])*":'
    • Doğru anladıysam "..." bloğunun içeriğini değiştirmek ve tırnakları tek tırnak ' yapmak istiyorsunuz
      Bu ifadeyle mümkün:
      echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"
      Sonuç '-' '-' olur
      Yani ".+?:-" ifadesiyle "" içindeki metni - işaretiyle değiştirirken aynı anda çevredeki tırnakları da değiştirir. Soru işareti non-greedy mod anlamına gelir

  • “Regex, metinde desen bulmak için harika bir araçtır ama metin düzenleme için bana hep yapay gelmiştir” iddiası projenin tamamının dayandığı şey gibi görünüyor, ama ortada tek bir örnek bile yok
    Regex’in düzenleme için neden yapay olduğunu anlamıyorum. Burada düzenlemenin ne anlama geldiğini de bilmiyorum; insanların gruplarda neden zorlandığını da bilmiyorum
    Bu projenin söz dizimi örneği çok, ama neden sıradan regex’ten daha iyi olduğunu bilmiyorum. “Temel regex sürümü şöyle, benim sürümüm şöyle, bu yüzden daha kolay” diyen birkaç örnek olursa projeyi anlayabilirim

    • Regex’in genelde bir kez yazılıp bir daha düzeltilmeyen bir karakteri olduğunu düşünüyorum. Bunun ötesini görmeye çalışan bir prototip yapmak, bu alanın daha iyi geleceğini keşfetmek için iyi bir yol
    • Yerinde bir nokta. En belirgin örnek, yalnızca bağlam içinde değiştirme gerektiği zaman
      Örneğin x ile z arasında bulunan yalnızca y’yi Y ile değiştirmek için Python’da kabaca şöyle yapılır:
      pattern = r'(x)y(z)'
      replacement = r'\1Y\2'
      result = re.sub(pattern, replacement, text)
      Ben bunu xy:Yz deseniyle değiştirmek istiyorum:
      result = re.trre('xy:Yz', text)
      x ve z daha karmaşık desenlerse ya da regex’in kendisiyse bu yaklaşım daha rahat olabilir
    • Regex’in tek başına düzenleme işlevi sağlamadığını söylemek daha doğru. Gruplar var, ama o grupları birleştirmek için sed gibi başka bir dil kullanmanız gerekiyor
    • Konu değiştirme. Yazarın söz dizimiyle değiştirmeyi ifade etmek, kelimenin tam anlamıyla yazmak, daha kolay
      Güzel proje

  • C kodunu okumak gerçekten keyifli. Çok iyi, şu anda okuyorum
    Sadece kısa bir yorum: README’deki theory.pdf bağlantısı bozuk. PDF docs/ dizininde, URL’ye yalnızca docs/ eklemek yeterli

    • Geri bildirim ve yazım hatası uyarısı için teşekkürler. Düzelttim. Aslında C becerilerim epey paslandı, bu yüzden biraz tedirginim

  • Sağ tarafta * veya + kullanmanın sonsuz döngüye yol açabileceği, bu yüzden kaçınılması gerektiği yazıyor; peki bunları doğrudan yasaklamak olmaz mı?
    Söz dizimi tanımının daha zorlaşacağını anlıyorum, ama elde tutmak için iyi bir neden yok gibi görünüyor

    • Yerinde bir nokta ve katılıyorum. Şimdilik devre dışı bırakmak daha iyi olur
      Asıl neden, dönüştürücü bileşimi denen ilginç bir işlemi hayata geçirmek istememdi. Dizgiler üzerinde basit işlemler yapıp trre’yi bir filtre gibi birleştirebilirsiniz, ama henüz tamamlayamadım. Dolayısıyla evet, yerinde bir nokta

  • Güzel bir araştırma, ama pratikte neden daha iyi olduğuna dair örnekler eksik. Elbette regex’e çok uzun süredir alışık olduğum için de böyle geliyor olabilir
    Örneğin trre’deki (cat):(dog) ifadesinin s/cat/dogdan neden daha iyi olduğunu, (x:)orun s/xor/ordan ne açıdan iyi olduğunu bilmiyorum. Neredeyse tüm örnekler zihnimde görece kolay regex karşılıklarına oturuyor
    Temel bir avantaj varsa bunun grup mantığı tarafında olacağını düşünüyorum; örneklerin de o tarafa odaklanması iyi olur. Temel söz dizimini anlatmadan önce, bunun neden daha iyi bir tercih olduğunu açıklamak daha iyi görünüyor
    Sezar şifresi örneğinde “bunu ters yönde uygula” işlevine ciddi ihtiyaç var gibi görünüyor. Birçok metin değiştirme işleminde yaygın bir istek ve bu örnekte özellikle çok açık. Programcı zihni hemen “aynı mantığı neden iki kez ifade etmek zorundayım?” diye bağırıyor
    Henüz faydalı olup olmadığını bilmiyorum, ama köklü statükoya alternatifleri araştırmak harika. Genelde bu tür denemelerin başarılı olmama ihtimali yüksek olsa da, araştırmanın kendisini görmek güzel

  • Belirtim oldukça yetersiz görünüyor. Daha ilk örnek garip:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    Burada ne olduğunu anlamıyorum. Sözdizimi şöyle verilmiş:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    Buradaki parse ağacı nedir? Neden c, daya dönüşmüyor? Ya da neden c silinip da, otye dönüşmüyor?
    Grup operatöründen daha sezgisel bir arama/değiştirme anlamına sahip olma fikri güzel. MS-DOS zamanında ren .log .txt gibi bir şey yapabiliyordunuz ve çalışıyordu; modern bash tarzı düşünceyle saçma ama bakınca niyet son derece açıktı

    • Bu, operatör önceliği ve tokenleştirme meselesi. Bu dilde token'lar tek karakterden oluşuyor ve karakterler arasında görünmez bir operatör var.
      O operatörü açıkça ~ diye adlandırırsak örnek şöyle görünür:
      $ echo 'cat' | trre 'c:d~a:o~t:g'
      dog
      Gereksiz parantezleri eklersek şöyle olur:
      $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
      dog
    • Dilbilgisi belirtimi yetersiz. Tam dilbilgisi daha karmaşık. Mevcut sürümü belgelerden kaldırmak gerekebilir; şu an gerçekten kafa karıştırıyor.
      cnin neden daya dönüşmediği tamamen önceliklerle ilgili. Bu tartışmaya bakınca yanlış önceliği seçmişim gibi geliyor ve bu da kafa karışıklığı yaratıyor.
      Mevcut öncelik tablosu şöyle:
      | 1 | kaçış karakteri | \ |
      | 2 | köşeli parantez ifadesi | [] |
      | 3 | gruplama | () |
      | 4 | tek karakter ERE tekrarı | * + ? {m,n} |
      | 5 | dönüşüm | : |
      | 6 | birleştirme | . (örtük) |
      | 8 | seçim | | |
      Yani :, .den, yani örtük birleştirmeden daha sıkı bağlanıyor.
    • Evet, belirtim yetersiz. Silme örneği boş dizgenin de REGEX olabileceğini gösteriyor. O zaman fiilen herhangi bir konumda istenildiği kadar çok boş dizge regex'i bulunduğu düşünülebilir; bu yüzden sonsuz sayıda parse oluşuyor.
      Bunun yerine regex'in boş olmamasını şart koşarsanız silme örneği bozulur, ama belirsizlik birleştirme tarafına kayar. Yani (((c:d)(a:o))(t:g)) mi yoksa ((c:d)((a:o)(d:g))) mi olduğu belirsizleşir. Birleşme yönü varsayılırsa bu fark önemli olmayacaktır.
    • Davranış hissi olarak c:d, a: yani hiçlik ve ot:g gibi görünüyor.
      Ama yeniden okuyunca gerçekten kafa karıştırıcı olduğu kesin ve teorik olarak itiraz haklı. Depoyu okuduktan sonra ben de cnin daya dönüşmesi gerektiğine inanmaya başladım, ama emin değilim.