ย้อนดู Let’s Build a Compiler อีกครั้ง

 (eli.thegreenplace.net)
1 คะแนน โดย GN⁺ 2025-12-12 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • โปรเจ็กต์ที่นำ บทเรียน ‘Let’s Build a Compiler’ ของ Jack Crenshaw ซึ่งเผยแพร่ในช่วงปี 1988~1995 มาสร้างใหม่ด้วย Python และ WebAssembly
  • ต้นฉบับใช้ Pascal และแอสเซมบลี Motorola 68000 แต่ในการทำครั้งนี้ได้แปลงให้เป็นโค้ดที่รันได้ในสภาพแวดล้อมสมัยใหม่
  • แกนสำคัญของบทเรียนคือการลงมือสร้าง recursive-descent parser ด้วยตนเอง และใช้แนวทางที่สร้างโค้ดแอสเซมบลีจริงตั้งแต่ช่วงเริ่มต้น
  • วิธีของ Crenshaw ใช้ syntax-directed translation แต่เริ่มเห็นข้อจำกัดเมื่อเข้าสู่ขั้นตอนจัดการชนิดข้อมูล
  • การสร้างใหม่ครั้งนี้มีความสำคัญตรงที่เป็นการ ฟื้นฟูบทเรียนคลาสสิกให้อยู่ในรูปแบบที่นักพัฒนายุคใหม่สามารถรันและทดลองได้ด้วยตนเอง

ที่มาของบทเรียนคลาสสิก

  • ‘Let’s Build a Compiler’ ของ Jack Crenshaw เป็นหนังสือแนะนำการสร้างคอมไพเลอร์ที่เผยแพร่ระหว่างปี 1988~1995 และยังคงถูกอ้างถึงอยู่บ่อยครั้งจนถึงปัจจุบัน
    • ต้นฉบับเขียนด้วย Pascal และสร้างผลลัพธ์เป็น โค้ดแอสเซมบลี Motorola 68000
    • แม้ผ่านไป 35 ปีแล้ว ในปี 2025 ก็ยัง ถูกพูดถึงอย่างต่อเนื่องใน Hacker News และที่อื่น ๆ
  • ผู้เขียนบทความได้พบกับบทเรียนนี้ครั้งแรกในปี 2003 และประทับใจมาก ก่อนจะนำกลับมาทำใหม่ด้วย Python และ WebAssembly ในปี 2025

การสร้างใหม่ด้วย Python และ WebAssembly

  • ไม่ได้หยุดแค่อ่าน แต่ยัง แปลคอมไพเลอร์ในบทเรียนให้เป็น Python และทำให้สามารถสร้างผลลัพธ์เป็น WebAssembly (WASM) ได้
  • ผลลัพธ์ถูกเผยแพร่ไว้ใน GitHub repository (eliben/letsbuildacompiler)
    • ไฟล์ TUTORIAL.md อธิบายว่าแต่ละส่วนของต้นฉบับถูกแมปมาเป็นโค้ด Python อย่างไร
    • ผู้ใช้สามารถอ่านบทเรียนต้นฉบับไปพร้อมกับทดลอง โค้ดที่รันได้จริง ด้วยตนเอง

ตัวอย่างภาษา KISS และผลลัพธ์ WASM

  • มีการยกตัวอย่างโปรแกรมใน ภาษา KISS ที่ Crenshaw ออกแบบไว้ แล้วคอมไพล์ด้วยคอมไพเลอร์เวอร์ชัน Python
    • ตัวอย่างมีทั้ง procedure, ลูป while, และการ ส่งค่าพารามิเตอร์แบบ by-value และ by-reference
  • WASM text ที่ได้มีตรรกะสำหรับจัดการ พารามิเตอร์อ้างอิง (by-reference parameter) รวมอยู่ด้วย และแทบไม่มีการปรับแต่งประสิทธิภาพ
  • ส่วนที่ตัวแปรโกลบอล X ถูกคืนค่าโดยนัยจากฟังก์ชัน main เป็น กลไกเพื่อความสะดวกในการทดสอบ
  • โค้ด WASM ที่สร้างขึ้นถูกนำไปรันจริงเพื่อใช้ใน การทดสอบยืนยันว่าผลลัพธ์ตรงตามที่คาดไว้

