เหตุใดจึงใช้ Rust สำหรับการทำโทเคไนซ์และการแยกวิเคราะห์ไวยากรณ์

 (xnacly.me)
2 คะแนน โดย GN⁺ 2024-11-09 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • sqleibniz เป็น เครื่องมือวิเคราะห์แบบสถิต ที่ต้องการตรวจสอบไวยากรณ์ของ SQL dialect แบบ SQLite การมีอยู่ของตาราง·คอลัมน์·ฟังก์ชัน และเงื่อนไขขณะรันไทม์ ดังนั้นการทำโทเคไนซ์และการพาร์สจึงเป็นขั้นตอนสำคัญ
  • macro_rules! ของ Rust ช่วยสร้างโครงสร้าง AST node, การ implement trait Node, และ table-driven tests แบบ Go ได้โดยไม่ต้องเขียนซ้ำ
  • เมื่อใช้แพตเทิร์น matches! และ match ก็สามารถถ่ายทอด แขนงไวยากรณ์ อย่าง numeric literal ของ SQLite, identifier, symbol และ EXPLAIN QUERY PLAN ให้ใกล้เคียงกับโค้ดได้
  • Option อย่าง is_some_and, map, map_or และตัวดำเนินการ ? ช่วยให้การจัดการอินพุต·สตรีมโทเคนในเรื่องการมีอยู่ของค่า การแปลงค่า ค่าเริ่มต้น และการส่งต่อข้อผิดพลาด กระชับขึ้น
  • iterator ของ Rust ถูกนำมาใช้กับการลบ _ ออกจาก numeric literal, การตรวจสอบอักขระฐานสิบหกภายใน blob, และการคำนวณตำแหน่งข้อผิดพลาด ซึ่งส่งผลให้โค้ดสำหรับโทเคไนซ์·พาร์สอ่านง่ายขึ้น

โฟลว์การวิเคราะห์ของ sqleibniz

  • sqleibniz เป็นเครื่องมือวิเคราะห์ SQL ที่กำลังพัฒนาสำหรับ SQLite dialect
  • ตั้งใจให้ทำ การตรวจสอบไวยากรณ์ กับอินพุต SQL, ตรวจว่ามีตาราง·คอลัมน์·ฟังก์ชันอยู่จริงหรือไม่, และตรวจเงื่อนไขโดยเชื่อมกับ SQLite runtime ในตัว
  • ข้อความผิดพลาดมีเป้าหมายให้ให้ทั้งบริบทและคำอธิบาย พร้อมรูปแบบที่สามารถเพิกเฉยต่อการวินิจฉัยบางรายการได้
  • โฟลว์การวิเคราะห์เริ่มจาก lexing/tokenizing แล้วตามด้วยการพาร์ส SQL ตามเอกสารของ SQLite และการวิเคราะห์โครงสร้างผลลัพธ์
  • หลังจากทำส่วน static analysis เสร็จแล้ว ยังมีแผนจะเขียน LSP server สำหรับ SQL ด้วย

ลดการเขียนซ้ำของ AST node ด้วยแมโคร

  • AST node ของ sqleibniz เป็น struct ที่เก็บ Token และทุก node ต้อง implement trait Node
  • trait Node ใช้ std::fmt::Debug เป็น supertrait ทำให้มีเพียง type ที่ตรงตาม Debug เท่านั้นจึงจะ implement Node ได้
  • เพื่อไม่ให้ต้องเขียนซ้ำทั้งการประกาศ struct และ fn token(&self) -> &Token สำหรับแต่ละ node แมโคร node! จึงถูกใช้สร้างสิ่งเหล่านี้
    • ชื่อ node รับผ่าน metavariable แบบ ident
    • สตริงเอกสารรับผ่าน metavariable แบบ literal
    • ฟิลด์เพิ่มเติมประมวลผลซ้ำในรูปแบบ $($field_name:ident:$field_type:ty),*
  • node Literal มีเพียงฟิลด์ token ส่วน Explain เพิ่มฟิลด์ child: Option<Box<dyn Node>>
  • คอมเมนต์เอกสารถูกส่งให้คอมไพเลอร์ผ่านรูปแบบ #[doc = $documentation] แทน ///

