อยากสร้างคอมไพเลอร์หรือ? แค่อ่านบทความสองชิ้นนี้ก็พอ (2008)

 (prog21.dadgum.com)
16 คะแนน โดย GN⁺ 14 일 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีการชี้ปัญหาว่า ตำราเกี่ยวกับคอมไพเลอร์ ส่วนใหญ่เน้นทฤษฎีและมีเนื้อหามหาศาล ทำให้ผู้เริ่มต้นลงมือสร้างคอมไพเลอร์ที่ใช้งานได้จริงได้ยาก
  • ในฐานะแหล่งข้อมูลเชิงปฏิบัติเพื่อก้าวข้ามปัญหานี้ มีการแนะนำซีรีส์ Jack Crenshaw's “Let’s Build a Compiler!” ซึ่งว่าด้วย คอมไพเลอร์ Pascal แบบ single-pass ที่กระชับ
  • บทเรียนชุดนี้สนับสนุนการเรียนรู้เชิงทดลองผ่าน การผสานการแยกวิเคราะห์ไวยากรณ์กับการสร้างโค้ด, การทำ optimization ขั้นต่ำ, และ เวอร์ชัน C·Forth
  • เอกสารชิ้นที่สองคือบทความ “A Nanopass Framework for Compiler Education” ซึ่งนำเสนอ สถาปัตยกรรมคอมไพเลอร์แบบโมดูลาร์ ที่ประกอบด้วย การแปลงอย่างง่ายจำนวนมาก (pass)
  • หลังจากสั่งสมประสบการณ์จากการลงมือทำจริงผ่านเอกสารทั้งสองแล้ว หากต้องการก็สามารถต่อยอดการเรียนเชิงลึกด้วย ตำราแบบดั้งเดิม (Dragon Book) ได้