จุดเด่นของบทเรียน

  • บทเรียนของ Crenshaw ค่อย ๆ สร้าง recursive-descent parser แบบเป็นขั้นตอน และเน้น การสร้างโค้ดที่ทำงานได้จริง มากกว่าทฤษฎีที่ซับซ้อน
    • ในยุคนั้น lex และ yacc ถูกมองว่าเป็นมาตรฐาน แต่ ความเรียบง่ายและชัดเจนของ parser ที่เขียนเอง สร้างอิทธิพลอย่างมาก
    • หลังจากนั้นอีก 20 ปี ผู้เขียนก็ยังคงชอบใช้ manual recursive-descent parser
  • นอกจากนี้ ในยุคที่บทเรียนส่วนใหญ่เน้นการวิเคราะห์ไวยากรณ์เป็นหลัก Crenshaw กลับพูดถึง การสร้างโค้ดแอสเซมบลีตั้งแต่ระยะเริ่มต้น

ข้อจำกัดและโอกาสในการปรับปรุง

  • บทเรียนนี้ใช้แนวทาง syntax-directed translation ที่สร้างโค้ดทันทีระหว่างการ parse
    • วิธีนี้มีประโยชน์ต่อการเรียนรู้ แต่ก็มี ข้อจำกัดตรงที่ไม่รู้ข้อมูลชนิดล่วงหน้า ทำให้ปรับแต่งประสิทธิภาพได้ยาก
  • โดยเฉพาะหลังส่วนที่ 14 ซึ่งเริ่มมีระบบชนิดข้อมูล จึงเห็นชัดว่าต้องการ แนวทางเชิงโครงสร้างที่ใช้ IR หรือ AST
  • ไม่มีการระบุชัดเจนว่าทำไม Crenshaw จึงหยุดบทเรียนไว้หลังส่วนที่ 14 แต่ก็มีการกล่าวถึงว่า อาจเกี่ยวข้องกับข้อจำกัดนี้
  • ผู้เขียนมองว่า การใช้ส่วนที่ 14 เป็นจุดเปลี่ยน แล้วสร้าง AST ก่อนทำ type checking และ code generation น่าจะเหมาะสมกว่า