ทำ table-driven tests แบบ Go ด้วยแมโครของ Rust

  • แนวทางแบบ table-driven test ของ Go ที่วนอาร์เรย์ของเคสอินพุตและรันแต่ละเคสเป็นการทดสอบแยกกัน ถูกทำซ้ำใน Rust ด้วยแมโคร
  • การทดสอบ lexer ใช้แมโคร test_group_pass_assert! และ test_group_fail!
    • การทดสอบที่ต้องผ่านจะป้อนอินพุตเข้า Lexer แล้วเปรียบเทียบรายการ type ของโทเคนจากผล Lexer.run() กับค่าที่คาดหวัง
    • การทดสอบที่ต้องล้มเหลวจะตรวจว่าเวกเตอร์โทเคนผลลัพธ์ว่างเปล่า และ Lexer.errors มีข้อผิดพลาดอย่างน้อยหนึ่งรายการ
    • เมื่อรัน cargo test แต่ละเคสจะแสดงผลตอบกลับ ok หรือ fail ราวกับเป็นฟังก์ชันทดสอบแยกกัน
  • การทดสอบ parser ใช้โครงสร้างเดียวกัน แต่จะ initialize Parser หลังรัน lexer แล้วตรวจผลของ parse()
    • EXPLAIN VACUUM; และ EXPLAIN QUERY PLAN VACUUM; เป็นเคสที่ผ่าน
    • EXPLAIN; และ EXPLAIN QUERY PLAN; เป็นเคสที่ล้มเหลว
    • เคสที่ล้มเหลวใช้ตรวจเงื่อนไขตามไวยากรณ์ sql-stmt ของ SQLite ว่าหลัง EXPLAIN ต้องมี statement ตามมา

จุดที่ไม่สะดวกของ macro_rules!

  • ภายใน macro_rules! การรองรับของ rust-analyzer ยังมีจำกัด
    • ไม่มี IntelliSense จริง
    • ไม่มี go to definition
    • ไม่มี hover ของ literal และ signature ของโครงสร้างภาษา
  • cargo fmt จะไม่จัดรูปแบบหรือย่อหน้าให้ทั้งภายใน macro_rules! และจุดที่เรียกใช้แมโคร
  • treesitter และ chroma บางครั้งมีปัญหากับ syntax highlighting ของ macro_rules!
  • เอกสารของแมโครก็ค่อนข้างมีน้อย

matches! และ match ที่โดดเด่นในการจับคู่อักขระ

  • การเปรียบเทียบอักขระใน lexer เป็นพื้นฐานของการประมวลผลอื่น ๆ และแมโคร matches! กับแพตเทิร์น match ของ Rust ทำให้ส่วนนี้กระชับขึ้น
  • การตัดสิน numeric ของ SQLite เขียนด้วย matches!
    • +, -
    • _
    • .
    • a..=f, A..=F
    • 0..=9
  • การตัดสิน identifier ก็เขียนได้ในรูปแบบอย่าง matches!(c, 'a'..='z' | 'A'..='Z' | '_' | '0'..='9')
  • ลูปหลักของ lexer แยกการทำงานตามอักขระปัจจุบันด้วย match
    • ข้ามอักขระ whitespace
    • *, ;, ,, % เป็นต้น จะสร้างโทเคนที่สอดคล้องกันทีละตัว
    • ตัวอย่างการจัดการ symbol ที่ไม่รู้จักถูกละไว้และแสดงเป็น panic!("whoops")

จัดการโครงสร้างไวยากรณ์ SQL ด้วยการจับคู่โทเคน

  • lexer เปลี่ยนสตรีมอักขระเป็นสตรีมของ struct Token ที่มีข้อมูลตำแหน่งและชนิด จากนั้น parser จะนำไปใช้สร้าง AST
  • enum Type รวมถึง Keyword, Ident, Number, String, Blob, Boolean, ParamName, Param, Dot, Asteriks, Semicolon, Percent, Comma, Eof เป็นต้น
  • sql_stmt_prefix เป็นฟังก์ชัน parser ที่จัดการ statement EXPLAIN ตามเอกสารของ SQLite
    • หากโทเคนปัจจุบันคือ Type::Keyword(Keyword::EXPLAIN) จะสร้าง node Explain และ consume EXPLAIN
    • ถ้าโทเคนถัดไปคือ QUERY ก็จะ consume QUERY และ PLAN ต่อเนื่องกัน
    • หลังจากนั้นจึงพาร์ส SQL statement จริงเป็น child
    • ถ้าไม่ใช่ EXPLAIN ก็จะเรียกการจัดการ sql_stmt ปกติ
  • literal_value สร้าง node Literal จาก keyword literal เช่น NULL, CURRENT_TIME, CURRENT_DATE, CURRENT_TIMESTAMP รวมถึง string, number, blob, boolean

