Show HN: Ekspresi reguler transduktif untuk penyuntingan teks

• TRRE: Ekspresi reguler transduktif

• Ringkasan

  • Ini adalah perluasan ekspresi reguler untuk penyuntingan teks dan alat baris perintah yang mirip grep.
  • Karena ini masih prototipe, jangan gunakan di lingkungan produksi.

• Pengantar

  • Ekspresi reguler adalah alat yang berguna untuk mencari pola dalam teks.
  • Karena terasa kurang alami untuk penyuntingan teks, sebuah perluasan diusulkan.
  • Ini disebut ekspresi reguler transduktif atau trre.
  • Simbol : digunakan untuk mendefinisikan transformasi.
  • a:b adalah bentuk paling sederhana yang mengganti a dengan b.
  • Sebuah alat baris perintah bernama trre dibuat untuk mendemonstrasikan konsep ini.

• Contoh

  • Dasar

    • Mengubah cat menjadi dog:

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

    • Mengganti semua kecocokan string seperti sed:

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

    • Penghapusan:

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

    • Penyisipan:

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

  • Ekspresi reguler melalui transformasi

    • Menggunakan alternasi:

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

    • Menggunakan star untuk mengulang transformasi:

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

  • Transformasi rentang

    • Transformasi rentang karakter:

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

  • Generator

    • trre dapat menghasilkan beberapa string keluaran untuk satu masukan.
    • Urutan biner:

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

• Spesifikasi bahasa

  • trre didefinisikan sebagai pasangan pattern-matching:pattern-generation.
  • pattern-matching dapat berupa string atau ekspresi reguler.
  • pattern-generation biasanya berupa string tetapi juga bisa berupa regex.

• Mengapa ini bekerja

  • trre membangun automata khusus yang disebut finite-state transducer (FST).
  • FST memproses pasangan input-output.

• Pilihan desain dan pertanyaan terbuka

  • Beberapa keputusan diperlukan terkait asosiativitas :, prioritas, epsilon implisit, dan lainnya.

• Mode dan greedy

  • trre mendukung dua mode:
    • Mode scan (default): menerapkan transformasi secara berurutan.
    • Mode match: memeriksa seluruh string terhadap ekspresi.

• Determinisasi

  • Proses mengubah automata nondeterministik menjadi automata deterministik itu penting.

• Kinerja

  • Versi NFT (nondeterministik) sedikit lebih lambat daripada sed.
  • Pada tugas yang kompleks, trre_dft (versi deterministik) bisa memiliki kinerja lebih baik daripada sed.

• TODO

  • Menyelesaikan set fitur ERE, dukungan Unicode penuh, penanganan rentang yang efisien, dan lain-lain.

• Referensi

  • Terinspirasi oleh artikel Russ Cox serta makalah Cyril Allauzen dan Mehryar Mohri.

[GN⁺]

Komentar Hacker News

• Keren, menantikan perkembangan proyek ini

  • Terasa bahwa prioritas operatornya tidak alami
  • Aneh bahwa cat:dog ditafsirkan sebagai ca(t:d)og alih-alih (cat):(dog)

• Merekomendasikan XFST (Xerox Finite-State Transducer)

  • Ini adalah alat yang telah digunakan dalam linguistik komputasional selama lebih dari 20 tahun
  • Pernah mendengar contoh penggunaan FST untuk analisis morfologi bahasa Finlandia

• Merekomendasikan Rosie Pattern Language sebagai alternatif regex standar

  • Bisa menjadi alternatif yang lebih mudah dipelihara bagi orang-orang yang kesulitan dengan logika grup
  • Menyertakan tautan terkait: GitLab, situs resmi Rosie

• Membagikan pengalaman menulis makalah tentang finite-state transducer pada 1997

  • Topiknya adalah analisis morfologi, dan itu merupakan topik yang kurang dihargai
  • Menanyakan apakah benar mengatur : agar berikatan lebih kuat daripada ab dalam sintaks

• Merasa ini tidak cukup saat melakukan substitusi terstruktur

  • Karena regex mendefinisikan pohon sintaks untuk bagian yang cocok, akan berguna jika transformasi umum pada pohon dapat dilakukan

• Meragukan klaim bahwa regex tidak alami untuk penyuntingan teks

  • Tujuan proyek ini bergantung pada klaim tersebut, tetapi tidak ada contohnya
  • Tidak memahami mengapa orang kesulitan menggunakan grup
  • Perlu contoh yang menjelaskan mengapa tata bahasa proyek ini lebih baik daripada regex

• Memuji bahwa kode C-nya sangat rapi

  • Tautan theory.pdf di README salah dan perlu diperbaiki

• Meragukan saran untuk tidak menggunakan * atau +

  • Itu memang akan membuat tata bahasanya lebih rumit, tetapi mungkin lebih baik jika tetap diizinkan

• Merasa contoh pertama aneh

  • Hasil echo 'cat' | trre 'c:da:ot:g' terasa janggal
  • Sulit memahami bagaimana pohon sintaksnya dibentuk
  • Merasa cara cari/ganti pada era MS-DOS lebih intuitif

• Meragukan apakah contoh-contohnya adalah keluaran nyata dari program

  • Mungkin kurang memahami tata bahasanya, tetapi contoh-contohnya terlihat salah
  • Hasil echo 'cat dog' | trre 'c:bat|d:hog' terasa aneh