Show HN: นิพจน์เรกิวลาร์แบบ Transductive สำหรับการแก้ไขข้อความ

• TRRE: นิพจน์เรกิวลาร์แบบแปลง

• สรุป

  • เป็นส่วนขยายของนิพจน์เรกิวลาร์สำหรับการแก้ไขข้อความและเครื่องมือบรรทัดคำสั่งที่คล้าย grep
  • เป็นเพียงต้นแบบ จึงไม่ควรนำไปใช้ในสภาพแวดล้อมจริง

• แนะนำ

  • นิพจน์เรกิวลาร์เป็นเครื่องมือที่มีประโยชน์สำหรับการค้นหารูปแบบในข้อความ
  • ผู้เขียนรู้สึกว่าเมื่อนำมาใช้กับการแก้ไขข้อความแล้วมันไม่ค่อยเป็นธรรมชาติ จึงเสนอส่วนขยายนี้ขึ้นมา
  • เรียกว่า นิพจน์เรกิวลาร์แบบแปลง หรือ trre
  • ใช้สัญลักษณ์ : เพื่อกำหนดการแปลง
  • a:b คือรูปแบบที่ง่ายที่สุด โดยแทนที่ a ด้วย b
  • มีการสร้างเครื่องมือบรรทัดคำสั่งชื่อ trre เพื่อสาธิตแนวคิดนี้

• ตัวอย่าง

  • พื้นฐาน

    • เปลี่ยน cat เป็น dog:

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

    • แทนที่ทุกตำแหน่งที่ตรงกันของสตริงเหมือน sed:

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

    • ลบ:

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

    • แทรก:

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

  • นิพจน์เรกิวลาร์ผ่านการแปลง

    • ใช้ alternation:

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

    • ใช้ star เพื่อทำการแปลงซ้ำ:

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

  • การแปลงช่วง

    • การแปลงช่วงของอักขระ:

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

  • ตัวสร้าง

    • trre สามารถสร้างสตริงผลลัพธ์ได้หลายแบบจากอินพุตเดียว
    • ลำดับเลขฐานสอง:

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

• ข้อกำหนดของภาษา

  • trre ถูกนิยามเป็นคู่ของ รูปแบบที่ใช้จับคู่:รูปแบบที่ใช้สร้าง
  • รูปแบบที่ใช้จับคู่ อาจเป็นสตริงหรือนิพจน์เรกิวลาร์ก็ได้
  • รูปแบบที่ใช้สร้าง โดยทั่วไปเป็นสตริง แต่ก็อาจเป็น regex ได้เช่นกัน

• ทำไมมันถึงทำงานได้

  • trre สร้างออโตมาตาชนิดพิเศษที่เรียกว่า finite-state transducer (FST)
  • FST จัดการกับคู่ของอินพุต-เอาต์พุต

• ทางเลือกในการออกแบบและคำถามที่ยังเปิดอยู่

  • ต้องมีการตัดสินใจหลายอย่าง เช่น associativity ของ :, ลำดับความสำคัญ และ epsilon โดยนัย

• โหมดและความละโมบ

  • trre รองรับสองโหมด:
    • โหมดสแกน (ค่าเริ่มต้น): ใช้การแปลงตามลำดับ
    • โหมดจับคู่: ตรวจสอบทั้งสตริงกับนิพจน์

• การทำให้เป็นแบบกำหนดแน่นอน

  • กระบวนการแปลงออโตมาตาแบบไม่กำหนดแน่นอนให้เป็นแบบกำหนดแน่นอนมีความสำคัญ

• ประสิทธิภาพ

  • เวอร์ชัน NFT (ไม่กำหนดแน่นอน) ช้ากว่า sed เล็กน้อย
  • ในงานที่ซับซ้อน trre_dft (เวอร์ชันกำหนดแน่นอน) อาจทำงานได้ดีกว่า sed

• TODO

  • ทำชุดความสามารถ ERE ให้สมบูรณ์, รองรับ Unicode ทั้งหมด, การจัดการช่วงอย่างมีประสิทธิภาพ เป็นต้น