การแสดงข้อผิดพลาดและการใช้ Option

  • lexer และ parser แสดงข้อผิดพลาดให้ผู้ใช้เห็นในกรณีอย่างการลืมใส่ semicolon ท้าย statement ของ SQL
  • ตัวดำเนินการ ? ของ Rust ใช้สำหรับการจัดการและส่งต่อข้อผิดพลาด
  • Option::is_some_and ใช้ตรวจว่ามีอักขระถัดไปหรืออักขระปัจจุบันอยู่ และตรงตามเงื่อนไขหรือไม่
    • self.source.get(self.pos + 1).is_some_and(...)
    • self.source.get(self.pos).is_some_and(...)
  • Option::map ถูกใช้เพื่อแปลงไบต์ถัดไปจากอินพุต Vec<u8> ให้เป็น char
  • Option::map_or ใช้ในรูปแบบที่เปรียบเทียบ type เฉพาะเมื่อมีโทเคนปัจจุบันหรือโทเคนถัดไปอยู่เท่านั้น และถ้าไม่มีก็คืนค่า false

จัดการตัวเลขและ blob ด้วย iterator

  • การพาร์สตัวเลขของ SQLite อนุญาตให้มี _ ได้ แต่การพาร์สตัวเลขของ Rust ไม่อนุญาต _ ดังนั้น lexer จึง consume ทั้งหมดรวม _ ไปก่อน แล้วค่อยลบออกก่อนพาร์ส
  • กระบวนการนี้เขียนเป็น iterator chain
    • นำ byte slice มาใช้
    • แปลงแต่ละไบต์เป็น char
    • filter เฉพาะอักขระที่ไม่ใช่ _
    • collect กลับเป็น String
  • ในกรณีนี้ใช้ unwrap_or_default() แต่ถึงเป็นสตริงว่างก็ไม่ถือว่าเป็นตัวเลขที่ถูกต้องอยู่ดี ดังนั้น parser ก็จะล้มเหลวอยู่แล้ว
  • ใน Go หากจะทำแบบเดียวกัน ต้องวนรายการอักขระ เขียนไบต์ลง strings.Builder แล้วค่อยสร้างสตริงกลับมาอีกครั้ง
  • SQLite blob รองรับข้อมูลฐานสิบหกในรูปแบบ x'<hex>' ดังนั้นจึงวนแต่ละอักขระของสตริงด้วย chars().enumerate() เพื่อตรวจว่าเป็น is_ascii_hexdigit() หรือไม่
    • enumerate ถูกใช้เพื่อดึงข้อมูลตำแหน่งของอักขระที่ผิดสำหรับการแสดงข้อผิดพลาด
    • เมื่อพบอักขระฐานสิบหกที่ไม่ถูกต้อง ก็จะสร้างข้อผิดพลาดแล้วหยุดการประมวลผล

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

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

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

  • ถ้าเป็นเมื่อสองเดือนก่อนก็คงคิดเหมือนผู้เขียน แต่กลับชนกับขอบเขตอันแข็งกระด้างของ Rust อย่าง borrow checker อยู่เรื่อย ๆ
    ชนิดข้อมูลเชิงพีชคณิต เช่น Enum และ pattern matching นั้นยอดเยี่ยมจริง ๆ แต่เพราะ borrow checker และการต้องคำนึงถึงหน่วยความจำระดับต่ำ ทำให้ใช้เวลาต่อสู้กับ borrow checker มากกว่าปัญหาภาษาโปรแกรมมิงซึ่งเป็นแกนหลักของโปรเจกต์
    ดังนั้นการทำ tokenization และ parsing ยังพอไหว แต่ตัว interpreter และ type checking กลายเป็นความทรมาน และระหว่างมองหาภาษาที่เหมาะกว่า หลังจากพิจารณา F#, Zig/C, Go แล้วก็ได้พบกับ OCaml
    ไวยากรณ์ดูเหมือน Haskell ที่เป็นมิตร และดูเหมือน Rust ที่ไม่มี lifetime จึงทำให้เชื่อมั่น อีกทั้งคอมไพเลอร์ Rust ตัวแรกก็เขียนด้วย OCaml และเป็นที่รู้จักกันดีในสายภาษาโปรแกรมมิง
    ยังอยู่ระหว่างเรียนจึงประเมินอย่างเป็นธรรมได้ยาก แต่จนถึงตอนนี้ก็ใกล้เคียงกับสิ่งที่ตามหาอยู่พอดี

    • พอมีคนพูดถึง Go ทีไรก็รู้สึกหงุดหงิดอย่างบอกไม่ถูกเสมอ
      มันใช้งานได้จริง เร็ว ไม่ได้ระดับต่ำจริง ๆ คอมไพล์ก็เร็ว และเหนือสิ่งอื่นใดคือได้รับความนิยมมากจนมีไลบรารีครบ เลยรู้สึกว่าควรใช้
      แต่ตัวภาษาเองกลับไม่ชอบอย่างแทบไร้เหตุผล และรู้สึกว่าทุกด้านดูน่าเกลียด
      เป็นภาษาที่คนสาย C สร้างขึ้นในปี 2009 แต่แม้เทียบกับมาตรฐานตอนนั้น ก็เหมือนจะไม่รู้จักสิ่งน่าสนใจที่เกิดขึ้นในวงการออกแบบภาษาโปรแกรมมิงตลอด 20 ปีก่อนหน้า
      แม้แต่ PHP ในปี 2009 ยังเป็นภาษาที่ทันสมัยกว่าและออกแบบดีกว่า Go และก็สลัดความรู้สึกไม่ได้ว่า Go หลังจากนั้นก็ไม่ได้ดีขึ้นมากนัก
    • ผมมองว่าหัวใจสำคัญเวลาจัดการ abstract syntax tree ใน Rust คืออย่าเก็บสิ่งอย่างสตริงไว้ในต้นไม้
      ให้ใช้ของที่ clone ได้ถูกและทำ interning ได้แทน เหมือนกับไลบรารีสตริงแบบสแตติก และสำหรับตำแหน่งในข้อความก็ควรใช้แค่ดัชนี
      ถ้าเป็นไปได้ควรหลีกเลี่ยงการเก็บ reference โดยเด็ดขาด
      ยิ่งเก็บของที่ clone ได้แบบ cheap/free มากเท่าไร ก็ยิ่งต้องสู้กับ borrow checker น้อยลง และเมื่อจำเป็นก็เปลี่ยนไปใช้ clone ได้
      ในส่วน interpreter จริง ๆ ไลบรารีที่ช่วยจัดการหน่วยความจำแบบ arena ค่อนข้างมีประโยชน์
      เป็นโดเมนที่เฉพาะทางมาก แต่ให้ทั้งประสิทธิภาพและความใช้งานง่าย และโปรเจกต์อย่าง Ruffle ก็ใช้แพตเทิร์นแบบนี้มาก
      อย่างไรก็ตาม OCaml และ Haskell ทำสิ่งเหล่านี้ให้ “ฟรี” ด้วย reference counting และ garbage collection ในตัว แต่ถึงอย่างนั้นก็ยังชอบไอเดียที่จะไปได้เร็วมากด้วย Rust
    • ตลอด 1 ปีที่ผ่านมาใช้ Go ค่อนข้างมาก แต่คิดว่าคงไม่ใช้กับ การเขียน parser
      Go ใกล้เคียงกับ C ที่ทำให้ทันสมัยขึ้น และโมเดลที่ให้มาก็เรียบง่ายมาก
      ถ้ามาจาก C# ความเรียบง่ายนั้นกลับทำให้เรียนยากขึ้นเสียอีก จุดแข็งคือภาระด้านแนวคิดต่ำ และเหมาะกับแอปพลิเคชันเล็ก ๆ ที่โฟกัสชัดเจน ซึ่งยอมรับการแลกเปลี่ยนด้วยความยืดยาวได้
      ถ้าจะแนะนำ ผมว่า F# หรือ C# สมัยใหม่ก็ใช้ได้
      แม้ Microsoft จะเกี่ยวข้องอยู่ แต่ถ้าจะใช้ชีวิตในโลกที่ไม่แตะของที่บริษัทเทคยักษ์ร้าย ๆ สร้างเลย ก็จะลำบาก
      Java, Go, Python, TypeScript/JavaScript, Swift ก็เข้าข่ายนี้ทั้งหมด แล้วทางเลือกแทบจะไม่เหลือ
      อยากรู้ว่าหลังจากใช้ OCaml สัก 1 ปีแล้วจะคิดอย่างไร
      สาย Haskell น่าสนใจ แต่สำหรับผม Haskell เองให้ผลตอบแทนไม่คุ้มกับ learning curve และ Rust ก็คล้ายกัน
      C# ผมขุดลึกและชำนาญระบบชนิดข้อมูลแล้ว แต่ไม่มีเวลาจะเจาะ Rust ให้ลึกระดับนั้น
    • Go ถูกใช้ฝั่งไคลเอนต์เยอะเหมือนกัน และบนมือถือก็รองรับค่อนข้างดีเพราะ go-mobile
      แน่นอนว่ามันเพิ่มขนาดไบนารีและการใช้หน่วยความจำราว 10–20MB แต่ตามมาตรฐานทุกวันนี้แทบไม่ใช่อะไรเลย
      ตัวอย่างเช่น Tailscale ดูเหมือนจะใช้ Go เป็นเลเยอร์ WireGuard ข้ามแพลตฟอร์มในแอปมือถือและเดสก์ท็อป และดูเหมือนทำงานได้ดี
      คงไม่ใช้ Go สร้าง native UI แต่สำหรับงานระดับต่ำถือว่ายอดเยี่ยม
      TinyGo ยังทำให้เขียน Go สำหรับไมโครคอนโทรลเลอร์หรือ WebAssembly ได้ด้วย แม้มีหลายอย่างที่ยังไม่รองรับ แต่ก็ใช้ไลบรารีมาตรฐานได้ส่วนใหญ่
    • ผมคงไม่เรียก Go ว่าเป็น ภาษา server-side
      ตัวอย่างเช่น คอมไพเลอร์ Go เองก็เขียนด้วย Go
      ด้วยการ cross-compile และไบนารีที่ค่อนข้างเล็ก ทำให้ deployment ง่ายมาก
      แต่ก็จริงที่ขาด syntactic sugar และไม่ค่อยเหมาะกับ pattern matching แบบ functional style

  • มองดูแล้ววิธีเข้าหา parsing ค่อนข้างแปลก และรู้สึกว่าผู้เขียนยังไม่ค่อยคุ้นกับ Rust และ แนวคิดภาษาโปรแกรมมิง ที่เป็นพื้นฐานของมันเท่าไร
    ลองดูบางจุด AST น่าจะง่ายขึ้นมากถ้านิยามเป็นชนิดข้อมูลเชิงพีชคณิต
    ไวยากรณ์ของ sqlite ไม่น่าจะขยายแบบอยู่ ๆ ก็เพิ่มโหนดใหม่จำนวนมากจนต้องเข้ารหัสซับซ้อน
    การเข้ารหัสปัจจุบันดูเหมือนรูปแบบที่คนคุ้นกับ object-oriented แต่มักไม่คุ้นกับชนิดข้อมูลเชิงพีชคณิตจะนึกออก
    คำพูดที่ว่า “macro ทำงานต่างกันไปในภาษาส่วนใหญ่ แต่เหตุผลหลักคือการกำจัดโค้ดซ้ำและลดการทำซ้ำ” ก็พูดแบบเดียวกันได้กับกลไก abstraction ทุกอย่างอย่างฟังก์ชัน
    คุณลักษณะที่นิยาม macro คือมันถูกรันใน เวลา compile
    ถ้าอยากดูวิธีจัดโครงสร้าง parser ให้สะอาด งานวิจัยเรื่อง parser combinator อาจเป็นจุดเริ่มต้นที่ดี

    • ผู้เขียนไม่เคยอ้างว่าเป็นโปรแกรมเมอร์มากประสบการณ์
      ชื่อบล็อกก็เป็น “Why I love ...” และแม้คำท้วงติงจะดูมีเหตุผล แต่การชี้ว่าขาดประสบการณ์ดูไม่จำเป็นนัก
      การที่ใครสักคนชอบการเขียนโปรแกรมเป็นเรื่องดี และประสบการณ์จะตามมาเอง
    • ในบริบทของบทความบล็อก ผู้เขียนต้องการสร้างนิยาม struct
      เรื่องนี้ทำด้วย ฟังก์ชัน ไม่ได้

  • จากมุมมองของคนที่เคยเขียนพาร์เซอร์เล็ก ๆ สำหรับสัญกรณ์หมากรุก Forsyth-Edwards [0] ผมคิดว่าในแง่ความเรียบง่ายและความอ่านง่าย Haskell เหนือกว่าอย่างชัดเจน
    มันอ่านแทบจะเหมือน BNF และแทบไม่มีพิธีกรรมทางเทคนิค ทำให้โฟกัสกับไวยากรณ์ที่ต้องการพาร์สจริง ๆ ได้
    [0] https://github.com/ryandv/chesskell/blob/master/src/Chess/Fa...
    [1] https://en.wikipedia.org/wiki/Forsyth%E2%80%93Edwards_Notati...

    • Haskell นั้นยอดเยี่ยมที่สุดแน่นอนในแง่การใช้ parser combinator แต่ถ้าจะจัดการผลลัพธ์ ก็ยังต้องอยู่กับ Haskell ต่อไป
    • นี่ไม่ใช่การใช้ Haskell ล้วน ๆ แต่เป็นการใช้ ไลบรารี parser combinator ไม่ใช่หรือ
      ผมสงสัยว่ามีเหตุผลชัดเจนอะไรที่ทำให้ใช้แนวทางคล้ายกันใน Rust ไม่ได้
      ตัวอย่างเช่น winnow [1] ดูเหมือนจะให้สไตล์เชิงประกาศได้ดีพอ และ Rust ก็มีไลบรารี parser combinator อื่น ๆ อีกหลายตัว
      [1]: https://docs.rs/winnow/latest/winnow/
    • ผมไม่มองว่า FEN เป็นตัวอย่างการพาร์สที่ยอดเยี่ยม
      เพราะสามารถทำได้ด้วยฟังก์ชันง่าย ๆ ที่มีลูปเดียว
      ไม่กี่วันก่อนผมเขียน “พาร์เซอร์” FEN สำหรับการทำ quad-bitboard แบบทดลอง และมันแทบเขียนออกมาเอง
      เพิ่มเติมคือ ผมเป็นผู้เขียน chessIO บน Hackage

  • ผมเคยเขียน eBPF disassembler และ emulator ที่ทำไปได้ครึ่งหนึ่งด้วย Rust และ Rust เป็นภาษาที่ให้ความรู้สึกค่อนข้างดีสำหรับงานจำพวกพาร์ส
    แต่เมื่อผู้เขียนยังไปไม่ถึง 1/6 ของกรณีศึกษาแล้วก็ต้องใช้ macro ผมรู้สึกว่ามันทำให้ข้อโต้แย้งของเขาอ่อนลง
    macro ไม่ใช่การสร้างโค้ดเต็มรูปแบบก็จริง แต่ก็ไม่ได้ให้ความรู้สึกว่าเป็นการทำงานอย่างเป็น idiom ภายในภาษามากนัก
    ไม่ได้จะตำหนิอะไร และผมก็คิดว่า Rust แข็งแกร่งจริง ๆ ในด้านนี้

    • ใน Rust จะนิยาม ไวยากรณ์อนันต์ ได้อย่างไร
      เช่น กฎ context-free S ::= abc|aabbcc|aaabbbccc|... สามารถพาร์ส a^Nb^Nc^N ได้อย่างมีประสิทธิภาพ และนี่เป็นตัวอย่างของ context-sensitive grammar
      เป็นตัวอย่างง่าย ๆ แต่ในของจริงก็เห็นสิ่งคล้ายกันได้ เช่น กรณีที่ภาษายอมให้กำหนด operator ได้
      Rust จัดการเรื่องแบบนี้อย่างไร
    • ถ้าเป็นไปได้ อยากให้แชร์ลิงก์ eBPF disassembler ด้วย
      ดูเท่ดี

  • จากประสบการณ์ที่เคยเขียนพาร์เซอร์และ lexer ด้วย Ragel และใช้ Go, Java, C++, C ถ้ามี ตัวสร้าง boilerplate ในระดับหนึ่ง C ล้วน ๆ ก็พอ ๆ กับโค้ด Rust ที่ผู้เขียนอธิบายไว้
    อาจดีกว่าด้วยซ้ำเพราะความเรียบง่าย
    ตัวอย่างเช่น โค้ดที่จำเป็นสำหรับ JSON parser ส่วนใหญ่มีประมาณนี้
    https://github.com/gritzko/librdx/blob/master/JSON.lex
    จริง ๆ แล้ว eBNF นั้นสร้างแค่ lexer และส่วน parser ก็ไม่ได้หวือหวาเท่าไร มี 120 บรรทัดและค่อนข้างซ้ำ ๆ
    https://github.com/gritzko/librdx/blob/master/JSON.c
    สุดท้ายผมคิดว่าโครงสร้างพื้นฐานของพาร์เซอร์วิวัฒน์ไปถึงจุดที่แค่มี eBNF ก็สร้างพาร์เซอร์ได้ และนั่นคือจุดอิ่มตัว

    • ความซ้ำ ๆ นั้นอาจมองได้ว่าเป็นข้อเสีย ไม่ใช่ข้อดี
      ผมรู้สึกว่า algebraic data types ของ Rust ทำให้การจัดการ syntax tree ที่สร้างขึ้นมาง่ายกว่ามาก
      แต่ก็เห็นด้วยว่า code generation หรือเวทมนตร์ macro เล็กน้อยสามารถทำให้ C ใช้งานได้ดีขึ้นมาก
    • ผมชอบ Ragel มากจริง ๆ
      แต่โค้ดตรงนี้
      https://github.com/gritzko/librdx/blob/master/JSON.lex
      ไม่ได้ยอมรับ [ เป็น JSON ที่ถูกต้องหรือ
      delimiter = OpenObject | CloseObject | OpenArray | CloseArray | Comma | Colon;
      primitive = Number | String | Literal;
      JSON = ws* ( primitive? ( ws* delimiter ws* primitive? )* ) ws*;
      Root = JSON;
      ดูเหมือนว่าใน JSON จะเลือก delimiter ได้ตัวเดียว แล้วที่เหลือเลือกเป็น 0 ตัวได้ทั้งหมด
      ปกติผมเริ่มจากดู RFC ก่อน
      https://datatracker.ietf.org/doc/html/rfc4627#autoid-3
      ผมก็ไม่แน่ใจด้วยว่า Ragel สามารถ implement JSON ได้หรือไม่
      เท่าที่รู้ Ragel จัดการได้เฉพาะ regular language ส่วน JSON เป็น context-free language
    • สาเหตุของ Cloudbleed คือบั๊กของ C/Ragel และนั่นก็เป็นเหตุผลที่ Cloudflare เปลี่ยนไปใช้ Rust ด้วย
      https://en.wikipedia.org/wiki/Cloudbleed

  • เกี่ยวกับเรื่องนี้ ผมชอบทอล์กของ Rob Pike เรื่อง lexical scanning ใน Go
    เป็นแนวทางที่ให้ความรู้และสง่างาม
    https://www.youtube.com/watch?v=HxaD_trXwRE

    • ทอล์กนั้นยอดเยี่ยม แต่ผมจำได้ว่าเคยเห็นการถกเถียงในภายหลังว่า ที่จริง Go ไม่ได้ใช้เทคนิคนั้น
      เหตุผลน่าจะเป็นเพราะ overhead ของการ scheduling goroutine หรือรูปแบบการจัดสรรหน่วยความจำที่ไม่มีประสิทธิภาพ
      การถกเถียงที่ดีที่สุดเท่าที่พบคือ [1]
      อีกทอล์กที่ยอดเยี่ยมเกี่ยวกับการสร้าง lexer และ parser ที่มีประสิทธิภาพ คือ “Practical Data Oriented Design” ของ Andrew Kelley [2]
      โดยสรุปคือ อธิบายกลยุทธ์หลายอย่างในการลดการใช้หน่วยความจำของโปรแกรม และทำให้เป็นมิตรต่อแคชเพื่อเพิ่ม throughput
      1: https://news.ycombinator.com/item?id=31649617
      2: https://www.youtube.com/watch?v=IroPQ150F6c
    • ทอล์กนั้นดูจะเกี่ยวกับวิธีแสดง concurrency ในปัญหาที่ทำให้นึกถึง concurrency ได้อย่างเป็นธรรมชาติมากกว่าเรื่อง lexing เอง

  • สำหรับผม มีประสบการณ์หนึ่งที่น่าประหลาดใจ
    ผมสามารถนำ parser combinator library ที่ใช้กับ parser ของคอมไพเลอร์ระดับสูงไปใช้แบบเดิมในสภาพแวดล้อม no-std, คอมไพล์สำหรับไมโครคอนโทรลเลอร์ แล้ว deploy เป็น parser โปรโตคอลประสิทธิภาพสูงใน embedded environment ได้
    ใช้ไลบรารีเดียวกันแบบเดิมเลย
    ความต่างก็แค่ลดการใช้ String และใช้ &'static str มากขึ้นเท่านั้น
    ดังนั้นการลองเล่นกับคอมไพเลอร์จึงต่อยอดไปเป็นความสามารถในการสร้าง parser โปรโตคอลฝังตัวได้ค่อนข้างดี

  • สิ่งที่ยากตอนเขียน AST parser ทั้งหมดด้วย Rust คือการแสดงลำดับชั้นของชนิด AST แบบ concrete รวมถึงการ upcast และ downcast
    ก็หาวิธีได้อยู่ แต่ต้องใช้การเล่นชนิดแปลก ๆ อย่าง PhantomData กับ macro
    ตรงนี้ก็น่าจะต้องใช้ macro ค่อนข้างเกินพอดีเหมือนกัน
    อยากรู้ว่างานก่อนหน้าที่เกี่ยวข้องมีหน้าตาเป็นอย่างไร

    • ชนิดข้อมูลเชิงพีชคณิตและ syntax การ matching ของ Rust น่าจะดี
      จนกว่าจะไปถึง upcast/downcast นั่นแหละ
      ผมยังมีประสบการณ์กับ Rust ไม่พอ เลยไม่รู้ว่ามีวิธีจัดการที่ดีหรือไม่
      dynamic trait อาจเป็นไปได้
    • ถ้าเป็นโอเพนซอร์ส ก็อยากรู้ว่ามี repository สาธารณะไหม

  • macro code แบบนี้ debug กันอย่างไร หรือคนที่เพิ่งเข้ามาใน codebase จะเข้าใจได้อย่างไร
    ต่อให้ดูจุดที่ใช้ macro node! และ definition ของ macro ก็ดูเหมือนจะยากที่จะรู้ว่า code จริง ๆ ที่ถูก generate ออกมาคืออะไร
    สงสัยว่าควรรันตัวอย่างแล้วดูว่า type hint อะไรออกมา, hover ใน IDE แล้วดูเวอร์ชันที่ expand แล้วได้ไหม, หรือถ้าจะให้แน่ใจต้องอ้างอิงโค้ดที่ compile แล้ว
    เพราะทำงานแต่กับ JS/TS และไม่ได้แตะ macro เลย เลยสงสัย workflow แบบนี้

    • รัน $ cargo expand แล้วจะดูโค้ดผลลัพธ์ได้
      จริง ๆ Rust ค่อนข้างใกล้เคียงกับการเป็นหลายภาษา โดย “vanilla” Rust, declarative macro และ procedural macro ต่างก็มีความสามารถและ dialect ที่ต่างกันเล็กน้อย
      เมื่อเวลาผ่านไปก็จะคุ้นเคยกับการจัดการแต่ละแบบ
      unit test ก็เป็นพื้นที่ทดลองที่ดีในการทำความเข้าใจผลกระทบของการแก้ macro
    • rust-analyzer ซึ่งเป็น Rust LSP ที่ใช้ใน VSCode และอื่น ๆ สามารถ expand declarative macro และ procedural macro แบบ recursive ได้
      ไม่ได้แย่มาก แต่ใน codebase ยิ่งมี procedural macro น้อยเท่าไรก็ยิ่งดี
      declarative macro จะเข้าใจง่ายกว่าเล็กน้อย และบำรุงรักษากับทดสอบได้ง่ายกว่ามาก
      กับ code generation ที่ทึบในภาษาอื่น ๆ ก็รู้สึกคล้ายกัน

  • การ parse ไวยากรณ์ sqlite ก็ขอให้โชคดี
    เมื่อไม่กี่ปีก่อน ผมต้องเขียน parser สำหรับ subset ที่ค่อนข้างเล็กของ sqlite ในงาน
    ผมชอบ sqlite มาก และมันเป็นแหล่งแรงบันดาลใจเสมอ
    railroad diagram มีประโยชน์มหาศาล
    https://www.sqlite.org/syntaxdiagrams.html
    ผมคิดว่า lemon parser generator ยังไม่ได้รับการยอมรับเท่าที่ควร
    https://sqlite.org/src/doc/trunk/doc/lemon.html
    ในแง่การเลือกภาษา ภาษาอะไรก็ได้ที่มีชนิดข้อมูลเชิงพีชคณิตก็เหมาะดี
    แม้แต่ TypeScript ก็อาจยอดเยี่ยมสำหรับงานนี้ได้
    เมื่อก่อนผมเคยเขียนบทความเกริ่นนำเล็ก ๆ เกี่ยวกับการเขียน parser ด้วยมือใน Rust ด้วย
    https://www.nhatcher.com/post/a-rustic-invitation-to-parsing...