Show HN: นิพจน์ปกติแบบ Transductive สำหรับการแก้ไขข้อความ
(github.com/c0stya)- TRRE เป็นส่วนขยายของภาษา regular expression ที่เพิ่มตัวดำเนินการ
:เพื่อแสดงการแปลงข้อความโดยตรง และมีให้ใช้งานในรูปเครื่องมือ CLI ชื่อtrreที่คล้ายgrep -Eสำหรับทดลองแนวคิดนี้ - รูปแบบพื้นฐานคือ transductive pair ที่เปลี่ยนแพตเทิร์นอินพุตเป็นแพตเทิร์นเอาต์พุต เช่น
a:b; การลบเขียนเป็นการแปลงกับสตริงว่างแบบx:และการแทรกเขียนเป็น:x - สามารถใช้ การเลือกทางเลือก, การทำซ้ำ และการแปลงช่วงอักขระได้เหมือน regular expression ทั่วไป พร้อมตัวอย่างอย่าง
cat:dog,[a:A-z:Z]และ Caesar cipher - ภายในไม่ได้สร้าง FSA ของ regular expression ทั่วไป แต่สร้าง Finite State Transducer(FST) ที่จัดการคู่ input-output และรองรับการทำ determinization แบบ on-the-fly เชิงทดลองด้วย
- ขณะนี้ยังไม่มีไบนารีที่ build ไว้ล่วงหน้า ต้อง build เอง และยังมี TODO เช่น การทำให้ DFT เสถียร, รองรับ Unicode เต็มรูปแบบ, ทำฟีเจอร์ ERE ให้ครบ และจัดการช่วงอย่างมีประสิทธิภาพ
ปัญหาที่ TRRE ต้องการแก้
- regular expression ทั่วไปมีประโยชน์ในการหาแพตเทิร์นในข้อความ แต่ในการแก้ไขข้อความ ตรรกะการจัดการกลุ่มอาจกลายเป็นเหมือน post-processing และซับซ้อนได้
- TRRE ขยายภาษา regular expression เพื่อใส่ทั้งการจับคู่แพตเทิร์นและการแก้ไขข้อความไว้ใน expression เดียวกัน
- ไวยากรณ์หลักคือรูปแบบ
pattern-to-match:pattern-to-generateและตัวอย่างที่ง่ายที่สุดคือa:bซึ่งเปลี่ยนaเป็นb - เครื่องมือ CLI
trreเป็น implementation ที่แสดงแนวคิดนี้ และทำงานให้ความรู้สึกคล้ายgrep -E
ไวยากรณ์การแปลงพื้นฐาน
- การแทนที่สตริงเขียนได้แบบ
cat:dogecho 'cat' | ./trre 'cat:dog'จะพิมพ์dog- สามารถได้ผลเดียวกันด้วยการแปลงทีละอักขระ เช่น
(c:d)(a:o)(t:g)
- ใช้แทนที่ทุก match ในสตริงได้เหมือน
sed- หากใช้
lamb:catกับMary had a little lamb.จะได้Mary had a little cat.
- หากใช้
- การลบ แสดงโดยเว้นฝั่งขวาให้ว่างในรูป
string_to_delete:(x:)orลบxออกจากxorเพื่อให้ได้ora:ใน scan mode พื้นฐานจะเปลี่ยนaทุกตัวเป็นสัญลักษณ์ว่างและลบทิ้ง- สามารถใช้ bracket expression เพื่อลบหลายอักขระได้ เช่น
[aie]:
- การแทรก แสดงโดยเว้นฝั่งซ้ายให้ว่างในรูป
:string_to_insert(:x)orแทรกxหน้าorเพื่อให้ได้xorhad a (:little )lambแทรกlittleภายในบริบท
การแปลงบน regular expression
- TRRE รองรับ การเลือกทางเลือก ด้วย
|เหมือน regular expression ทั่วไป(c:b)at|(d:h)ogเปลี่ยนcat dogเป็นbat hog
- ตัวดำเนินการทำซ้ำก็ใช้กับการแปลงได้
(cat:dog)*เปลี่ยนcatcatcatเป็นdogdogdog- ใน scan mode พื้นฐาน แค่
cat:dogก็จะถูกใช้ซ้ำและให้ผลเดียวกันได้
- เมื่อใช้การทำซ้ำในแพตเทิร์นฝั่งซ้าย จะ consume อินพุตหลายรายการแล้วเปลี่ยนเป็นเอาต์พุตเดียวได้
(cat)*:dogเปลี่ยนcatcatcatเป็นdog
- หากใช้
*หรือ+ในแพตเทิร์นฝั่งขวา อาจเกิด ลูปไม่สิ้นสุด ได้- ควรหลีกเลี่ยง expression อย่าง
:a* - หากต้องการทำซ้ำแบบจำกัด ให้ระบุจำนวนครั้ง เช่น
:(repeat-10-times){10}
- ควรหลีกเลี่ยง expression อย่าง
การแปลงช่วงและ generator
- การแปลงช่วงอักขระเขียนได้แบบ
[a:A-z:Z]- สามารถเปลี่ยน
regular expressionsเป็นREGULAR EXPRESSIONSได้
- สามารถเปลี่ยน
- มีตัวอย่าง Caesar cipher รวมอยู่ด้วย
[a:b-y:zz:a]เปลี่ยนcaesar cipherเป็นdbftbs djqifs[a:zb:a-z:y]เปลี่ยนกลับเป็นcaesar cipher
- ยังสามารถสร้างเอาต์พุตหลายแบบจากอินพุตเดียวได้เหมือน generator
- ค่าเริ่มต้นจะใช้ match แรกที่เป็นไปได้
- หากใช้ตัวเลือก
-aจะสร้างเอาต์พุตทั้งหมดที่เป็นไปได้
- ตัวอย่างเช่น เมื่อนำ
:(0|1){3}ไปใช้กับอินพุตว่าง จะสร้างลำดับไบนารี 3 บิตตั้งแต่000ถึง111ได้ - เมื่อใช้
:(0|1){,3}?ร่วมกับ-maจะสร้างเอาต์พุตในรูปแบบ subset ที่มีความยาวไม่เกิน 3
สเปกภาษาและลำดับความสำคัญของตัวดำเนินการ
- อย่างไม่เป็นทางการ TRRE นิยามเป็นคู่
pattern-to-match:pattern-to-generate - ฝั่งซ้าย
pattern-to-matchอาจเป็นสตริงหรือ regular expression ก็ได้ - ฝั่งขวา
pattern-to-generateโดยทั่วไปเป็นสตริง แต่ก็เป็น regular expression ได้เช่นกัน - ปัจจุบันตัวดำเนินการ
:ถูกปฏิบัติเป็นแบบ ไม่จับกลุ่มทั้งซ้ายและขวา และรูปแบบTRRE:TRREไม่ได้รับอนุญาตตามไวยากรณ์- รูปแบบนี้มีความหมายโดยธรรมชาติว่าเป็นการประกอบความสัมพันธ์ที่ TRRE นิยามไว้ แต่ยังถูกตัดออกเพราะความซับซ้อนอาจสูงขึ้น
- ลำดับความสำคัญของตัวดำเนินการจากสูงไปต่ำมีดังนี้
- อักขระ escape
\ - bracket expression
[] - การจัดกลุ่ม
() - การทำซ้ำ
* + ? {m,n} - การต่อกัน
- Transduction
: - การเลือกทางเลือก
|
- อักขระ escape
โหมดและความ greedy
trreรองรับสองโหมด- Scan Mode: โหมดเริ่มต้น ใช้การแปลงตามลำดับ
- Match Mode: ใช้แฟล็ก
-mและตรวจสอบว่าทั้งสตริงตรงกับ expression หรือไม่
- ตัวเลือก
-aสร้างเอาต์พุตทั้งหมดที่เป็นไปได้ - modifier
?ทำให้ตัวดำเนินการ*,+,{,}เป็นแบบ non-greedy<(.:)*>พิมพ์<>จาก<cat><dog><(.:)*?>พิมพ์<><>จากอินพุตเดียวกัน
- ยังมีตัวอย่างการเปลี่ยนเนื้อหาภายในแท็กหรือวงเล็บด้วย
<(.*?:cat)>เปลี่ยน<dog> <mouse>เป็น<cat> <cat>
การ implementation บน FST และ determinization
- TRRE สร้าง Finite State Transducer(FST) ภายใน
- FST คล้ายกับ Finite State Automaton(FSA) ที่ใช้ใน regular expression ทั่วไป แต่จัดการคู่ input-output แทนสตริงเดี่ยว
- ความแตกต่างหลักของ TRRE มีดังนี้
- นิยาม ความสัมพันธ์ทวิภาค ระหว่าง regular language สองชุด
- ใช้ FST แทน FSA ในการอนุมาน
- รองรับการทำ determinization แบบ on-the-fly เชิงทดลองเพื่อประสิทธิภาพ
- ในเอนจิน regex ทั่วไป determinization จะเปลี่ยน nondeterministic automaton เป็น deterministic automaton ทำให้อนุมานได้ในเวลาเชิงเส้นตามความยาวสตริงอินพุต
- ใน TRRE ก็ใช้แนวทางคล้ายกันได้ แต่ไม่สามารถเปลี่ยนตัวแปลงแบบไม่กำหนดทั้งหมด NFT เป็นตัวแปลงแบบกำหนด DFT ได้
- หากมี cycle “bad” สองชุดที่มี input label เดียวกัน การสร้าง state อาจตกอยู่ในลูปไม่สิ้นสุด
- มีวิธีตรวจจับลูปประเภทนี้ แต่มีต้นทุนสูง
ประสิทธิภาพและสถานะการติดตั้ง
- มีตัวอย่างที่ระบุว่าเวอร์ชันแบบไม่กำหนดพื้นฐานช้ากว่า
sedเล็กน้อยในการแทนที่ง่าย ๆ./trre '(vodka):(VODKA)': real0m0.046ssed 's/vodka/VODKA/': real0m0.024s
- ในงานที่ซับซ้อน มีตัวอย่างที่เวอร์ชันแบบกำหนด
trre_dftเร็วกว่าsedsed -e 's/\(.*\)/\U\1/': real0m0.508s./trre_dft '[a:A-z:Z]': real0m0.131s
- ยังไม่มีไบนารีที่ build ไว้ล่วงหน้าให้ใช้
- การติดตั้งทำโดย clone repository แล้ว build และทดสอบด้วย
make && sh test.sh - TODO ยังมีรายการต่อไปนี้
- เวอร์ชัน DFT ที่เสถียร
- รองรับ Unicode เต็มรูปแบบ
- ทำฟีเจอร์ ERE ให้ครบ
- การปฏิเสธด้วย
^ภายใน[] - character class
- สัญลักษณ์ anchor
$^
- การปฏิเสธด้วย
- การจัดการช่วงอย่างมีประสิทธิภาพ
แนวทางที่อ้างอิง
- แนวทางการจับคู่ regular expression ได้แรงบันดาลใจอย่างมากจาก Regular Expression Matching Can Be Simple And Fast ของ Russ Cox
- แนวคิด transducer determinization มาจาก Finitely Subsequential Transducers ของ Cyril Allauzen และ Mehryar Mohri
- แนวทางการ parse ใช้ Double-E algorithm ของ Erik Eidt และใกล้เคียงกับ Shunting Yard algorithm แบบคลาสสิก
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
น่าสนใจว่าโปรเจกต์นี้จะไปทางไหน แต่ ลำดับความสำคัญของตัวดำเนินการ ดูไม่เป็นธรรมชาติ และดูเหมือนคนอื่น ๆ ในเธรดนี้ก็รู้สึกคล้ายกัน
cat:dogทำให้คาดโดยธรรมชาติว่ามันจะเท่ากับ(cat):(dog)ไม่ใช่ca(t:d)ogผมเองก็งงเหมือนกันที่
cat:dogถูกตีความเป็นca(t:d)ogไม่ใช่(cat):(dog)แต่พอนึกได้ว่าทุกคนใช้ regex กันผิดไปนิดหน่อยก็เข้าใจขึ้น regex “เดิมที” ควรมองว่าเป็น ตัวสร้างสตริง ไม่ใช่ matcher ดังนั้นcat|dogในเชิงรูปแบบจึงมองได้ว่าขยายเป็นเซตอย่าง{catog,cadog}ในการ matching ก็แค่เอาเซตของสตริงนี้ไปทำ substring matching กับข้อความที่ใหญ่กว่า ปัญหาคือ regex engine ส่วนใหญ่ในโลกจริงไม่ได้ทำงานแบบนี้ และมีพฤติกรรมแปลก ๆ หลายอย่างเพื่อให้ตรงกับความคาดหวังหรือเพื่อประสิทธิภาพ
ถ้าลองทดสอบเครื่องมือ regex หลาย ๆ ตัว จะได้รูปแบบแปรผันอย่าง
(cat)|(dog)หรือ(cat)|(dog)|(ca[td]og)ดังนั้นจากมุมมองที่เป็นทางการกว่า ผมคิดว่าcat:dogสร้างca(t:d)ogไม่ใช่(cat):(dog)จึงถูกต้องแล้ว แต่เพราะประสบการณ์หลายสิบปีที่เราใช้ regex อย่างผิดวัตถุประสงค์ให้เป็นเครื่องมือ matching ที่ปรับตามความคาดหวังของผู้ใช้ ตอนนี้ทุกคนเลยใส่วงเล็บครอบนิพจน์ที่อยากแทนที่ข้อเสนอนี้น่าสนใจและออกแบบมาดี แต่สุดท้ายให้ความรู้สึกเหมือนพยายามพา regex กลับไปสู่ โมเดลตัวสร้าง ดั้งเดิม ปัญหาน่าจะอยู่ที่ฝั่งเครื่องมือมากกว่าไวยากรณ์
ผมเคยทำงานใกล้เคียงกับสายนี้มาก่อน และถ้าคุณไม่เคยคิดถึง regex ในฐานะตัวสร้างเซตของสตริง ลองเล่นได้ที่นี่: https://onlinestringtools.com/generate-string-from-regex
อย่างไรก็ตาม พฤติกรรมของเครื่องมือสร้างแบบนี้ก็มีความเฉพาะมาก เครื่องมือที่ผมเคยใช้มีหลายวิธีในการจำกัด generator เช่นกำหนดข้อจำกัดให้ closure เป็นต้น
ถ้าเลื่อนไปไว้หลัง concatenation ก็อาจเกิดปัญหาอื่น เช่นกับ
:ที่ไม่ associative,cat:dog:mouseอาจควรเป็นสิ่งผิดกฎหมาย แต่ยังไม่แน่ใจว่าจะจัดการอย่างไรในเวอร์ชันปัจจุบัน จะใส่ epsilon หรือสตริงว่างเข้าไป เช่นถ้าต้องการลบโดยข้ามทีละตัว ในทางเทคนิคคุณสามารถรัน
..:ซึ่งคือ.(.:eps)ได้ผลลัพธ์ของ
echo 'abcde' | ./trre '..:'คือ'ace'จริง ๆ แล้วการผูก
:อาจมีความหมายเป็น composition ของ regular relation ได้ด้วย แต่ตอนนี้ผมมองว่ามันซับซ้อนเกินไป[a-z:A-Z]แทน[a:A-z:Z]และ[a-y:b-z;z:a]แทน[a:b-y:zz:a]ถ้าสนใจ finite-state transducer และเครื่องมือที่เกี่ยวข้อง XFST (Xerox Finite-State Transducer) ก็น่าดู ใช้ในงานภาษาศาสตร์เชิงคำนวณมากว่า 20 ปีแล้ว
เคยมีนักวิจัยชาวฟินแลนด์จาก PARC มาในคลาสที่ UT แล้วสาธิตวิธีจัดการสัณฐานวิทยาภาษาฟินแลนด์ด้วย FST ซึ่งดูจากภายนอกก็ถือว่าน่าทึ่งมาก
อธิบายงานที่ทำที่ PARC
OpenFst เป็นไลบรารีสำหรับ transducer ที่ยอดเยี่ยมจริง ๆ บทเรียนตัวอย่างการใช้ Pynini ที่ทำเป็นโจทย์โดย Johns Hopkins และที่อื่น ๆ ก็ใช้ได้ดี
[1] https://www.openfst.org/twiki/bin/view/GRM/Pynini
[2] https://www.openfst.org/
ถ้ากำลังมองหาทางเลือกแทน regex มาตรฐาน โดยเฉพาะถ้าตรรกะของกลุ่มเข้าใจยาก หรืออยากได้ expression ที่ดูแลรักษาได้ Rosie Pattern Language อาจเหมาะ
https://gitlab.com/rosie-pattern-language/rosie/-/blob/maste...
https://rosie-lang.org/about/
เจ๋งดี ผมเคยเขียนวิทยานิพนธ์ Diplom ด้านวิทยาการคอมพิวเตอร์ราวปี 1997 ด้วย finite-state transducer และมันไม่ใช่เรื่องเล็กน้อยกว่าที่คิดมาก
งานคือการ implement composition และ DFA เมื่อทำได้ รวมถึง transducer ที่ประกอบกันแล้วด้วย เป็นเรื่อง “พีชคณิตของ finite-state transducer” และ use case คือสัณฐานวิทยา หัวข้อนี้ถูกประเมินต่ำเกินไปมาก จนผมต้องหยุดไว้ประมาณกลางทาง ดังนั้นขอคารวะ
เรื่องไวยากรณ์ ผมสงสัยว่าต้องการให้
:จับกลุ่มแน่นกว่า concatenationabจริง ๆ หรือเปล่าดีใจที่เห็นว่า 20 ปีผ่านไปโปรเจกต์นี้ยังเดินหน้าต่อ: https://www.openfst.org/twiki/bin/view/FST/WebHome
ผมยังไม่แน่ใจว่า
:ควรจับกลุ่มแน่นกว่า concatenation หรือไม่ ดูตัวอย่างประมาณ 100 ตัวแล้วผมคิดว่าวิธีปัจจุบัน คือให้:มีลำดับต่ำกว่า.ดูเป็นธรรมชาติกว่า แต่ในโค้ดเปลี่ยนได้ด้วยการเปลี่ยนตัวเลขแค่ตัวเดียวจริง ๆ เพราะงั้นเลยเอามาโพสต์ที่นี่ และต้องการฟีดแบ็กจริง ๆทันทีที่ต้องการทำ การแทนที่เชิงโครงสร้าง แบบใดแบบหนึ่ง วิธีนี้ก็ดูเหมือนจะไม่พอ ตัวอย่างเช่น บางครั้งเราอยากทำอะไรอย่าง
s/"([^"]*)"/'$1'/ยิ่งไปกว่านั้น ถ้าสามารถเปลี่ยนสิ่งที่แมตช์กับ
[']ภายใน[^"]ให้เป็น\'ได้ ก็น่าจะมีประโยชน์มากขึ้นโดยทั่วไปกว่านั้น regex กำหนด parse tree ให้กับผลการแมตช์โดยพฤตินัย ดังนั้นถ้าสามารถทำการแปลงที่ทั่วไปกว่านี้กับ tree นั้นได้ก็น่าจะมีประโยชน์
":'(':(\\')|[^"'])*":'"..."และเปลี่ยนเครื่องหมายคำพูดเป็นอัญประกาศเดี่ยว'ทำได้ด้วยนิพจน์นี้:
echo '"hello world" "hello again!"' | ./trre "\":'.+?:-\":'"ผลลัพธ์คือ
'-' '-'กล่าวคือ ด้วยนิพจน์
".+?:-"จะแทนที่ข้อความภายใน""ด้วยเครื่องหมาย-พร้อมกับเปลี่ยนเครื่องหมายคำพูดรอบ ๆ ไปด้วย เครื่องหมายคำถามหมายถึง โหมดไม่ละโมบดูเหมือนทั้งโปรเจกต์จะตั้งอยู่บนข้ออ้างว่า “regex เป็นเครื่องมือที่ยอดเยี่ยมในการหารูปแบบในข้อความ แต่สำหรับการแก้ไขข้อความแล้ว มันรู้สึกไม่เป็นธรรมชาติเสมอ” แต่กลับไม่มีตัวอย่างเลย
ผมไม่เข้าใจว่าทำไม regex ถึงไม่เป็นธรรมชาติสำหรับการแก้ไข และก็ไม่รู้ว่าในที่นี้การแก้ไขหมายถึงอะไร รวมถึงไม่เข้าใจว่าทำไมผู้คนถึงลำบากกับกลุ่ม
โปรเจกต์นี้มีตัวอย่างไวยากรณ์เยอะ แต่ผมไม่เห็นว่ามันดีกว่า regex ปกติอย่างไร ถ้ามีตัวอย่างสักสองสามอันแบบ “เวอร์ชัน regex พื้นฐานเป็นแบบนี้ เวอร์ชันของผมเป็นแบบนี้ ดังนั้นจึงง่ายขึ้น” ก็น่าจะช่วยให้เข้าใจโปรเจกต์ได้
เช่น ถ้าต้องการเปลี่ยนเฉพาะ
yที่อยู่ระหว่างxกับzให้เป็นYใน Python ก็จะทำประมาณนี้:pattern = r'(x)y(z)'replacement = r'\1Y\2'result = re.sub(pattern, replacement, text)ผมอยากแทนที่สิ่งนี้ด้วยแพตเทิร์น
xy:Yz:result = re.trre('xy:Yz', text)ถ้า
x,zเป็นแพตเทิร์นที่ซับซ้อนกว่านี้ หรือเป็น regex เอง แนวทางนี้อาจสะดวกกว่าเป็นโปรเจกต์ที่ดี
โค้ด C อ่านสนุกจริง ๆ ดีมาก และตอนนี้กำลังอ่านอยู่
ขอคอมเมนต์เล็กน้อยอย่างเดียว ลิงก์
theory.pdfใน README เสียอยู่ ตัว PDF อยู่ในไดเรกทอรีdocs/ดังนั้นแค่ใส่docs/ใน URL ก็พอมีบอกไว้ว่าควรหลีกเลี่ยงการใช้
*หรือ+ในส่วนด้านขวา เพราะอาจเกิดลูปไม่รู้จบได้ แล้วทำไมไม่ห้ามไปเลยล่ะ?เข้าใจว่ามันทำให้สเปกไวยากรณ์ยากขึ้น แต่ดูไม่เห็นมีเหตุผลดี ๆ ที่จะเก็บไว้
เหตุผลเดิมคือผมตั้งใจจะ implement โอเปอเรชันที่น่าสนใจชื่อ การประกอบตัวแปลง เราสามารถทำโอเปอเรชันง่าย ๆ กับสตริงและประกอบ trre ให้เหมือนฟิลเตอร์ได้ แต่ยังทำไม่เสร็จ ดังนั้นก็เป็นประเด็นที่ถูกต้องจริง ๆ
เป็นการสำรวจที่น่าสนใจ แต่ยังขาดตัวอย่างว่าทำไมในทางปฏิบัติมันถึงดีกว่า แน่นอนว่าอาจเป็นเพราะผมคุ้นกับ regex มานานเกินไปก็ได้
เช่น ผมไม่เห็นว่า
(cat):(dog)ของ trre ดีกว่าs/cat/dogอย่างไร หรือ(x:)orดีกว่าs/xor/orตรงไหน ตัวอย่างแทบทั้งหมดในหัวผมสามารถเทียบเป็น regex ที่ค่อนข้างง่ายได้ถ้ามีข้อดีหลักอยู่จริง ก็น่าจะอยู่ทางด้าน ตรรกะของกลุ่ม ดังนั้นตัวอย่างควรโฟกัสไปทางนั้นจะดี ก่อนอธิบายไวยากรณ์พื้นฐาน น่าจะดีกว่าถ้าอธิบายก่อนว่าทำไมมันถึงเป็นตัวเลือกที่ดีกว่า
ตัวอย่างรหัสซีซาร์ทำให้รู้สึกว่าจำเป็นต้องมีฟีเจอร์ “นำสิ่งนี้ไปใช้แบบย้อนกลับ” มาก ๆ ซึ่งเป็นคำขอที่พบบ่อยในการแทนที่ข้อความจำนวนมาก และในตัวอย่างนี้ก็ชัดเป็นพิเศษ สมองโปรแกรมเมอร์จะร้องขึ้นมาทันทีว่า “ทำไมต้องแสดงตรรกะเดียวกันสองครั้ง?”
ยังไม่แน่ใจว่ามีประโยชน์หรือไม่ แต่การสำรวจทางเลือกแทนสถานะเดิมที่อยู่มานานเป็นเรื่องยอดเยี่ยม ปกติความพยายามแบบนั้นมีโอกาสสูงที่จะไม่สำเร็จ แต่ถึงอย่างนั้นการสำรวจก็น่าชื่นชม
สเปกดูเหมือนจะยังขาดรายละเอียดไปมาก ตัวอย่างแรกก็ดูแปลกแล้ว:
$ echo 'cat' | trre 'c:da:ot:g'dogไม่รู้ว่าเกิดอะไรขึ้นตรงนี้ ไวยากรณ์เขียนไว้แบบนี้:
TRRE <- TRRE* TRRE|TRRE TRRE.TRRETRRE <- REGEX REGEX:REGEXparse tree ตรงนี้คืออะไร? ทำไม
cถึงไม่ถูกเปลี่ยนเป็นda? หรือทำไมcถึงไม่ถูกลบ แล้วdaถูกเปลี่ยนเป็นot?ไอเดียที่ให้ความหมายแบบค้นหา/แทนที่ที่เข้าใจง่ายกว่าตัวดำเนินการจัดกลุ่มนั้นดี สมัย MS-DOS เคยทำอะไรอย่าง
ren .log .txtได้และมันก็ทำงาน แม้จะฟังดูไม่สมเหตุสมผลเลยในวิธีคิดแบบ bash ยุคใหม่ แต่ดูปุ๊บก็รู้ชัดมากว่าต้องการทำอะไรถ้าเรียกตัวดำเนินการนั้นอย่างชัดเจนว่า
~ตัวอย่างจะดูเป็นแบบนี้:$ echo 'cat' | trre 'c:d~a:o~t:g'dogถ้าใส่วงเล็บที่ไม่จำเป็นเข้าไปก็จะเป็นแบบนี้:
$ echo 'cat' | trre '(c:d)~(a:o)~(t:g)'dogเหตุผลที่
cไม่ถูกเปลี่ยนเป็นdaล้วนเป็นเพราะลำดับความสำคัญ ดูจากการสนทนานี้แล้ว ผมคงเลือกลำดับความสำคัญผิด และนั่นก่อให้เกิดความสับสนตารางลำดับความสำคัญปัจจุบันเป็นดังนี้:
| 1 | อักขระ escape | \ || 2 | นิพจน์วงเล็บเหลี่ยม | [] || 3 | การจัดกลุ่ม | () || 4 | การทำซ้ำ ERE ของอักขระเดี่ยว | * + ? {m,n} || 5 | การแปลง | : || 6 | การเชื่อมต่อ | . (โดยนัย) || 8 | การเลือก | | |ดังนั้น
:จึงจับกลุ่มแน่นกว่า.หรือการเชื่อมต่อโดยนัยแต่ถ้ากำหนดแทนว่า regex ต้องไม่ว่าง ตัวอย่างการลบก็จะพัง แต่ความกำกวมจะย้ายไปอยู่ที่การเชื่อมต่อแทน กล่าวคือจะกำกวมว่าเป็น
(((c:d)(a:o))(t:g))หรือ((c:d)((a:o)(d:g)))หากสมมติเรื่อง associativity ความแตกต่างนี้ก็คงไม่สำคัญc:d,a:คือไม่มีอะไร และot:gแต่พอกลับมาอ่านอีกครั้งก็สับสนจริง ๆ และในเชิงทฤษฎี สิ่งที่ชี้ให้เห็นนั้นถูกต้อง หลังจากอ่าน repository แล้ว ผมเองก็เริ่มเชื่อว่า
cควรถูกเปลี่ยนเป็นdaแต่ก็ยังไม่มั่นใจ