การคำนวณความต่างและจุดตัดของนิพจน์เรกิวลาร์สองชุด

 (phylactery.org)
2 คะแนน โดย GN⁺ 2023-09-12 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เมื่อต้องการเปรียบเทียบนิพจน์เรกิวลาร์ในฐานะ เซตของสตริง antimirov สามารถคำนวณความสัมพันธ์การครอบคลุมและความเท่ากันของนิพจน์ α และ β รวมถึงจุดตัดและผลต่างได้ในหน้าจอเดียว
  • พื้นที่แสดงผลจะแสดงทั้ง ส่วนเติมเต็มและความสัมพันธ์ ร่วมกัน ทำให้ตรวจสอบการดำเนินการอย่าง ~α, α < β, α = β, α & β, α ^ β, α - β ได้
  • หากใส่สตริงแยกต่างหาก s ก็สามารถตรวจสอบได้ทันทีว่า แต่ละนิพจน์เรกิวลาร์แมตช์หรือไม่ ผ่าน s ∈ α, s ∈ β
  • ไวยากรณ์รองรับ ., การเชื่อมต่อ, ตัวเลือก |, การทำซ้ำ *·+·?·{n}·{m,n}, กลุ่มอักขระ, กลุ่มอักขระปฏิเสธ, เอสเคป และ UTF-16 Unicode escape
  • ไม่รองรับ ฟีเจอร์ที่เปลี่ยนพฤติกรรม เช่น anchor, zero-width assertion, backreference, การดึง sub-group, การค้นหา/การแมตช์บางส่วน, และการไม่แยกตัวพิมพ์เล็กพิมพ์ใหญ่

การเปรียบเทียบนิพจน์เรกิวลาร์และการดำเนินการกับเซต

  • พื้นที่ป้อนข้อมูลรับนิพจน์เรกิวลาร์สองชุดคือ α และ β
  • เอาต์พุตจะแสดงทั้งส่วนเติมเต็มของนิพจน์เรกิวลาร์ทั้งสอง พร้อมความสัมพันธ์และการดำเนินการกับเซต
    • ~α, ~β: ส่วนเติมเต็มของแต่ละนิพจน์เรกิวลาร์
    • α < β, α = β, α > β: ความสัมพันธ์การครอบคลุมและความเท่ากันของนิพจน์เรกิวลาร์ทั้งสอง
    • α & β: จุดตัด
    • α ^ β: symmetric difference
    • α - β: ผลต่างเซต
  • หากป้อนสตริง s จะสามารถตรวจสอบได้ในรูปแบบ s ∈ α, s ∈ β ว่าสตริงนั้นอยู่ในแต่ละนิพจน์เรกิวลาร์หรือไม่
  • ยังแสดงขนาดของแต่ละนิพจน์เรกิวลาร์และ จำนวนสถานะของ DFA ด้วย
    • ในหน้าจอตัวอย่าง |α| = 1, |β| = 1
    • ในหน้าจอตัวอย่าง dfa(α) และ dfa(β) ต่างมีสถานะอย่างละ 1 สถานะ

ไวยากรณ์นิพจน์เรกิวลาร์ที่รองรับ

  • ตัวดำเนินการพื้นฐานครอบคลุมอักขระเดี่ยว การเชื่อมต่อ ตัวเลือก และการทำซ้ำ
    • .: แมตช์อักขระเดี่ยวใดก็ได้
    • xy: การเชื่อมต่อที่แมตช์ x แล้วตามด้วย y
    • x|y: แมตช์ x หรือ y
    • x*: ทำซ้ำ 0 ครั้งขึ้นไป
    • (xyz): การจัดกลุ่ม
    • (): นิพจน์เรกิวลาร์ว่างที่แมตช์สตริงว่าง
  • ยังรองรับรูปย่อของการทำซ้ำที่ใช้บ่อย
    • x+: ทำซ้ำ 1 ครั้งขึ้นไป เทียบเท่ากับ xx*
    • x?: การแมตช์แบบเลือกได้ เทียบเท่ากับ (x|)
    • x{n}: เชื่อม x จำนวน n ครั้ง
    • x{m,n}: เชื่อม x ตั้งแต่ m ครั้งถึง n ครั้ง
  • เซตอักขระและเอสเคปสามารถใช้ได้ในรูปแบบต่อไปนี้
    • [a-z0-9]: แมตช์อักขระเดี่ยวในกลุ่ม
    • [^a-z0-9]: แมตช์อักขระเดี่ยวที่ไม่อยู่ในกลุ่ม
    • \\c: เอสเคปอักขระพิเศษ c
    • \\u001a: แมตช์อักขระ UTF-16 ที่สอดคล้องกัน
    • นอกจากนี้ อักขระอย่าง a, b, c จะถูกแมตช์เป็นตัวมันเอง