บทสรุป

  • บทเรียนต้นฉบับยังคงมี ความอ่านง่ายและใช้งานได้จริงยอดเยี่ยมในฐานะหนังสือแนะนำการสร้างคอมไพเลอร์
  • เวอร์ชัน Python·WASM ครั้งนี้เป็น การเติมเต็มให้เหมาะกับนักพัฒนาสมัยใหม่ที่ต้องการเรียนรู้โดยไม่ต้องพึ่งเทคโนโลยีล้าสมัย
  • ทุกคนสามารถทดลองได้ผ่าน GitHub repository และถือเป็น การตีความใหม่แบบร่วมสมัยที่เปิดโอกาสให้สัมผัสโครงสร้างของคอมไพเลอร์ได้โดยตรง

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

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

 
GN⁺ 2025-12-12
ความเห็นจาก Hacker News

  • ชอบที่บทสอนนี้ไม่จมอยู่กับรายละเอียดของฟรอนต์เอนด์ แต่เริ่มจากการสร้าง โค้ดแอสเซมบลีที่ใช้งานได้จริง ตั้งแต่ต้นเลย
    แนวทางแบบ Ghuloum ที่ค่อย ๆ สร้างระบบทั้งหมดขึ้นมาจากส่วนเล็กมากของภาษาแล้วขยายเพิ่มทีละนิดนั้นน่าสนใจเป็นพิเศษ
    หนังสือดี ๆ ที่เพิ่งเจอไม่นานนี้คือ ลิงก์นี้ ซึ่งแม้ C และ x86 จะไม่ใช่เป้าหมายที่เหมาะที่สุดสำหรับผู้เริ่มต้น แต่ก็เป็นแหล่งความรู้ชั้นยอดสำหรับการสร้างคอมไพเลอร์ตัวแรก
    อ้างอิงเพิ่มเติม วิทยานิพนธ์ของ Ghuloum อยู่ที่นี่

    • นี่เป็นกรณีที่พบไม่บ่อย แต่ผมคิดว่านี่คือตัวอย่างที่ แนวทางแบบวิชาการ ไม่สอดคล้องกับการใช้งานจริง
      ในอดีตการพาร์สเป็นส่วนที่สำคัญที่สุด หลักสูตรจึงถูกออกแบบมาแบบนั้น แต่ทุกวันนี้สิ่งที่สำคัญกว่าคือจะทำฟีเจอร์ของภาษาให้ทำงานอย่างไร
      ต่อให้จะสร้างคอมไพเลอร์เอง เดี๋ยวนี้ก็เป็นยุคที่พูดว่า “Claude, ช่วยสร้าง recursive descent parser ด้วยไวยากรณ์นี้ให้หน่อย” แล้วแทบจะได้ผลลัพธ์ในครั้งเดียว
    • ทำให้รู้สึกถึงความต่างระหว่างนักวิจัยสายวิชาการกับนักพัฒนาสายปฏิบัติ
      ฝั่งวิชาการมักเข้าหาแบบ layer ส่วนฝั่งปฏิบัติมักเข้าหาแบบ pipe
      วิธีแบบ layer ให้โค้ดที่ build ได้ แต่รันยาก ส่วนวิธีแบบ pipe รันง่ายแต่โครงสร้างไม่ค่อยแข็งแรง
      สุดท้ายแล้วหัวใจสำคัญคือการแบ่งงานพัฒนาออกเป็นหน่วยย่อยที่สุดที่ยังรันได้

  • คิดว่าบทความนี้จับประเด็นสำคัญได้ดีมาก
    ผมสนใจคอมไพเลอร์ตั้งแต่ก่อนเข้ามหาวิทยาลัย และเอกสารชิ้นนี้คือบทนำที่เข้าถึงง่ายที่สุดเท่าที่เคยเจอ
    ตอนอายุ 17 ผมลองทำ recursive descent parser เอง และได้ตระหนักว่าปัญหาที่ดูซับซ้อนก็กลายเป็นเรื่องง่ายได้ถ้าแยกมันออกเป็น primitive พื้นฐานที่เหมาะสม

    • “การแยกปัญหาออกเป็น primitive ที่ถูกต้อง” คือแก่นแท้ที่แท้จริงของการเขียนโปรแกรม
      มีข้อมูลเกี่ยวกับอัลกอริทึมอยู่มากมาย แต่ข้อมูลที่พูดถึงวิธีเข้าหาปัญหาด้วย primitive กลับมีน้อย
    • recursive descent ไม่ได้เป็นแค่วิธีสร้าง parser เท่านั้น แต่ยังเป็น บทเรียนด้านการออกแบบโปรแกรม ด้วย
      เมื่อก่อน table-driven parser อย่าง yacc เคยเป็นกระแสหลัก แต่ทุกวันนี้ recursive descent ใช้งานได้จริงและยืดหยุ่นกว่า
      ด้วยพลังของการสร้างโค้ดโดย LLM วิธีนี้จึงยิ่งเข้าถึงง่ายขึ้น
      สำหรับ toy compiler เพื่อการเรียนรู้ การข้าม AST, IR และการ optimize แล้วไปสร้างโค้ดโดยตรงเลยก็ยังมีประโยชน์มากพอ
      เมื่อก่อนตอนทำเครื่องมือทดสอบในบริษัทที่รองรับ subset ของ C เราให้ parser คืนค่าเป็น โครงสร้างข้อมูลที่รันได้ แทนที่จะสร้างโค้ดออกมา
      ตัวอย่างเช่นคลาส ForLoopStatement จะมี testExpression อยู่ภายใน และเรียกมันโดยตรงจากเมธอด Execute()
    • งานของ Niklaus Wirth ปี 1971 ชื่อ Program Development by Stepwise Refinement เป็นงานคลาสสิกยุคแรกที่วางรากฐานแนวคิดแบบนี้
      เป็นบทความสำคัญที่ถูกกล่าวถึงใน The Mythical Man-Month ของ Fred Brooks ด้วย
    • ทุกวันนี้เวลาอยากทำ parsing ผมมักจะเลือกใช้ parser combinator
      มันเป็นแนวคิดที่เป็นธรรมชาติและสะอาดมากในเชิงโครงสร้าง

  • คำอธิบายที่ว่าบทสอนของ Jack Crenshaw ใช้วิธี syntax-directed translation นั้นน่าสนใจมาก
    ผมสงสัยว่านี่หมายถึงแค่ single-pass compiler หรือเป็นแนวคิดที่เฉพาะเจาะจงกว่านั้น
    ผมพอเข้าใจว่าในภาษาที่มี static type จะทำ optimization ตามชนิดข้อมูลได้ยาก แต่ก็อยากรู้ว่ามันจำกัดไปถึงระดับของการตรวจชนิดข้อมูลด้วยหรือเปล่า

    • ถ้าภาษาเป้าหมายใช้กฎ ต้องประกาศก่อนใช้งาน และไม่มี type inference ที่ซับซ้อน ก็ยังทำ optimization ตามชนิดข้อมูลหรือ constant folding ได้
      แต่ถ้าไม่มี IR ก็จะทำ optimization ขั้นสูงอย่าง LICM, CSE, GVN ไม่ได้
      โดยส่วนตัวผมชอบ การคอมไพล์แบบ 2 pass ระดับฟังก์ชัน — pass แรกสร้าง IR แล้วสร้างโค้ดทันทีหลังจากนั้นและทิ้งสถานะไป ซึ่งให้ผลลัพธ์ที่เร็วและมีประสิทธิภาพ
    • syntax-directed translation เป็นแนวคิดที่เฉพาะเจาะจงกว่านั้น คือหมายถึง อ่านซอร์สโค้ดไปพร้อมกับสร้างโค้ดทันที
      ต่อให้เป็น single-pass compiler ก็ยังอาจแยกขั้นตอนภายในออกจากกัน แล้วค่อยสร้างโค้ดตอนท้ายสุดเพียงอย่างเดียวก็ได้

  • บทสอนของ Crenshaw อาจยังไม่ถึงระดับใช้งานจริง แต่ถ้าขยายด้วยเทคนิค precedence climbing ก็จะมีประโยชน์มากขึ้นมาก
    บทความที่เกี่ยวข้องสรุปไว้ดีที่ ลิงก์นี้

  • ลองกลับไปดูเธรดเกี่ยวกับ “Let’s Build a Compiler” อีกครั้ง
    มี ประวัติการขึ้น HN หลายครั้ง ตั้งแต่ปี 2007 ถึง 2023
    โดยเฉพาะ บทสัมภาษณ์ Jack Crenshaw ที่แม้จะไม่มีคอมเมนต์ แต่ก็เป็นเรื่องอ่านที่น่าสนใจมาก

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

  • ขอแนะนำพร้อมโปรโมตโปรเจกต์ส่วนตัว: cwerg.org
    ใช้ Python และ recursive descent parsing พร้อมแยกฟรอนต์เอนด์กับแบ็กเอนด์ออกจากกันด้วย IR
    สร้าง ELF binary สำหรับ x86 และ ARM และตั้งเป้าให้ใช้งานจริงได้
    แต่ค่อนข้างซับซ้อนและไม่ใช่สไตล์บทสอน

  • มีความทรงจำดี ๆ กับการเรียนบทสอนของ Jack Crenshaw จากกลุ่มข่าว comp.compilers บน USENET ในอดีต
    อ้างอิงเพิ่มเติม กลุ่มนั้นยังคงเปิดใช้งานอยู่

  • ถ้าจะมองหาแนวทางคอมไพเลอร์สมัยใหม่ ขอแนะนำบทความบล็อกของ Cornell นี้

    • ต้องยกความดีความชอบให้ LLVM ที่ทำให้การสร้างคอมไพเลอร์ ง่ายอย่างน่าทึ่ง
      ทุกครั้งที่ใช้มันให้ความรู้สึกเหมือนแค่วางหินเพิ่มอีกไม่กี่ก้อนบนยอดพีระมิด
    • แต่ LLVM เป็น แนวทางอ้อม จึงมีข้อจำกัดอยู่
      ภาษาที่ใช้ LLVM เป็นแบ็กเอนด์ต่างก็มีปัญหาร่วมกันคือ คอมไพล์ช้า
      Zig มองเห็นเรื่องนี้และกำลังพัฒนาแบ็กเอนด์ของตัวเอง ส่วน Rust ก็ยังติดอยู่กับปัญหาการคอมไพล์ช้า
      ผมคิดว่า LLVM ทำให้คนเข้าใจผิดว่าความซับซ้อนคือหลักประกันของคุณภาพ และเป็นเทคโนโลยีที่ ลดทอนความเป็นอิสระของนักพัฒนา
      มันคล้ายกับเทคโนโลยียอดนิยมอื่นบางอย่างด้วย (ที่มีชื่อย่อคล้ายกัน)

  • ด้วยเหตุผลคล้ายกัน ผมก็เลยเขียนบทสอนชื่อ tiny-optimizing-compiler ขึ้นมา
    เป็นตัวอย่างแบบกระชับที่ครอบคลุมเฉพาะ ขั้นตอนกลางและแบ็กเอนด์ ของคอมไพเลอร์
    ลิงก์ GitHub

    • ถ้าลองทำสิ่งนี้ด้วย Lean ก็น่าจะสนุกดี

  • ตอนเด็ก ๆ ผมเคยพิมพ์บทสอนนี้ออกมาแล้วพกติดตัวไว้อ่าน
    การได้เห็นคอมไพเลอร์ถูกสร้างเสร็จในเวลาไม่นานนั้นยอดเยี่ยมมากจริง ๆ
    เอกสารอย่าง Beej’s Guide แบบนี้คือหนึ่งใน เอกสารที่มีคุณค่าที่สุดสำหรับการศึกษาด้าน CS แต่กลับยังไม่ได้รับการยกย่องอย่างที่ควรได้