• เอกสารอ้างอิง

  • ได้แรงบันดาลใจจากบทความของ Russ Cox และงานวิจัยของ Cyril Allauzen กับ Mehryar Mohri

[GN⁺]

ความคิดเห็นบน Hacker News

• เจ๋งมาก คาดหวังการพัฒนาของโปรเจ็กต์นี้

  • รู้สึกว่าลำดับความสำคัญของตัวดำเนินการไม่ค่อยเป็นธรรมชาติ
  • แปลกที่ cat:dog ถูกตีความเป็น ca(t:d)og แทนที่จะเป็น (cat):(dog)

• แนะนำ XFST (Xerox Finite-State Transducer)

  • เป็นเครื่องมือที่ใช้ในภาษาศาสตร์คอมพิวเตอร์มานานกว่า 20 ปี
  • เคยได้ยินตัวอย่างการใช้ FST สำหรับการวิเคราะห์หน่วยคำของภาษาฟินแลนด์

• แนะนำ Rosie Pattern Language เป็นทางเลือกแทน regular expression มาตรฐาน

  • อาจเป็นทางเลือกที่ดูแลรักษาได้ง่ายกว่าสำหรับคนที่มีปัญหากับตรรกะของกลุ่ม
  • ให้ลิงก์ที่เกี่ยวข้อง: GitLab, เว็บไซต์ทางการของ Rosie

• แชร์ประสบการณ์การเขียนงานวิจัยเกี่ยวกับ finite-state transducer เมื่อปี 1997

  • หัวข้อคือการวิเคราะห์หน่วยคำ และเป็นหัวข้อที่ถูกมองข้าม
  • ถามว่าการกำหนดให้ : จับกลุ่มแน่นกว่า ab สำหรับไวยากรณ์นั้นถูกต้องหรือไม่

• รู้สึกว่ายังไม่เพียงพอเมื่อใช้ทำการแทนที่แบบมีโครงสร้าง

  • เนื่องจาก regular expression กำหนด syntax tree ให้กับส่วนที่แมตช์ได้ ถ้าสามารถทำการแปลง tree ทั่วไปได้ก็น่าจะมีประโยชน์

• ตั้งข้อสงสัยกับคำกล่าวที่ว่า regular expression ไม่เป็นธรรมชาติสำหรับการแก้ไขข้อความ

  • เป้าหมายของโปรเจ็กต์นี้ตั้งอยู่บนคำกล่าวนี้ แต่ไม่มีตัวอย่าง
  • ไม่เข้าใจว่าทำไมคนถึงมีปัญหากับการใช้กลุ่ม
  • ต้องการตัวอย่างที่อธิบายว่าทำไมไวยากรณ์ของโปรเจ็กต์นี้จึงดีกว่า regular expression

• ชมว่าโค้ด C สะอาดมาก

  • ลิงก์ theory.pdf ใน README เสียและควรแก้ไข

• ตั้งข้อสงสัยกับคำแนะนำที่ว่าไม่ควรใช้ * หรือ +

  • แม้จะทำให้ไวยากรณ์ซับซ้อนขึ้น แต่การไม่อนุญาตให้ใช้สิ่งเหล่านี้อาจดีกว่า

• รู้สึกว่าตัวอย่างแรกแปลก ๆ

  • ผลลัพธ์ของ echo 'cat' | trre 'c:da:ot:g' ดูผิดปกติ
  • เข้าใจได้ยากว่า syntax tree ถูกประกอบขึ้นอย่างไร
  • รู้สึกว่าวิธีค้นหา/แทนที่ในยุค MS-DOS เข้าใจง่ายกว่า

• สงสัยว่าตัวอย่างต่าง ๆ เป็นผลลัพธ์จริงจากโปรแกรมหรือไม่

  • อาจเป็นเพราะยังเข้าใจไวยากรณ์ไม่พอ แต่ตัวอย่างดูเหมือนผิด
  • ผลลัพธ์ของ echo 'cat dog' | trre 'c:bat|d:hog' ดูผิดปกติ