Ingin membuat compiler? Cukup baca dua makalah ini (2008)

 (prog21.dadgum.com)
17 poin oleh GN⁺ 2026-04-16 | 1 komentar | Bagikan ke WhatsApp
  • Sebagian besar buku ajar compiler sangat teoretis dan sangat tebal, sehingga pemula sulit mengimplementasikan compiler yang benar-benar berjalan
  • Sebagai bahan praktis untuk mengatasinya, diperkenalkan seri Jack Crenshaw, “Let’s Build a Compiler!”, yang membahas compiler Pascal sederhana dengan struktur single-pass
  • Tutorial ini mendukung pembelajaran eksperimental melalui penggabungan parsing dan code generation, optimisasi minimal, serta versi C dan Forth
  • Bahan kedua, makalah “A Nanopass Framework for Compiler Education”, menyajikan struktur compiler modular yang terdiri dari banyak transformasi sederhana (pass)
  • Setelah membangun pengalaman implementasi nyata lewat dua bahan ini, barulah jika perlu dapat melanjutkan pendalaman dengan buku ajar tradisional (Dragon Book)

Realitas belajar compiler dan dua makalah kunci

  • Ada kritik bahwa buku compiler yang ada terlalu tebal dan sulit, sehingga pemula kesulitan menulis compiler yang benar-benar berfungsi
    • Kebanyakan buku membahas topik besar seperti transformasi regular expression, teori tata bahasa, dan lain-lain, tanpa memberi titik awal yang praktis
    • Akibatnya, terbentuk kesalahpahaman dan mitos bahwa “compiler itu sulit”
  • Sebagai bahan representatif yang mematahkan anggapan ini, diperkenalkan seri Jack Crenshaw, “Let’s Build a Compiler!”
    • Tutorial yang dimulai pada 1988 ini membahas compiler single-pass setingkat Turbo Pascal
    • Strukturnya menggabungkan parsing dan code generation, dan hanya melakukan optimisasi minimal
    • Awalnya ditulis dalam Pascal, dan kemudian juga ada versi C serta terjemahan Forth
    • Versi Forth memudahkan eksperimen dan pemahaman berkat sifat bahasanya yang interaktif
  • Keterbatasan seri Crenshaw adalah tidak adanya representasi internal program (abstract syntax tree, AST)
    • Di Pascal, manipulasi tree cukup rumit sehingga dihilangkan, tetapi dalam bahasa tingkat tinggi seperti Python, Ruby, Erlang, Haskell, Lisp hal ini bisa diimplementasikan dengan mudah
    • Bahasa-bahasa ini pada dasarnya dirancang untuk memanipulasi data berstruktur tree
    Iklan
  • Bahan kedua yang direkomendasikan adalah makalah Sarkar, Waddell, Dybvig “A Nanopass Framework for Compiler Education”
    • Gagasan intinya adalah bahwa “compiler merupakan serangkaian proses yang secara bertahap mentransformasikan representasi internal program”
    • Diusulkan struktur yang terdiri dari puluhan hingga ratusan transformasi sederhana (pass)
    • Setiap transformasi dijaga sesederhana mungkin, dan menghindari keterikatan antar-transformasi
    • Framework tersebut mendefinisikan input dan output tiap pass secara eksplisit
    • Bahasa implementasinya adalah Scheme, dan verifikasi dijalankan saat runtime berbasis tipe dinamis
  • Setelah menulis compiler nyata melalui dua bahan ini, bila perlu pembelajaran dapat dilanjutkan lebih dalam dengan buku ajar tradisional seperti Dragon Book
    • Namun, hanya dengan dua bahan ini pun sudah cukup untuk memperoleh pengalaman praktis membuat compiler

Bacaan terkait

