Show HN: Ekspresi Reguler Transduktif untuk Penyuntingan Teks

 (github.com/c0stya)
1 poin oleh GN⁺ 2025-02-09 | 1 komentar | Bagikan ke WhatsApp
  • TRRE adalah ekstensi bahasa yang menambahkan operator : untuk mengekspresikan transformasi teks langsung di dalam ekspresi reguler, dan disediakan sebagai alat CLI trre mirip grep -E untuk bereksperimen dengannya
  • Bentuk dasarnya adalah pasangan transduktif yang mengubah pola input menjadi pola output, seperti a:b; penghapusan diekspresikan sebagai transformasi dengan string kosong seperti x:, dan penyisipan seperti :x
  • Seperti ekspresi reguler biasa, TRRE mendukung alternatif, repetisi, dan transformasi rentang karakter, dengan contoh seperti cat:dog, [a:A-z:Z], dan Caesar cipher
  • Implementasi internalnya membangun Finite State Transducer(FST) yang menangani pasangan input-output, alih-alih FSA pada ekspresi reguler biasa, serta mendukung determinisasi on-the-fly yang eksperimental
  • Saat ini belum ada biner prabangun dan harus dibangun sendiri; stabilisasi DFT, dukungan Unicode penuh, penyelesaian fitur ERE, dan pemrosesan rentang yang efisien masih tersisa sebagai TODO

Masalah yang ingin diselesaikan TRRE

  • Ekspresi reguler biasa berguna untuk menemukan pola dalam teks, tetapi dalam penyuntingan teks, logika pemrosesan grup dapat menjadi rumit karena terasa seperti pascapemrosesan
  • TRRE memperluas bahasa ekspresi reguler agar pencocokan pola dan modifikasi teks dapat dimasukkan ke dalam ekspresi yang sama
  • Sintaks intinya berbentuk pattern-to-match:pattern-to-generate, dan contoh paling sederhana adalah a:b, yang mengubah a menjadi b
  • Alat CLI trre adalah implementasi yang menunjukkan konsep ini dan bekerja dengan nuansa yang mirip grep -E

Sintaks transformasi dasar

  • Substitusi string ditulis seperti cat:dog
    • echo 'cat' | ./trre 'cat:dog' mencetak dog
    • Hasil yang sama juga bisa dibuat sebagai transformasi per karakter seperti (c:d)(a:o)(t:g)
  • Dapat digunakan seperti sed untuk mengganti semua kecocokan di dalam string
    • Jika menerapkan lamb:cat pada Mary had a little lamb., hasilnya menjadi Mary had a little cat.
  • Penghapusan diekspresikan dengan mengosongkan sisi kanan, dalam bentuk string_to_delete:
    • (x:)or menghapus x dari xor dan menghasilkan or
    • a: dalam scan mode default mengganti semua a dengan simbol kosong sehingga menghapusnya
    • Beberapa karakter dapat dihapus menggunakan ekspresi kurung siku seperti [aie]:
  • Penyisipan diekspresikan dengan mengosongkan sisi kiri, dalam bentuk :string_to_insert
    • (:x)or menyisipkan x di depan or dan menghasilkan xor
    • had a (:little )lamb menyisipkan little di dalam konteks

Transformasi di atas ekspresi reguler

  • TRRE mendukung alternatif menggunakan | seperti ekspresi reguler biasa
    • (c:b)at|(d:h)og mengubah cat dog menjadi bat hog
  • Operator repetisi juga dapat diterapkan pada transformasi
    • (cat:dog)* mengubah catcatcat menjadi dogdogdog
    • Dalam scan mode default, cat:dog saja juga diterapkan berulang dan menghasilkan hasil yang sama
  • Jika repetisi digunakan pada pola kiri, beberapa input dapat dikonsumsi dan diubah menjadi satu output
    • (cat)*:dog mengubah catcatcat menjadi dog
  • Menggunakan * atau + pada pola kanan dapat menyebabkan loop tak hingga
    • Ekspresi seperti :a* sebaiknya dihindari
    • Jika perlu repetisi terbatas, tentukan jumlahnya seperti :(repeat-10-times){10}