ความเป็นจริงของการเรียนคอมไพเลอร์และบทความสำคัญสองชิ้น

  • มีข้อวิจารณ์ว่า หนังสือคอมไพเลอร์ ที่มีอยู่เดิมมีขนาดใหญ่และเข้าใจยากเกินไป ทำให้ผู้เริ่มต้นเขียนคอมไพเลอร์ที่ทำงานได้จริงได้ยาก
    • หนังสือส่วนใหญ่ว่าด้วยหัวข้อจำนวนมาก เช่น การแปลง regular expression, ทฤษฎีไวยากรณ์ เป็นต้น แต่ไม่ได้ให้จุดเริ่มต้นเชิงปฏิบัติที่ชัดเจน
    • ด้วยเหตุนี้จึงเกิด ความเข้าใจผิดและภาพลวง ว่า “คอมไพเลอร์เป็นเรื่องยาก”
  • ในฐานะเอกสารตัวอย่างที่ช่วยทำลายภาพจำนี้ มีการแนะนำซีรีส์ Jack Crenshaw's “Let’s Build a Compiler!”
    • บทเรียนชุดนี้ซึ่งเริ่มต้นในปี 1988 ว่าด้วย คอมไพเลอร์แบบ single-pass ระดับ Turbo Pascal
    • มีโครงสร้างที่ผสานการแยกวิเคราะห์ไวยากรณ์เข้ากับการสร้างโค้ด และทำ optimization เพียงขั้นต่ำ
    • เดิมเขียนด้วย Pascal และภายหลังก็มีทั้ง เวอร์ชัน C และ ฉบับแปล Forth
    • เวอร์ชัน Forth เอื้อต่อการทดลองและการทำความเข้าใจได้ง่าย เพราะคุณสมบัติของภาษาแบบโต้ตอบได้
  • ข้อจำกัดของซีรีส์ Crenshaw คือไม่มี ตัวแทนภายในของโปรแกรม (abstract syntax tree, AST)
    • ใน Pascal การจัดการต้นไม้มีความซับซ้อนจึงถูกละไว้ แต่ในภาษาระดับสูงอย่าง Python, Ruby, Erlang, Haskell, Lisp สามารถทำได้ง่าย
    • ภาษาเหล่านี้ถูกออกแบบมาตั้งแต่ต้นเพื่อ จัดการข้อมูลโครงสร้างแบบต้นไม้
  • เอกสารอีกชิ้นที่แนะนำเป็นลำดับถัดมาคือบทความของ Sarkar, Waddell, Dybvig “A Nanopass Framework for Compiler Education”
    • แนวคิดหลักคือ “คอมไพเลอร์คือกระบวนการต่อเนื่องที่ค่อย ๆ แปลงตัวแทนภายในของโปรแกรมไปทีละขั้น”
    • เสนอโครงสร้างที่ประกอบด้วย การแปลงอย่างง่ายหลายสิบถึงหลายร้อยขั้น (pass)
    • แต่ละการแปลงถูกทำให้เรียบง่ายที่สุดเท่าที่จะเป็นไปได้ และ หลีกเลี่ยงการผูกติดกันระหว่างการแปลง
    • เฟรมเวิร์กระบุอินพุตและเอาต์พุตของแต่ละ pass อย่างชัดเจน
    • ภาษาในการใช้งานคือ Scheme และอาศัย dynamic typing ในการตรวจสอบระหว่างรันไทม์
  • หลังจากได้ลองเขียนคอมไพเลอร์จริงผ่านเอกสารทั้งสองแล้ว หากต้องการก็สามารถศึกษาต่อเชิงลึกด้วยตำราแบบดั้งเดิมอย่าง Dragon Book ได้
    • อย่างไรก็ตาม เพียงเอกสารสองชิ้นนี้ก็เพียงพอที่จะทำให้ได้ ประสบการณ์เชิงปฏิบัติในการสร้างคอมไพเลอร์

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

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

 
GN⁺ 14 일 전
ความคิดเห็นจาก Hacker News

  • 『The Art of Computer Programming』 ของ Donald Knuth ยังเขียนไม่จบ และตอนนี้ก็ดูมีแนวโน้มสูงว่าจะไม่ครอบคลุมเรื่อง คอมไพเลอร์ แล้ว
    ฉันไม่เห็นด้วยกับข้อสรุปของผู้เขียน บทที่ 2 ของ 『Dragon Book』 (โดย Aho และคณะ) อ่านแยกเดี่ยวก็ได้ และสมบูรณ์พอในฐานะ หนังสือเริ่มต้นเรื่องคอมไพเลอร์
    หนังสือเริ่มต้นที่ยอดเยี่ยมอีกเล่มคือ 『Compilers』 ของ Niklaus Wirth ซึ่งยาวไม่ถึง 100 หน้า แต่มีทั้งซอร์สโค้ดของคอมไพเลอร์ที่สมบูรณ์และคำอธิบายที่ชัดเจน
    ฉันเรียนรู้จากสองเล่มนี้มากพอที่จะลงมือสร้างคอมไพเลอร์เองได้ตั้งแต่สมัยมัธยมปลาย

    • 『Dragon Book』 ยอดเยี่ยมก็จริง แต่ไม่เหมาะสำหรับมือใหม่ ฉันเองก็เกือบเลิกเรื่องคอมไพเลอร์เพราะหนังสือเล่มนี้
      ฉันคิดว่าหนังสือที่พาเราลงมือทำและเดินตามกระบวนการสร้างคอมไพเลอร์จริงจะดีกว่ามาก
      แหล่งอ้างอิงถูกรวบรวมไว้ในลิงก์นี้
    • 『Dragon Book』 เน้น parsing เป็นหลัก ดังนั้นถ้าสนใจ backend หรือ optimization ก็ไม่ค่อยแนะนำ
      ฉบับพิมพ์ครั้งที่ 2 เพิ่ม data flow analysis เข้ามา แต่ SSA (Static Single Assignment) ซึ่งเป็นแกนหลักของคอมไพเลอร์สมัยใหม่อย่าง GCC และ LLVM ถูกกล่าวถึงเพียงหน้าเดียว
      ถ้าจะสร้าง backend สมัยใหม่ ก็ต้องไปศึกษา SSA เพิ่มต่างหาก
    • ดู 『Compilers』 ของ Niklaus Wirth ได้ที่นี่
    • ตามเว็บไซต์ของ Knuth ยังมีแผนจะพูดถึงเทคนิคคอมไพเลอร์ใน Volume 7 อยู่
      ดูหน้า TAOCP อย่างเป็นทางการ
    • เพิ่งรู้ชื่อกลางของ Knuth เหมือนกัน แต่ในบทความคงไม่จำเป็นต้องใส่ก็ได้

  • งานวิจัย An Incremental Approach to Compiler Construction ของ Abdulaziz Ghuloum
    ช่วยทลายภาพจำว่า “คอมไพเลอร์เป็นของวิเศษลึกลับ” และแสดงให้เห็นว่า เราสร้างคอมไพเลอร์ได้ง่ายพอๆ กับอินเทอร์พรีเตอร์
    โดยอธิบายอย่างละเอียดถึงการค่อยๆ สร้างคอมไพเลอร์ที่รองรับ Scheme ได้ส่วนใหญ่ และสร้างแอสเซมบลีสำหรับ Intel x86 ออกมา

  • ช่วงหลังเทคโนโลยีคอมไพเลอร์ก้าวหน้าไปมาก ทั้ง meta-compiler, adaptive compilation, และ JIT compiler
    กลุ่มวิจัย VPRI ของ Alan Kay ก็ทำงานกับปัญหาด้านความซับซ้อนนี้
    ดูเพิ่มได้ที่ งานวิจัย Ometa, วิดีโอ Adaptive Compilation, บรรยายของ Alan Kay

  • ฉันเคยได้คำแนะนำดีๆ เรื่องการอ่านหนังสือว่า หนังสือมัน เข้าถึงแบบสุ่มได้เหมือน RAM (random access)
    ถ้าเลือกอ่านเฉพาะส่วนที่ต้องใช้ หนังสือเล่มหนาก็จะไม่รู้สึกหนักเกินไป
    แต่ถ้าเรายังไม่รู้ด้วยซ้ำว่าไม่รู้อะไร วิธีนี้ก็ใช้ไม่ได้ นั่นจึงเป็นเหตุผลว่าทำไมหนังสือเริ่มต้นแบบเบาๆ ถึงสำคัญมาก

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

  • ทุกวันนี้หลายคนแนะนำ 『Crafting Interpreters』
    แต่ลิงก์ไปงานวิจัย Nanopass เสียแล้ว

    • ต่อให้เรียกว่า “หนังสือคอมไพเลอร์” ขอบเขตที่แต่ละเล่มครอบคลุมก็ต่างกันมาก และหลายครั้งก็ไม่ตรงกับส่วนที่ฉันอยากได้
      เพราะแบบนั้นฉันเลยทำชีตสรุปของสาระสำคัญใน 『Crafting Interpreters』 ไว้
      หนังสือเล่มนี้ไม่ใช่แค่คู่มือ แต่เป็น หนังสือเรียนรู้จากประสบการณ์ ที่สะท้อนความสนุกของผู้เขียนเอาไว้ เช่น visitor pattern
    • 『Crafting Interpreters』 ยอดเยี่ยมมาก แต่ถ้ามีเล่มคู่ที่ครอบคลุม type system, optimization, และ linking ด้วยก็คงสมบูรณ์แบบ
    • เป็นหนังสือที่เหมาะกับการเรียนด้วยตัวเองมากจริงๆ
    • ฉันอ่านจบตอนสมัยมหาวิทยาลัย ระหว่างรอเข้าเรียน Nanopass ยังไม่เคยลอง แต่ตั้งใจจะลองจากลิงก์อื่นดู
    • งานวิจัย Nanopass ถูกเก็บรักษาไว้ในรีโพซิทอรี GitHub นี้

  • ช่วงนี้ฉันกำลังทำ toy compiler เล่นๆ
    แทนที่จะใช้ทฤษฎี parsing ซับซ้อนหรือ DSL ฉันใช้ Megaparsec parser combinator
    ทำให้ตรรกะการ parse ชัดเจน ใช้ซ้ำง่าย และไม่ต้องยุ่งกับภาระของการแยก lexer/parser แบบดั้งเดิม

    • ฉันมองว่า recursive descent parser ใช้งานได้จริงกว่า LL/LR parser generator
      มันมีบั๊กน้อยกว่า วินิจฉัยข้อผิดพลาดได้ดีกว่า และภาษาส่วนใหญ่ เช่น C# กับ Rust ก็ใช้แนวทางนี้
      tree-sitter ก็ยอดเยี่ยม แต่มี dependency เยอะ ขณะที่ recursive descent ทำให้ได้ implementation ที่กระชับและไม่มี dependency
    • ถึงอย่างนั้น ฉันก็ยังคิดว่าควรแยก lexer/parser ไว้เหมือนเดิม
      ข้อดีของแนวทาง parser combinator คือเราสามารถจัดการทั้ง lexer และ parser ด้วย parser type แบบเดียวกันได้
      ทำให้จัดการเรื่องช่องว่างและการ tokenization ได้อย่างเรียบร้อย

  • ลิงก์งานวิจัย Nanopass ที่เคยเสีย สามารถดูได้ที่นี่

  • สิ่งที่สอนฉันเรื่องคอมไพเลอร์จริงๆ คือบทความ Tiny Pascal compiler ในนิตยสาร BYTE ปี 1978
    เรื่อง optimization ฉันเรียนจากคอร์สภาคฤดูร้อนของ Ullman และ Hennessy ที่ Stanford
    ส่วน code generator ก็เป็นวิธีที่ฉันคิดขึ้นเองแบบต้นฉบับ
    ฉันมี 『Dragon Book』 อยู่ แต่จริงๆ แล้วไม่เคยอ่านมันเลย

    • ดูนิตยสาร BYTE ฉบับดังกล่าวได้ที่ archive.org

  • แก่นสำคัญของแนวทาง Nanopass ไม่ได้อยู่ที่ จำนวน pass แต่คือการกำหนด ภาษา input/output ที่ชัดเจน สำหรับแต่ละ pass
    วิธีคิดแบบมีโครงสร้างนี้ช่วยจับบั๊กได้มากก่อนรันจริง
    บทสอนของ Crenshaw ก็ยอดเยี่ยม แต่การ จัดการความไม่แปรเปลี่ยนของภาษา แบบนี้ต่างหากที่ทำให้คอมไพเลอร์ขยายต่อได้จริง

  • สมัยอยู่ UC Irvine ฉันจำได้ว่าเคย implement optimizing compiler ในวิชา CS241 ของศาสตราจารย์ Michael Franz ซึ่งเป็นลูกศิษย์ของ Niklaus Wirth
    โจทย์คือสร้างไบต์โค้ดสำหรับเครื่องเสมือนชื่อ DLX
    ดูข้อมูลที่เกี่ยวข้องได้จากคำอธิบายสถาปัตยกรรม DLX และ
    ภาพอ้างอิงอัลกอริทึม register allocation