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

• TRRE: Dönüşümlü düzenli ifadeler

• Özet

  • Metin düzenleme ve grep benzeri komut satırı araçları için düzenli ifadelerin bir uzantısıdır.
  • Bir prototip olduğu için gerçek ortamlarda kullanılmamalıdır.

• Giriş

  • Düzenli ifadeler, metin içinde desen aramak için kullanışlı araçlardır.
  • Metin düzenleme için doğal olmadığı düşünülerek bir uzantı önerilmektedir.
  • Buna dönüşümlü düzenli ifadeler ya da trre denir.
  • Dönüşümleri tanımlamak için : simgesi kullanılır.
  • a:b, a'yı b ile değiştiren en basit biçimdir.
  • Kavramı göstermek için trre adlı bir komut satırı aracı oluşturulmuştur.

• Örnekler

  • Temel

    • cat ifadesini dog olarak değiştir:

      $ echo 'cat' | trre 'c:da:ot:g'
      dog
      

    • sed gibi, bir dizgedeki tüm eşleşmeleri değiştir:

      $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
      Mary had a little cat.
      

    • Silme:

      $ echo 'xor' | trre '(x:)or'
      or
      

    • Ekleme:

      $ echo 'or' | trre '(:x)or'
      xor
      

  • Dönüşüm yoluyla düzenli ifadeler

    • Alternation kullanımı:

      $ echo 'cat dog' | trre 'c:bat|d:hog'
      bat hog
      

    • Dönüşümü yinelemek için star kullanımı:

      $ echo 'catcatcat' | trre '((cat):(dog))*'
      dogdogdog
      

  • Aralık dönüşümü

    • Karakter aralığı dönüşümü:

      $ echo "regular expressions" | trre "[a:A-z:Z]"
      REGULAR EXPRESSIONS
      

  • Üreteç

    • trre, tek bir girdi için birden çok çıktı dizgesi üretebilir.
    • İkili dizi:

      $ echo '' | trre -ma ':(0|1){3}'
      000  001  010  011  100  101  110  111
      

• Dil belirtimi

  • trre, desen-eşleme:desen-üretme çifti olarak tanımlanır.
  • desen-eşleme bir dizge ya da düzenli ifade olabilir.
  • desen-üretme genellikle bir dizgedir, ancak regex de olabilir.

• Neden çalışıyor

  • trre, sonlu durum dönüştürücüsü (FST) denilen özel bir otomat kurar.
  • FST, girdi-çıktı çiftlerini işler.

• Tasarım seçimleri ve açık sorular

  • : işlecinin bağlaşıklığı, önceliği, örtük epsilon gibi çeşitli kararlar gereklidir.

• Modlar ve açgözlülük

  • trre iki modu destekler:
    • Tarama modu (varsayılan): dönüşümleri sırayla uygular.
    • Eşleşme modu: ifadenin tüm dizgeyi kapsayıp kapsamadığını denetler.

• Determinizasyon

  • Belirlenimsiz bir otomatı belirlenimli bir otomata dönüştürme süreci önemlidir.

• Performans

  • NFT (belirlenimsiz) sürüm, sed'den biraz daha yavaştır.
  • Karmaşık işlerde trre_dft (belirlenimli sürüm), sed'den daha iyi performans gösterebilir.

• TODO

  • ERE özellik kümesinin tamamlanması, tam Unicode desteği, verimli aralık işleme vb.

• Kaynakça

  • Russ Cox'un makaleleri ile Cyril Allauzen ve Mehryar Mohri'nin çalışmalarından esinlenilmiştir.

[GN⁺]

Hacker News yorumu

• Güzel, bu projenin gelişimini merakla bekliyorum

  • Operatör önceliğinin doğal gelmediğini düşünüyorum
  • cat:dog ifadesinin (cat):(dog) yerine ca(t:d)og olarak yorumlanması tuhaf

• XFST'yi (Xerox Finite-State Transducer) öneriyorum

  • 20 yılı aşkın süredir bilgisayarlı dilbilimde kullanılan bir araç
  • Fince biçimbirim çözümlemesinde FST kullanıldığı örnekler duydum

• Standart düzenli ifadelere alternatif olarak Rosie Pattern Language öneriliyor

  • Grup mantığında zorlananlar için bakımı daha kolay bir alternatif olabilir
  • İlgili bağlantılar: GitLab, Rosie resmi sitesi

• 1997'de sonlu durum dönüştürücüleri üzerine bir makale yazma deneyimi paylaşılıyor

  • Konu biçimbirim çözümlemesiydi ve yeterince değer verilmeyen bir alandı
  • Sözdiziminde : işlecinin ab'den daha güçlü bağlanacak şekilde ayarlanmasının doğru olup olmadığı soruluyor

• Yapısal ikame yaparken bunun yeterli gelmediğini düşünüyorum

  • Düzenli ifade eşleşen kısım için bir sözdizim ağacı tanımladığına göre, ağacın genel dönüşümlerini yapabilmek faydalı olurdu

• Düzenli ifadelerin metin düzenleme için doğal olmadığı iddiasını sorguluyorum

  • Projenin amacı bu iddiaya dayanıyor gibi görünüyor ama örnek yok
  • İnsanların grup kullanırken neden zorlandığını anlayamıyorum
  • Bu projenin dil bilgisinin düzenli ifadelerden neden daha iyi olduğunu gösteren örneklere ihtiyaç var

• C kodu çok temiz görünüyor

  • README içindeki theory.pdf bağlantısı hatalı, düzeltilmesi gerekiyor

• * veya + kullanılmaması yönündeki tavsiyeyi sorguluyorum

  • Dil bilgisini daha karmaşık hale getirebilir ama bunlara izin vermemek daha iyi olabilir

• İlk örnek bana tuhaf geldi

  • echo 'cat' | trre 'c:da:ot:g' çıktısı garip görünüyor
  • Sözdizim ağacının nasıl kurulduğunu anlamak zor
  • MS-DOS dönemindeki ara/bul-değiştir yaklaşımı daha sezgisel geliyor

• Örneklerin gerçekten program çıktısı olup olmadığını merak ediyorum

  • Dil bilgisini yeterince anlamamış olabilirim ama örnekler hatalı görünüyor
  • echo 'cat dog' | trre 'c:bat|d:hog' çıktısı tuhaf