Tính khác biệt và giao của hai biểu thức chính quy

 (phylactery.org)
2 điểm bởi GN⁺ 2023-09-12 | 1 bình luận | Chia sẻ qua WhatsApp
  • Khi cần so sánh biểu thức chính quy như tập hợp chuỗi, antimirov tính toán trên một màn hình quan hệ bao hàm và tương đương, giao và hiệu giữa hai biểu thức α và β
  • Khu vực kết quả hiển thị đồng thời phần bù và các quan hệ, cho phép kiểm tra các phép toán như ~α, α < β, α = β, α & β, α ^ β, α - β
  • Nếu nhập thêm một chuỗi s riêng, có thể xác minh ngay mỗi biểu thức chính quy có khớp hay không dưới dạng s ∈ α, s ∈ β
  • Cú pháp hỗ trợ ., nối, lựa chọn |, lặp *·+·?·{n}·{m,n}, nhóm ký tự, nhóm ký tự phủ định, escape, escape Unicode UTF-16
  • Không hỗ trợ các tính năng thay đổi hành vi như anchor, khẳng định độ rộng bằng không, backreference, trích xuất nhóm con, tìm kiếm/khớp một phần, bỏ qua phân biệt chữ hoa chữ thường

So sánh biểu thức chính quy và phép toán tập hợp

  • Vùng nhập nhận hai biểu thức chính quy α và β
  • Đầu ra hiển thị đồng thời phần bù của hai biểu thức chính quy cùng các phép toán quan hệ/tập hợp
    • ~α, ~β: phần bù của từng biểu thức chính quy
    • α < β, α = β, α > β: quan hệ bao hàm và tính tương đương của hai biểu thức chính quy
    • α & β: giao
    • α ^ β: hiệu đối xứng
    • α - β: hiệu tập hợp
  • Nếu nhập chuỗi s, có thể kiểm tra chuỗi đó có thuộc từng biểu thức chính quy hay không dưới dạng s ∈ α, s ∈ β
  • Cũng hiển thị kích thước của từng biểu thức chính quy và số trạng thái DFA
    • Trong màn hình ví dụ, |α| = 1, |β| = 1
    • Trong màn hình ví dụ, dfa(α) và dfa(β) mỗi cái có 1 trạng thái

Cú pháp biểu thức chính quy được hỗ trợ

  • Các toán tử cơ bản xử lý ký tự đơn, nối, lựa chọn và lặp
    • .: khớp một ký tự đơn bất kỳ
    • xy: phép nối khớp y sau x
    • x|y: khớp x hoặc y
    • x*: lặp 0 lần trở lên
    • (xyz): nhóm hóa
    • (): biểu thức chính quy rỗng khớp chuỗi rỗng
  • Cũng hỗ trợ cú pháp viết tắt lặp thường dùng
    • x+: lặp 1 lần trở lên, tương đương xx*
    • x?: khớp tùy chọn, tương đương (x|)
    • x{n}: nối x n lần
    • x{m,n}: nối x từ m lần đến n lần
  • Tập ký tự và escape có thể dùng các dạng sau
    • [a-z0-9]: khớp một ký tự đơn trong nhóm
    • [^a-z0-9]: khớp một ký tự đơn không có trong nhóm
    • \c: escape ký tự đặc biệt c
    • \u001a: khớp ký tự UTF-16 tương ứng
    • Các ký tự khác như a, b, c sẽ khớp chính chúng

Tính năng không được hỗ trợ

  • antimirov tập trung vào việc xử lý biểu thức chính quy như đối tượng của các phép toán tập hợp, nên loại trừ các tính năng sau
    • Anchor ^, $
      • Tuy nhiên, ^ và $ vẫn phải được escape
    • Khẳng định độ rộng bằng không, ví dụ: (?=...), (?<=...)
    • Backreference, ví dụ: \1, \2
    • Trích xuất nhóm con
    • Tìm kiếm hoặc khớp một phần
    • Các flag khác thay đổi hành vi, chẳng hạn như bỏ qua phân biệt chữ hoa chữ thường
  • Có thể xem thông tin chi tiết tại non/antimirov