1 komentar

 
GN⁺ 2026-04-16
Komentar Hacker News

  • 『The Art of Computer Programming』 karya Donald Knuth masih terus ditulis, dan sekarang kemungkinan besar tidak akan membahas topik compiler
    Saya tidak setuju dengan klaim penulis. Bab 2 dari 『Dragon Book』(oleh Aho dkk.) sudah cukup utuh jika dibaca sendiri sebagai pengantar compiler
    Pengantar lain yang sangat bagus adalah 『Compilers』 karya Niklaus Wirth, yang dalam kurang dari 100 halaman memuat source code compiler lengkap beserta penjelasan yang jelas
    Dari dua buku ini saya belajar cukup banyak hingga bisa membuat compiler sendiri saat masih SMA

    • 『Dragon Book』 memang bagus, tetapi tidak cocok sebagai buku pengantar. Saya sendiri hampir menyerah mempelajari compiler gara-gara buku ini
      Menurut saya, buku yang berfokus pada praktik dan mengikuti proses pembuatan compiler nyata jauh lebih baik
      Referensinya dirangkum di tautan ini
    • 『Dragon Book』 berfokus pada parsing, jadi tidak saya rekomendasikan jika Anda tertarik pada backend atau optimisasi
      Edisi ke-2 memang menambahkan analisis aliran data, tetapi format SSA (Static Single Assignment), yang merupakan inti compiler modern (GCC, LLVM, dll.), hanya dibahas satu halaman
      Untuk membuat backend modern, Anda tetap perlu mempelajari teori SSA secara terpisah
    • 『Compilers』 karya Niklaus Wirth dapat dilihat di sini
    • Menurut situs Knuth, masih ada rencana membahas teknik compiler di Volume 7
      Lihat halaman resmi TAOCP
    • Saya baru tahu nama tengah Knuth, tetapi rasanya tidak perlu dimasukkan ke artikel

  • Makalah Abdulaziz Ghuloum An Incremental Approach to Compiler Construction
    mematahkan anggapan bahwa “compiler adalah sesuatu yang ajaib”, dan menunjukkan bahwa compiler bisa dibuat semudah interpreter
    Makalah ini menjelaskan secara rinci proses membangun compiler secara bertahap yang mendukung sebagian besar bahasa Scheme dan menghasilkan assembly untuk Intel x86

    • 『Writing a C Compiler』 karya Nora Sandler, yang terinspirasi oleh makalah ini, juga merupakan buku yang sangat bagus
    • Ada juga versi dengan test yang mengimplementasikan pendekatan Aziz oleh Nada Amin

  • Belakangan ini teknologi compiler berkembang pesat lewat meta-compiler, adaptive compilation, JIT compiler, dan sebagainya
    Grup riset VPRI milik Alan Kay menangani masalah kompleksitas
    Materi terkait: makalah Ometa, video Adaptive Compilation, kuliah Alan Kay

  • Saya pernah mendengar nasihat bagus soal membaca buku — buku itu bisa diakses secara acak seperti RAM (random access)
    Jika hanya membaca bagian yang diperlukan, buku tebal pun terasa tidak terlalu membebani
    Namun, cara ini tidak berlaku saat kita bahkan tidak tahu apa yang belum kita ketahui. Karena itu buku pengantar yang ringan sangat penting

    • Kebanyakan buku punya terlalu banyak detail yang tidak perlu sehingga akhirnya saya lewati. Sebaliknya, buku teknis sering terlalu sulit sampai memahami satu bagian saja butuh berjam-jam
    • Saya merasa sulit mendapatkan makna jika tidak membaca buku sampai tuntas. Sekarang banyak materi yang berperan sebagai buku referensi bagus sudah berpindah ke internet
    • Sebagian besar buku teknis saya gunakan sebagai referensi untuk pertanyaan tertentu

  • Sekarang 『Crafting Interpreters』 sering direkomendasikan
    Tautan ke makalah Nanopass sudah mati

    • Bahkan untuk “buku compiler” pun cakupan bahasannya sangat beragam, jadi sering kali tidak sesuai dengan bagian yang sebenarnya saya inginkan
      Karena itu saya membuat cheat sheet yang merangkum inti 『Crafting Interpreters』
      Buku ini bukan sekadar manual, melainkan bahan belajar berbasis pengalaman, dengan kesenangan penulis terlihat dalam hal-hal seperti pola visitor
    • 『Crafting Interpreters』 sangat bagus, tetapi akan sempurna jika ada buku pendamping yang membahas type system, optimisasi, dan linking
    • Ini benar-benar buku yang bagus untuk belajar sendiri
    • Saya menamatkannya saat menunggu kelas di masa kuliah. Saya belum mencoba Nanopass, tetapi berniat mencobanya lewat tautan lain
    • Makalah Nanopass disimpan di repositori GitHub ini

  • Belakangan ini saya membuat toy compiler untuk bersenang-senang
    Alih-alih teori parsing yang rumit atau DSL, saya memakai parser combinator Megaparsec
    Logika parsing jadi jelas dan mudah dipakai ulang, serta tidak ada kerepotan dari pemisahan lexer/parser tradisional

    • Saya menganggap parser rekursif turun lebih praktis daripada generator parser LL/LR
      Bug-nya lebih sedikit, diagnosis error lebih baik, dan kebanyakan bahasa (C#, Rust, dll.) juga memakai pendekatan ini
      tree-sitter juga hebat, tetapi punya banyak dependensi. Sebaliknya, rekursif turun memungkinkan implementasi ringkas tanpa dependensi
    • Meski begitu, saya tetap merasa lebih baik mempertahankan pemisahan lexer/parser
      Keuntungan pendekatan parser combinator adalah lexer dan parser sama-sama bisa diperlakukan dengan tipe parser yang sama
      Ini bisa menyelesaikan masalah whitespace dan tokenisasi dengan rapi

  • Tautan makalah Nanopass yang sebelumnya mati bisa dilihat di sini

  • Yang mengajari saya compiler adalah artikel compiler Tiny Pascal di majalah BYTE tahun 1978
    Optimisasi saya pelajari dari kuliah musim panas Stanford oleh Ullman dan Hennessy
    Code generator-nya memakai pendekatan orisinal yang saya buat sendiri
    Saya punya 『Dragon Book』, tetapi sebenarnya belum pernah membacanya

  • Inti pendekatan Nanopass bukanlah jumlah pass, melainkan bahwa setiap pass mendefinisikan bahasa input dan output yang eksplisit
    Berkat cara berpikir yang terstruktur ini, banyak bug bisa ditemukan sebelum eksekusi
    Tutorial Crenshaw juga bagus, tetapi pengelolaan invariansi bahasa seperti ini adalah pembeda yang membuat compiler benar-benar bisa diskalakan

  • Saya ingat pernah mengimplementasikan optimizing compiler di kelas CS241 milik Profesor Michael Franz, murid Niklaus Wirth, saat di UC Irvine
    Tugasnya adalah menghasilkan bytecode untuk mesin virtual bernama DLX
    Materi terkait bisa dilihat di penjelasan arsitektur DLX dan
    gambar referensi algoritme alokasi register