Transformasi rentang dan generator

  • Transformasi rentang karakter ditulis seperti [a:A-z:Z]
    • regular expressions dapat diubah menjadi REGULAR EXPRESSIONS
  • Contoh Caesar cipher disertakan
    • [a:b-y:zz:a] mengubah caesar cipher menjadi dbftbs djqifs
    • [a:zb:a-z:y] mengembalikannya lagi menjadi caesar cipher
  • TRRE juga dapat membuat beberapa output dari satu input, seperti generator
    • Default-nya menggunakan kecocokan pertama yang mungkin
    • Jika opsi -a digunakan, semua output yang mungkin akan dihasilkan
  • Sebagai contoh, menerapkan :(0|1){3} pada input kosong dapat menghasilkan urutan biner 3-bit dari 000 hingga 111
  • Menggunakan :(0|1){,3}? bersama -ma menghasilkan output berbentuk subset dengan panjang 3 atau kurang

Spesifikasi bahasa dan prioritas operator

  • Secara informal, TRRE didefinisikan sebagai pasangan pattern-to-match:pattern-to-generate
  • pattern-to-match di sisi kiri dapat berupa string atau ekspresi reguler
  • pattern-to-generate di sisi kanan biasanya berupa string, tetapi juga dapat berupa ekspresi reguler
  • Operator : saat ini diperlakukan sebagai non-asosiatif, dan bentuk TRRE:TRRE tidak diizinkan secara sintaksis
    • Bentuk ini memiliki makna alami sebagai komposisi relasi yang didefinisikan TRRE, tetapi belum disertakan karena kompleksitasnya dapat meningkat
  • Prioritas operator dari yang tertinggi adalah sebagai berikut
    • Karakter escape \
    • Ekspresi kurung siku []
    • Pengelompokan ()
    • Repetisi * + ? {m,n}
    • Konkatenasi
    • Transduksi :
    • Alternatif |

Mode dan greediness

  • trre mendukung dua mode
    • Scan Mode: mode default, menerapkan transformasi secara berurutan
    • Match Mode: menggunakan flag -m, memeriksa apakah seluruh string cocok dengan ekspresi
  • Opsi -a menghasilkan semua output yang mungkin
  • Modifier ? membuat operator *, +, {,} menjadi non-greedy
    • <(.:)*> mencetak <> dari <cat><dog>
    • <(.:)*?> mencetak <><> dari input yang sama
  • Contoh untuk mengubah isi di dalam tag atau tanda kurung juga disertakan
    • <(.*?:cat)> mengubah <dog> <mouse> menjadi <cat> <cat>

Implementasi berbasis FST dan determinisasi

  • TRRE secara internal membangun Finite State Transducer(FST)
  • FST mirip dengan Finite State Automaton(FSA) yang digunakan pada ekspresi reguler biasa, tetapi menangani pasangan input-output alih-alih string sederhana
  • Perbedaan utama TRRE adalah sebagai berikut
    • Mendefinisikan relasi biner antara dua bahasa reguler
    • Menggunakan FST, bukan FSA, untuk inferensi
    • Mendukung determinisasi on-the-fly yang eksperimental demi performa
  • Dalam mesin ekspresi reguler biasa, determinisasi mengubah automata nondeterministik menjadi automata deterministik sehingga memungkinkan inferensi waktu linear terhadap panjang string input
  • Pendekatan serupa juga dimungkinkan di TRRE, tetapi tidak semua transducer nondeterministik NFT dapat diubah menjadi transducer deterministik DFT
    • Jika ada dua cycle “bad” dengan label input yang sama, pembuatan state dapat terjebak dalam loop tak hingga
    • Ada cara untuk mendeteksi loop seperti ini, tetapi biayanya besar

Performa dan status instalasi

  • Versi nondeterministik default disajikan dengan contoh yang sedikit lebih lambat daripada sed dalam substitusi sederhana
    • ./trre '(vodka):(VODKA)': real 0m0.046s
    • sed 's/vodka/VODKA/': real 0m0.024s
  • Untuk tugas kompleks, ada contoh versi deterministik trre_dft yang lebih cepat daripada sed
    • sed -e 's/\(.*\)/\U\1/': real 0m0.508s
    • ./trre_dft '[a:A-z:Z]': real 0m0.131s
  • Biner prabangun belum tersedia
  • Instalasi dilakukan dengan meng-clone repositori lalu membangun dan menguji dengan make && sh test.sh
  • TODO masih mencakup hal-hal berikut
    • Versi DFT yang stabil
    • Dukungan Unicode penuh
    • Penyelesaian fitur ERE
      • Negasi ^ di dalam []
      • Kelas karakter
      • Simbol anchor $^
    • Pemrosesan rentang yang efisien

