Show HN: Biểu thức chính quy transductive cho chỉnh sửa văn bản

 (github.com/c0stya)
1 điểm bởi GN⁺ 2025-02-09 | 1 bình luận | Chia sẻ qua WhatsApp

  • TRRE: Biểu thức chính quy chuyển đổi

  • Tóm tắt
    • Đây là một phần mở rộng của biểu thức chính quy dành cho chỉnh sửa văn bản và các công cụ dòng lệnh tương tự grep.
    • Đây là bản nguyên mẫu, không nên dùng trong môi trường thực tế.

  • Giới thiệu

    • Biểu thức chính quy là công cụ hữu ích để tìm kiếm mẫu trong văn bản.
    • Tác giả cảm thấy chúng không thật sự tự nhiên cho việc chỉnh sửa văn bản nên đã đề xuất một phần mở rộng.
    • Tên gọi của nó là biểu thức chính quy chuyển đổi hoặc trre.
    • Nó dùng ký hiệu : để định nghĩa phép biến đổi.
    • a:b là dạng đơn giản nhất, thay a bằng b.
    • Tác giả đã tạo một công cụ dòng lệnh tên trre để minh họa ý tưởng này.

  • Ví dụ

    • Cơ bản

      • Đổi cat thành dog: 
        $ echo 'cat' | trre 'c:da:ot:g'
dog
      • Thay mọi chuỗi khớp trong văn bản như sed: 
        $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
Mary had a little cat.
      • Xóa: 
        $ echo 'xor' | trre '(x:)or'
or
      • Chèn: 
        $ echo 'or' | trre '(:x)or'
xor

    • Biểu thức chính quy thông qua phép chuyển đổi

      • Dùng luân phiên: 
        $ echo 'cat dog' | trre 'c:bat|d:hog'
bat hog
      • Dùng star để lặp phép chuyển đổi: 
        $ echo 'catcatcat' | trre '((cat):(dog))*'
dogdogdog

    • Chuyển đổi theo khoảng

      • Chuyển đổi dải ký tự: 
        $ echo "regular expressions" | trre "[a:A-z:Z]"
REGULAR EXPRESSIONS

    • Bộ sinh

      • trre có thể tạo ra nhiều chuỗi đầu ra từ một đầu vào duy nhất.
      • Chuỗi nhị phân: 
        $ echo '' | trre -ma ':(0|1){3}'
000  001  010  011  100  101  110  111

  • Đặc tả ngôn ngữ

    • trre được định nghĩa dưới dạng cặp mẫu-khớp:mẫu-sinh.
    • mẫu-khớp có thể là chuỗi hoặc biểu thức chính quy.
    • mẫu-sinh thường là chuỗi, nhưng cũng có thể là regex.

  • Vì sao nó hoạt động

    • trre xây dựng một dạng automata đặc biệt gọi là bộ chuyển đổi trạng thái hữu hạn (FST).
    • FST xử lý các cặp đầu vào-đầu ra.

  • Lựa chọn thiết kế và các câu hỏi còn mở

    • Cần đưa ra nhiều quyết định như tính kết hợp của :, độ ưu tiên, epsilon ngầm định, v.v.

  • Chế độ và tính tham lam

    • trre hỗ trợ hai chế độ:
      • Chế độ quét (mặc định): áp dụng các phép chuyển đổi theo trình tự.
      • Chế độ khớp: kiểm tra toàn bộ chuỗi theo biểu thức.

  • Xác định hóa

    • Quá trình chuyển automata không xác định sang automata xác định là rất quan trọng.

  • Hiệu năng

    • Phiên bản NFT (không xác định) chậm hơn sed một chút.
    • Với các tác vụ phức tạp, trre_dft (phiên bản xác định) có thể cho hiệu năng tốt hơn sed.

  • TODO

    • Hoàn thiện bộ tính năng ERE, hỗ trợ Unicode đầy đủ, xử lý khoảng hiệu quả hơn, v.v.

  • Tài liệu tham khảo

    • Lấy cảm hứng từ các bài viết của Russ Cox và các bài báo của Cyril Allauzen, Mehryar Mohri.

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-02-09
Bình luận trên Hacker News

  • Hay đấy, mong chờ dự án này phát triển

    • Cảm giác độ ưu tiên của toán tử không được tự nhiên
    • Việc cat:dog được diễn giải thành ca(t:d)og thay vì (cat):(dog) nghe có vẻ kỳ lạ

  • Đề xuất XFST (Xerox Finite-State Transducer)

    • Đây là công cụ đã được dùng trong ngôn ngữ học máy tính hơn 20 năm
    • Từng nghe về các trường hợp dùng FST cho phân tích hình thái tiếng Phần Lan

  • Đề xuất Rosie Pattern Language như một lựa chọn thay thế cho biểu thức chính quy tiêu chuẩn

  • Chia sẻ kinh nghiệm từng viết bài báo về bộ chuyển đổi trạng thái hữu hạn vào năm 1997

    • Chủ đề là phân tích hình thái học, và đó là một chủ đề bị đánh giá thấp
    • Hỏi liệu với cú pháp này có đúng khi để : liên kết mạnh hơn ab hay không

  • Cảm thấy chưa đủ khi thực hiện thay thế có cấu trúc

    • Vì biểu thức chính quy định nghĩa cây cú pháp cho phần được khớp, sẽ rất hữu ích nếu có thể thực hiện các phép biến đổi tổng quát trên cây

  • Hoài nghi về nhận định rằng biểu thức chính quy là không tự nhiên đối với việc chỉnh sửa văn bản

    • Mục tiêu của dự án dường như dựa trên nhận định này, nhưng không có ví dụ nào
    • Không hiểu vì sao mọi người lại gặp khó với việc dùng nhóm
    • Cần các ví dụ giải thích vì sao ngữ pháp của dự án này tốt hơn biểu thức chính quy

  • Khen mã C rất gọn gàng

    • Liên kết theory.pdf trong README bị sai và cần được sửa

  • Hoài nghi về lời khuyên không nên dùng * hay +

    • Điều đó sẽ làm ngữ pháp phức tạp hơn, nhưng có lẽ vẫn tốt hơn là không cho phép chúng

  • Cảm thấy ví dụ đầu tiên khá kỳ lạ

    • Kết quả của echo 'cat' | trre 'c:da:ot:g' trông khó hiểu
    • Khó hiểu cây cú pháp được xây dựng như thế nào
    • Cảm thấy kiểu tìm kiếm/thay thế thời MS-DOS còn trực quan hơn

  • Hoài nghi liệu các ví dụ có phải là đầu ra thực của chương trình hay không

    • Có thể là do chưa hiểu đủ về cú pháp, nhưng các ví dụ trông như bị sai
    • Kết quả của echo 'cat dog' | trre 'c:bat|d:hog' trông kỳ lạ