Bài viết liên quan

1 bình luận

 
GN⁺ 2023-09-12
Các ý kiến trên Hacker News

  • Tôi đã làm một demo web tương tự, cho thấy quá trình regex được chuyển đổi theo chuỗi phân tích cú pháp → NFA → DFA → DFA tối thiểu, rồi xuất từ DFA tối thiểu ra LLVM IR/Javascript/WebAssembly
    http://compiler.org/reason-re-nfa/src/index.html

    • Tuy nhiên, đi từ NFA sang DFA tường minh không phải lúc nào cũng là lựa chọn tốt
      Nhân tiện, đạo hàm Brzozowski dùng như một cách thay thế để khớp regex cũng có thể thú vị: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • Thư viện này có thể dùng để tạo phân cấp lớp chuỗi, nhờ đó có thể tận dụng tích cực hơn các chuỗi có kiểu
    Ví dụ, email và URL có cú pháp đặc thù; không gian giá trị của chúng là tập con của mọi chuỗi không rỗng, còn chuỗi không rỗng là tập con của mọi chuỗi
    Nếu hệ thống kiểu biết rằng chuỗi email là kiểu con của chuỗi không rỗng, thì việc truyền địa chỉ email vào một hàm yêu cầu chuỗi không rỗng có thể được xem là hợp lệ
    Thư viện này có thể dùng để định nghĩa và kiểm chứng các kiểu chuỗi như vậy cùng hệ phân cấp của chúng; cách hiện thực phân cấp sẽ khác nhau tùy ngôn ngữ, chẳng hạn subclassing, ràng buộc trait, v.v.

    • Trong các ngôn ngữ có kiểu hợp có gắn thẻ, cách này thường được dùng. Mã giả kiểu Haskell đại khái như sau
      Không export constructor Address mà chỉ export kiểu; kiểm tra trong fromString :: Text -> Maybe Address, và nếu địa chỉ sai thì trả về Nothing
      Đừng trộn tính hợp lệ vào dữ liệu; hãy báo hiệu qua một đường riêng, và khi cần xuất ra thì lấy lại giá trị được bọc bằng toText :: Address -> Text
    • Không nên dùng regex để kiểm tra địa chỉ email
      https://news.ycombinator.com/item?id=31092912
    • Không có nhiều thứ kỳ lạ bằng việc đào sâu xem bên trái dấu @ thì những gì được phép và không được phép trong địa chỉ email vào một buổi sáng cuối hè
      Heuristic đơn giản rằng mọi regex cố biểu diễn “địa chỉ email hợp lệ” đều sai là khá an toàn, nhưng nó cũng phá hỏng hết niềm vui
    • Tôi thắc mắc “không gian giá trị” nghĩa là gì

  • Regex là một ví dụ hay về việc gói một lý thuyết toán học khá tuyệt và phức tạp thành một giao diện có giá trị
    Đại số tuyến tính cũng cho cảm giác tương tự

    • Tôi luôn thấy đáng kinh ngạc là khi có một trường phù hợp, rất nhiều toán học có thể được chuyển thành đại số tuyến tính
      Ngay cả phép biến đổi Möbius trên mặt phẳng phức w=(az+b)/(cz+d) cũng có thể chuyển thành đại số tuyến tính
    • Thường thì trong những trường hợp như vậy, điều đó có nghĩa là biểu diễn đang tiến gần hơn tới sự thật
      Một giao diện tốt có giá trị nội tại, nhưng nhiều người thiên về kết quả lại không chịu thừa nhận điều đó
    • Nếu tôi nhớ không nhầm thì trong cuốn của Conway https://store.doverpublications.com/0486485838.html có nói tới mối liên hệ với đại số tuyến tính. Tôi chỉ lướt qua đại khái thôi

  • Trang tuyệt vời này tính quan hệ nhị phân giữa các cặp regex và hiển thị DFA dưới dạng đồ thị
    Nó trình diễn rất ấn tượng những phép toán khá không tầm thường thực hiện trên regex

    • Rất hay, nhưng nói nghiêm ngặt thì cũng không ngạc nhiên khi nó không hỗ trợ các tính năng khiến biểu thức không còn là chính quy nữa
      Dù vậy tôi cứ nghĩ các anchor ^ và $ thì không có vấn đề

  • Tôi dán “regex filter numbers divisible by 3” vào thì trang bị treo hoàn toàn: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    Tôi tự hỏi liệu có biểu thức nào ngắn hơn không

    • Trang web này bị treo với các regex tạo ra DFA có nhiều trạng thái
      Ví dụ như (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog
    • Dù sao trong phần mô tả của trang cũng nói là không hỗ trợ anchor

  • Tôi muốn xem giao giữa URL hợp lệ về mặt cú pháp và địa chỉ email, nhưng chỉ nhập regex URL dưới đây thôi mà trang đã xử lý quá lâu
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    Nguồn: https://stackoverflow.com/a/3809435/623763

    • Những biểu thức như (...){1,256} rất nặng, và mã Scala JS rốt cuộc sẽ timeout hoặc làm chết trình duyệt
      Nếu đổi nó thành (...)+ thì ít nhất trên môi trường của tôi nó chạy được. Những biểu thức nhỏ như (...){1,6} có lẽ ổn

  • Ban đầu tôi ngạc nhiên rồi nhanh chóng hiểu ra rằng regex sinh ra từ hợp và giao không hẳn là ngắn gọn
    Ví dụ, giao của "y.+" và ".+z" có thể viết bằng một biểu thức rất đơn giản là "y.*z", và trang cũng xác nhận tính tương đương. Nhưng công cụ lại đưa ra yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz*
    Hẳn là có lý do khiến kết quả như vậy, nhưng việc đưa ra regex tối thiểu theo tiêu chí như số ký tự có khả năng khó hơn nhiều

    • Một lý do có lẽ là ".+z" sau khi được chuyển thành ô-tô-mát quyết định thì trở nên lớn hơn và lộn xộn hơn

  • Trước đây tôi từng dùng khái niệm này để viết logic kiểm chứng cho cấu hình “IP RegEx filter”
    Mục tiêu là cho phép người dùng thiết lập bộ lọc IP bằng biểu thức chính quy. Bên marketing không hiểu CIDR, nhưng vì Google Analytics nên họ biết về biểu thức chính quy
    Có thể định nghĩa một biểu thức chính quy hợp lệ như thế nào? Nó phải có giao với biểu thức chính quy “mọi địa chỉ IPv4” không rỗng, đồng thời cũng không được bằng với biểu thức chính quy “mọi địa chỉ IPv4”
    Cách này đã ngăn được khá nhiều phàn nàn rằng bộ lọc không làm gì cả, nhưng không ngăn được bản thân việc nhập bộ lọc sai

    • Chẳng lẽ không thể có giải pháp đơn giản hơn sao? Thay vì cố kiểm chứng biểu thức chính quy của bộ lọc, chỉ cần hiển thị các địa chỉ IP mẫu, hoặc cho người dùng nhập một nhóm địa chỉ rồi cho thấy địa chỉ nào khớp và địa chỉ nào không khớp
      Việc này cũng giúp xử lý vấn đề bộ lọc sai

  • Để dùng tốt hơn trên di động, có lẽ nên tắt gợi ý tự động của trường nhập biểu thức chính quy
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • Tôi đã thử trang bằng 2 biểu thức chính quy cho các số chia hết cho 3 tương tự, và ngay cả khi bỏ ^ và $ ở hai đầu thì trang vẫn bị treo
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    Mọi thứ đều được parse cho đến ngay trước dấu * cuối cùng, nhưng ngay khi thêm * vào thì toàn bộ trang bị treo
    Nếu không có *, nó tạo ra một bộ kiểm chứng hợp lệ để parse các đoạn số có tổng chữ số chia hết cho 3