Pendekatan yang dirujuk

Bacaan terkait

1 komentar

 
GN⁺ 2025-02-09
Komentar Hacker News

  • Menarik melihat proyek ini akan berkembang ke mana. Namun prioritas operator terasa tidak alami, dan tampaknya orang lain di thread ini juga merasakan hal yang sama
    cat:dog secara alami lebih mudah diasumsikan setara dengan (cat):(dog) daripada ca(t:d)og

    • Ini ide yang menarik dari banyak sisi
      Aku juga sempat bingung karena cat:dog ditafsirkan seperti ca(t:d)og, bukan (cat):(dog), tetapi lalu teringat bahwa semua orang sedikit banyak memakai regex dengan “keliru”, jadi masuk akal. Regex “pada dasarnya” lebih tepat dipandang sebagai generator string, bukan matcher, sehingga cat|dog secara formal bisa dianggap berkembang menjadi himpunan seperti {catog,cadog}
      Untuk matching, himpunan string ini lalu cukup dicocokkan sebagai substring terhadap teks yang lebih besar. Masalahnya, kebanyakan regex engine nyata tidak bekerja seperti ini, dan demi memenuhi ekspektasi atau efisiensi, mereka melakukan berbagai perilaku aneh
      Kalau mencoba beberapa alat regex, akan muncul variasi seperti (cat)|(dog) atau (cat)|(dog)|(ca[td]og). Jadi dari sudut pandang yang lebih formal, menurutku benar jika cat:dog menghasilkan ca(t:d)og, bukan (cat):(dog). Namun karena selama puluhan tahun regex disalahgunakan sebagai alat matching yang disesuaikan dengan ekspektasi pengguna, sekarang semua orang cenderung menambahkan tanda kurung di sekitar ekspresi yang ingin diganti
      Usulan ini menarik dan dirancang dengan baik, tetapi pada akhirnya terasa seperti upaya mengembalikan regex ke model generator aslinya. Masalahnya lebih dekat ke alatnya daripada ke tata bahasanya
      Dulu aku pernah mengerjakan hal yang dekat dengan bidang ini, dan kalau kamu belum pernah memikirkan regex sebagai generator himpunan string, kamu bisa bermain-main di sini: https://onlinestringtools.com/generate-string-from-regex
      Namun perilaku alat generator seperti ini juga sangat spesifik. Alat yang dulu kupakai punya berbagai cara untuk membatasi generator, misalnya dengan memberi kendala pada closure dan semacamnya
    • Terima kasih atas masukannya, aku juga sedang memikirkan prioritasnya, jadi bisa saja diubah
      Kalau diturunkan ke bawah konkatenasi, bisa muncul masalah lain. Misalnya pada : yang tidak asosiatif, cat:dog:mouse mungkin seharusnya ilegal, dan aku belum yakin bagaimana menanganinya
      Pada versi saat ini, epsilon, yaitu string kosong, disisipkan. Misalnya untuk menghapus dengan melompati satu karakter setiap kali, secara teknis bisa menjalankan ..: yang merupakan .(.:eps)
      Hasil echo 'abcde' | ./trre '..:' adalah 'ace'
      Sebenarnya pengikatan : juga bisa diberi makna sebagai komposisi relasi reguler, tetapi untuk saat ini menurutku itu terlalu rumit
    • Transformasi rentang juga mirip. [a:A-z:Z] lebih baik ditulis [a-z:A-Z], dan alih-alih [a:b-y:zz:a], aku ingin mengusulkan bentuk seperti [a-y:b-z;z:a]

  • Jika tertarik pada finite-state transducer dan alat terkait, XFST (Xerox Finite-State Transducer) layak dilihat. Ini sudah dipakai lebih dari 20 tahun dalam aplikasi linguistik komputasional
    Seorang peneliti Finlandia dari PARC pernah datang ke kelas UT dan menunjukkan cara menangani morfologi bahasa Finlandia dengan FST, dan bahkan dari luar pun itu tampak sangat mengesankan

    • Aku juga tadinya ingin menyebut ini. Tautan makalah Kaplan: https://aclanthology.org/J94-3001.pdf
      Menjelaskan pekerjaan yang dilakukan di PARC
    • http://hfst.github.io/ adalah versi open source modern dari XFST. Ini mencakup foma dan OpenFst, dan kemungkinan bisa melakukan hampir semua yang dikerjakan trre, bahkan lebih
    • Pynini juga patut dilirik. Ini adalah wrapper Python untuk OpenFst dengan banyak fitur tambahan untuk kemudahan penggunaan
      OpenFst benar-benar pustaka yang hebat untuk transduser. Tutorial use case Pynini yang dibuat dalam bentuk tugas oleh Johns Hopkins dan lainnya juga cukup bagus
      [1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
      [2] https://www.openfst.org/

  • Jika sedang mencari alternatif untuk regex standar, terutama bila logika grup terasa sulit atau ingin ekspresi yang lebih mudah dirawat, Rosie Pattern Language mungkin cocok
    https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
    https://rosie-lang.org/about/

  • Keren. Sekitar tahun 1997 aku menulis tesis Diplom ilmu komputer dengan topik finite-state transducer, dan ternyata jauh kurang sepele daripada yang kukira
    Tugasnya adalah mengimplementasikan komposisi dan DFA jika memungkinkan, termasuk transduser hasil komposisi. Judulnya “aljabar finite-state transducer” dan use case-nya adalah morfologi. Topik ini sangat diremehkan sehingga aku harus berhenti di tengah jalan. Jadi salut
    Soal tata bahasa, aku penasaran apakah benar : ingin diikat lebih kuat daripada konkatenasi ab

    • Pada awal 2000-an aku memakai OpenFST di bioinformatika. Menyenangkan untuk dimainkan, tetapi pada akhirnya tidak berguna untuk pekerjaan yang kulakukan
      Senang melihat proyek itu masih berlanjut 20 tahun kemudian: https://www.openfst.org/twiki/bin/view/FST/WebHome
    • Menjadikan kelulusan pada dasarnya bergantung pada “apakah kamu bisa menangani regex dengan cukup keras” adalah pilihan yang luar biasa berani
    • Benar. Transduser adalah topik yang sangat tua. Entah kenapa, ini tidak pernah terikat kuat pada bahasa tertentu seperti regex
      Aku masih belum yakin apakah : memang harus diikat lebih kuat daripada konkatenasi. Setelah melihat sekitar 100 contoh, cara sekarang—yakni : lebih rendah daripada .—terasa lebih alami, tetapi di kode perubahan itu harfiah hanya butuh mengganti satu angka. Itulah kenapa aku mempostingnya di sini; aku butuh umpan balik nyata.

  • Begitu ingin melakukan substitusi terstruktur jenis tertentu, pendekatan ini terasa kurang memadai. Misalnya, ada kalanya kita ingin melakukan sesuatu seperti s/\"([^\"]*)\"/'$1'/
    Selain itu, akan lebih berguna jika bagian yang cocok dengan ['] di dalam [^\"] bisa diubah menjadi \\'
    Secara lebih umum, regex pada dasarnya mendefinisikan parse tree terhadap hasil pencocokan, jadi akan berguna jika kita bisa melakukan transformasi yang lebih umum pada tree tersebut

    • Jika saya memahaminya dengan benar, ekspresi ttre berikut melakukan yang diinginkan:
      \":'(':(\\\\')|[^\"'])*\":'
    • Kalau saya paham dengan benar, yang diinginkan adalah mengubah isi di dalam blok \"...\" dan mengganti tanda kutipnya menjadi kutip tunggal '
      Ini bisa dilakukan dengan ekspresi berikut:
      echo '\"hello world\" \"hello again!\"' | ./trre "\\\":'.+?:-\\\":'"
      Hasilnya adalah '-' '-'
      Artinya, dengan ekspresi \".+?:-\", teks di dalam \"\" diganti dengan simbol - sambil sekaligus mengubah tanda kutip di sekelilingnya. Tanda tanya berarti mode non-greedy

  • Seluruh proyek ini tampaknya bertumpu pada klaim bahwa “regex adalah alat yang hebat untuk menemukan pola dalam teks, tetapi selalu terasa tidak alami untuk penyuntingan teks”, tetapi justru tidak ada satu pun contohnya
    Saya tidak paham kenapa regex terasa tidak alami untuk penyuntingan. Saya juga tidak tahu apa yang dimaksud dengan penyuntingan di sini, dan kenapa orang kesulitan dengan grup
    Contoh sintaks proyek ini banyak, tetapi saya tidak paham kenapa ini lebih baik daripada regex biasa. Kalau ada beberapa contoh seperti “versi regex biasa seperti ini, versi saya seperti ini, jadi lebih mudah”, saya rasa proyeknya akan lebih mudah dipahami

    • Saya cenderung melihat regex sebagai sesuatu yang sekali ditulis lalu tidak diubah lagi. Membuat prototipe yang mencoba melampaui itu adalah cara yang baik untuk mengeksplorasi masa depan yang lebih baik di bidang ini
    • Itu masukan yang valid. Contoh yang paling jelas adalah saat perlu mengubah hanya dalam konteks tertentu
      Misalnya, jika ingin mengubah hanya y yang berada di antara x dan z menjadi Y, di Python kira-kira ditulis seperti ini:
      pattern = r'(x)y(z)'
      replacement = r'\\1Y\\2'
      result = re.sub(pattern, replacement, text)
      Saya ingin menggantinya dengan pola xy:Yz:
      result = re.trre('xy:Yz', text)
      Jika x dan z adalah pola yang lebih kompleks atau regex itu sendiri, pendekatan ini bisa terasa lebih nyaman
    • Menurut saya tepat jika dikatakan bahwa regex sendiri tidak menyediakan kemampuan penyuntingan. Ada grup, tetapi untuk menggabungkan grup-grup itu Anda harus memakai bahasa lain seperti sed
    • Ini soal substitusi. Dengan sintaks penulis, menuliskan substitusi memang lebih mudah, secara harfiah lebih sedikit repot diketik
      Proyek yang bagus

  • Kode C-nya benar-benar menyenangkan untuk dibaca. Sangat bagus, dan saya sedang membacanya sekarang
    Satu komentar kecil saja: tautan theory.pdf di README rusak. Karena PDF-nya ada di direktori docs/, URL-nya cukup ditambahkan docs/

    • Terima kasih atas masukan dan koreksi salah ketiknya. Sudah saya perbaiki. Sebenarnya kemampuan C saya sudah cukup berkarat, jadi saya agak cemas soal itu

  • Disebutkan bahwa memakai * atau + di sisi kanan bisa menyebabkan loop tak hingga, jadi sebaiknya dihindari. Kenapa tidak dilarang saja?
    Saya paham kalau itu membuat spesifikasi sintaks lebih sulit, tetapi rasanya tidak ada alasan kuat untuk mempertahankannya

    • Masukan yang valid, dan saya setuju. Untuk saat ini memang lebih baik dinonaktifkan
      Alasan awalnya adalah karena saya ingin mengimplementasikan operasi menarik berupa komposisi transduser. Kita bisa melakukan operasi sederhana pada string dan mengomposisikan trre seperti filter, tetapi itu belum sempat saya selesaikan. Jadi, ya, masukan itu memang valid

  • Eksplorasinya menarik, tetapi masih kurang contoh yang menunjukkan kenapa ini benar-benar lebih baik. Tentu saja, mungkin karena saya sudah terlalu lama terbiasa dengan regex
    Misalnya, saya tidak tahu kenapa (cat):(dog) di trre lebih baik daripada s/cat/dog, atau apa keunggulan (x:)or dibanding s/xor/or. Hampir semua contoh terlihat bisa dipetakan di kepala saya ke regex yang relatif mudah
    Kalau ada keunggulan inti, sepertinya itu ada di sisi logika grup, jadi akan bagus kalau contohnya lebih fokus ke sana. Bahkan sebelum menjelaskan sintaks dasarnya, mungkin lebih baik dijelaskan dulu kenapa ini pilihan yang lebih baik
    Contoh sandi Caesar terasa sangat membutuhkan fitur “terapkan ini secara terbalik”. Itu permintaan yang umum dalam banyak substitusi teks, dan pada contoh ini kebutuhan itu terlihat sangat jelas. Otak programmer langsung berteriak, “kenapa logika yang sama harus dinyatakan dua kali?”
    Saya masih belum tahu apakah ini akan berguna, tetapi mengeksplorasi alternatif terhadap status quo yang sudah lama mengakar adalah hal yang hebat. Biasanya upaya seperti itu memang punya kemungkinan besar untuk tidak berhasil, tetapi eksplorasinya sendiri tetap menyenangkan untuk dilihat

  • Spesifikasinya tampak cukup kurang. Contoh pertama saja sudah aneh:
    $ echo 'cat' | trre 'c:da:ot:g'
    dog
    Saya tidak paham apa yang terjadi di sini. Sintaksnya ditulis seperti ini:
    TRRE <- TRRE* TRRE|TRRE TRRE.TRRE
    TRRE <- REGEX REGEX:REGEX
    Di sini parse tree-nya seperti apa? Kenapa c tidak berubah menjadi da? Atau kenapa c tidak dihapus lalu da berubah menjadi ot?
    Idenya bagus, yaitu memiliki makna cari/ganti yang lebih intuitif daripada operator pengelompokan. Pada era MS-DOS, kita bisa melakukan hal seperti ren .log .txt dan itu bekerja; dari sudut pikir bash modern itu terdengar tidak masuk akal, tetapi sekali lihat maksudnya sangat jelas

  • Ini masalah prioritas operator dan tokenisasi. Dalam bahasa ini, token adalah karakter tunggal, dan ada operator tak terlihat di antara karakter-karakter tersebut
    Jika operator itu kita sebut secara eksplisit sebagai ~, contohnya jadi terlihat seperti ini:
    $ echo 'cat' | trre 'c:d~a:o~t:g'
    dog
    Jika ditambahkan tanda kurung yang tidak perlu, hasilnya menjadi seperti ini:
    $ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'
    dog

  • Tata bahasanya memang kurang spesifik. Tata bahasa lengkapnya lebih rumit. Versi saat ini sepertinya harus dihapus dari dokumentasi, karena sekarang justru benar-benar membingungkan
    Kenapa c tidak berubah menjadi da sepenuhnya karena prioritas. Dari diskusi ini, saya jadi merasa saya memilih prioritas yang salah, dan itu menimbulkan kebingungan
    Tabel prioritas saat ini adalah sebagai berikut:
    | 1 | karakter escape | \\ |
    | 2 | ekspresi tanda kurung siku | [] |
    | 3 | pengelompokan | () |
    | 4 | pengulangan ERE karakter tunggal | * + ? {m,n} |
    | 5 | transformasi | : |
    | 6 | konkatenasi | . (implisit) |
    | 8 | pilihan | | |
    Jadi : mengikat lebih kuat daripada . yaitu konkatenasi implisit

  • Benar, spesifikasinya kurang. Contoh penghapusan menunjukkan bahwa string kosong juga bisa menjadi REGEX. Kalau begitu, pada dasarnya bisa dianggap ada regex string kosong sebanyak yang diinginkan di posisi mana pun, sehingga jumlah parse menjadi tak terbatas
    Sebaliknya, jika diwajibkan bahwa regex tidak boleh kosong, contoh penghapusan jadi rusak, tetapi ambiguitasnya berpindah ke sisi konkatenasi. Artinya, ambigu apakah (((c:d)(a:o))(t:g)) atau ((c:d)((a:o)(d:g))). Jika kita mengasumsikan asosiativitas, perbedaan ini seharusnya tidak penting

  • Dari kesan perilakunya, ini terlihat seperti c:d, a: yaitu tidak ada, lalu ot:g
    Tetapi setelah saya baca lagi, memang jelas membingungkan, dan secara teoritis keberatan itu masuk akal. Setelah membaca repositorinya, saya juga jadi percaya bahwa c seharusnya berubah menjadi da, tetapi saya tidak yakin