ฟีเจอร์ที่ไม่รองรับ

  • antimirov มุ่งเน้นการจัดการนิพจน์เรกิวลาร์ในฐานะเป้าหมายของการดำเนินการกับเซต ดังนั้นจึงไม่รวมฟีเจอร์ต่อไปนี้
    • anchor ^, $
      • อย่างไรก็ตาม ^ และ $ ยังคงต้องเอสเคป
    • zero-width assertion เช่น (?=...), (?<=...)
    • backreference เช่น \\1, \\2
    • การดึง sub-group
    • การค้นหาหรือการแมตช์บางส่วน
    • แฟล็กอื่นที่เปลี่ยนพฤติกรรม เช่น การไม่แยกตัวพิมพ์เล็กพิมพ์ใหญ่
  • ดูข้อมูลเพิ่มเติมได้ที่ non/antimirov

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-09-12
ความคิดเห็นจาก Hacker News

  • เคยทำเว็บเดโมที่คล้ายกัน ซึ่งแสดงกระบวนการที่ regex ถูกแปลงจาก การพาร์ส → NFA → DFA → DFA ที่เล็กที่สุด และจาก DFA ที่เล็กที่สุดก็ยังเอาต์พุตเป็น LLVM IR/Javascript/WebAssembly ได้ด้วย
    http://compiler.org/reason-re-nfa/src/index.html

    • อย่างไรก็ตาม การไปจาก NFA ไปเป็น DFA แบบชัดเจนไม่ได้เป็นทางเลือกที่ดีเสมอไป
      อนึ่ง อนุพันธ์ของ Brzozowski ซึ่งใช้เป็นวิธีทางเลือกสำหรับการแมตช์ regex ได้ ก็น่าสนใจเช่นกัน: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • ไลบรารีนี้ใช้สร้าง ลำดับชั้นของคลาสสตริง ได้ และผลลัพธ์คือสามารถใช้สตริงที่มีไทป์ได้อย่างจริงจังมากขึ้น
    เช่น อีเมลและ URL มีไวยากรณ์เฉพาะ และสเปซของค่าของมันเป็นเซตย่อยของสตริงที่ไม่ว่างทั้งหมด ส่วนสตริงที่ไม่ว่างก็เป็นเซตย่อยของสตริงทั้งหมด
    ถ้า type system รู้ว่าสตริงอีเมลเป็น subtype ของสตริงที่ไม่ว่าง ก็จะตัดสินได้ว่าการส่งที่อยู่อีเมลให้ฟังก์ชันที่ต้องการสตริงที่ไม่ว่างนั้นถูกต้อง
    ไลบรารีนี้ใช้ตรวจสอบนิยามและลำดับชั้นของไทป์สตริงแบบนั้นได้ ส่วนการอิมพลีเมนต์ลำดับชั้นจะแตกต่างกันไปตามภาษา เช่น subclassing, trait bounds เป็นต้น

    • ในภาษาที่มี tagged union type มักใช้แนวทางนี้กันบ่อย pseudocode สไตล์ Haskell จะประมาณนี้
      ไม่ export constructor ของ Address แต่ export เฉพาะไทป์ และตรวจสอบใน fromString :: Text -> Maybe Address; ถ้าที่อยู่ไม่ถูกต้องก็คืน Nothing
      อย่าเอาความถูกต้องไปปนอยู่ในข้อมูล ให้ส่งสัญญาณผ่านอีกเส้นทางหนึ่ง และเมื่อต้องการเอาต์พุต ก็ใช้ toText :: Address -> Text เพื่อดึงค่าที่ห่อไว้กลับออกมา
    • ไม่ควรใช้ regex เพื่อตรวจสอบความถูกต้องของที่อยู่อีเมล
      https://news.ycombinator.com/item?id=31092912
    • ไม่มีอะไรแปลกพิกลเท่ากับการขุดคุ้ยว่าอะไรอนุญาตและไม่อนุญาตให้เป็นที่อยู่อีเมลทางซ้ายของ @ ในเช้าช่วงปลายฤดูร้อนอีกแล้ว
      ฮิวริสติกง่าย ๆ ที่ถือว่า regex ทุกตัวที่พยายามแทน “ที่อยู่อีเมลที่ถูกต้อง” นั้นผิด ค่อนข้างปลอดภัย แต่ก็ทำลายความสนุกไปหมด
    • สงสัยว่า “สเปซของค่า” หมายถึงอะไร

  • regex เป็นตัวอย่างที่ดีของการห่อ ทฤษฎีคณิตศาสตร์ ที่ค่อนข้างเจ๋งและซับซ้อนไว้ในอินเทอร์เฟซที่มีคุณค่า
    linear algebra ก็ให้ความรู้สึกคล้ายกัน

    • น่าทึ่งเสมอที่เมื่อมี field ที่เหมาะสม คณิตศาสตร์จำนวนมากจริง ๆ สามารถถูกแปลงเป็น linear algebra ได้
      แม้แต่ Möbius transformation w=(az+b)/(cz+d) บนระนาบเชิงซ้อนก็ยังแปลงเป็น linear algebra ได้
    • โดยปกติแล้ว กรณีแบบนั้นหมายความว่าการแทนกำลังเข้าใกล้ความจริงมากขึ้น
      อินเทอร์เฟซที่ดีมีคุณค่าในตัวเอง แต่คนจำนวนมากที่เน้นผลลัพธ์มักไม่ค่อยยอมรับเรื่องนั้น
    • ถ้าจำไม่ผิด ในหนังสือของ Conway https://store.doverpublications.com/0486485838.html น่าจะมี การเชื่อมโยงกับ linear algebra อยู่ เคยแค่เปิดดูคร่าว ๆ เท่านั้น

  • หน้านี้สุดเจ๋ง คำนวณ ความสัมพันธ์แบบทวิภาค ระหว่างคู่ของ regex และแสดง DFA เป็นกราฟ
    เป็นการสาธิตปฏิบัติการที่ค่อนข้างไม่ธรรมดาบน regex ได้อย่างน่าประทับใจจริง ๆ

    • เจ๋งมาก แต่พูดอย่างเคร่งครัด ก็ไม่น่าแปลกใจที่มันไม่รองรับฟีเจอร์ที่ทำให้ ไม่ใช่ regex อีกต่อไป
      ถึงอย่างนั้นก็คิดว่า anchor ^ และ $ น่าจะไม่เป็นปัญหา

  • ลองวาง “regex filter numbers divisible by 3” แล้วหน้าเว็บค้างสนิท: 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])))+$
    สงสัยว่ามีนิพจน์ที่สั้นกว่านี้ไหม

    • เว็บเพจนี้จะค้างกับ regex ที่สร้าง DFA ที่มี state จำนวนมาก
      เช่น (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog เป็นต้น
    • ยังไงตามคำอธิบายของหน้าเว็บก็ระบุว่าไม่รองรับ anchor อยู่แล้ว

  • อยากดู จุดตัด ของ URL กับที่อยู่อีเมลที่ถูกต้องตามไวยากรณ์ แต่แค่ใส่ regex ของ URL ด้านล่าง หน้าเว็บก็ใช้เวลาประมวลผลนานเกินไปแล้ว
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    ที่มา: https://stackoverflow.com/a/3809435/623763

    • นิพจน์อย่าง (...){1,256} หนักมาก และโค้ด Scala JS ก็จะลงเอยด้วยการ timeout หรือทำให้เบราว์เซอร์ตาย
      ถ้าเปลี่ยนมันเป็น (...)+ อย่างน้อยในสภาพแวดล้อมของฉันก็ทำงานได้ นิพจน์เล็ก ๆ อย่าง (...){1,6} น่าจะโอเค

  • ตอนแรกแปลกใจที่ regex ที่สร้างจาก union และ intersection ไม่ได้กระชับเป็นพิเศษ แต่ไม่นานก็เข้าใจ
    เช่น จุดตัดของ "y.+" กับ ".+z" เขียนเป็นนิพจน์ที่เรียบง่ายมากได้ว่า "y.*z" และหน้าเว็บก็ยืนยันความเท่ากันได้ด้วย แต่เครื่องมือกลับให้ yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* ออกมา
    น่าจะมีเหตุผลที่ได้ผลลัพธ์แบบนี้ แต่การสร้าง regex ที่สั้นที่สุด ตามเกณฑ์อย่างจำนวนอักขระ น่าจะยากกว่ามาก

    • เหตุผลหนึ่งน่าจะเป็นเพราะ ".+z" ถูกแปลงเป็น deterministic automaton แล้วใหญ่และรกขึ้น

  • ผมเคยใช้แนวคิดนี้มาก่อนเพื่อเขียน ลอจิกการตรวจสอบความถูกต้อง ของการตั้งค่า “IP RegEx filter”
    เป้าหมายคือให้ผู้ใช้ตั้งค่าฟิลเตอร์ IP ด้วย regular expression ได้ ฝั่งมาร์เก็ตติ้งไม่เข้าใจ CIDR แต่รู้จัก regular expression เพราะ Google Analytics
    จะนิยาม regular expression ที่ถูกต้องได้อย่างไร? ต้องมี intersection กับ regular expression ของ “ที่อยู่ IPv4 ทั้งหมด” ที่ไม่ว่าง และในขณะเดียวกันก็ต้องไม่เท่ากับ regular expression ของ “ที่อยู่ IPv4 ทั้งหมด” ด้วย
    วิธีนี้ช่วยกันข้อร้องเรียนว่าฟิลเตอร์ไม่ทำอะไรเลยได้มาก แต่ไม่ได้ป้องกันการป้อนฟิลเตอร์ที่ผิดตั้งแต่ต้น

    • อาจมีวิธีที่ง่ายกว่านี้ได้ไหม? แทนที่จะพยายามตรวจสอบ regular expression ของฟิลเตอร์ ก็แสดง ตัวอย่างที่อยู่ IP หรือให้ผู้ใช้ใส่ชุดที่อยู่เข้ามา แล้วแสดงว่าที่อยู่ใด match และที่อยู่ใดไม่ match ก็พอ
      วิธีนี้ยังช่วยรับมือปัญหาฟิลเตอร์ที่ผิดได้ด้วย

  • ถ้าจะให้ใช้งานบนมือถือได้ดีขึ้น ควรปิด การแนะนำอัตโนมัติ ของช่องกรอก regular expression
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • ผมทดสอบหน้าด้วย regular expression สำหรับจำนวนที่หารด้วย 3 ลงตัว ที่คล้ายกัน 2 ตัว และถึงจะลบ ^ กับ $ ที่หัวท้ายออกก็ยังค้าง
    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])))*
    ทุกอย่าง parse ได้จนถึงก่อน * ตัวสุดท้าย แต่ทันทีที่ใส่ * เข้าไป ทั้งหน้าก็ค้าง
    ถ้าไม่มี * มันสร้างตัวตรวจสอบความถูกต้องที่ใช้ได้สำหรับ parse ชิ้นส่วนของตัวเลขที่ผลรวมของหลักหารด้วย 3 ลงตัว