Cara menulis kompiler yang sangat dasar

Kompiler tingkat lanjut seperti gccmengkompilasi kode ke dalam file yang dapat dibaca mesin sesuai dengan bahasa di mana kode telah ditulis (misalnya C, C ++, dll). Bahkan, mereka menginterpretasikan arti dari masing-masing kode sesuai dengan perpustakaan dan fungsi dari bahasa yang sesuai. Koreksi saya jika saya salah.

Saya ingin lebih memahami kompiler dengan menulis kompiler yang sangat mendasar (mungkin dalam C) untuk mengkompilasi file statis (misalnya Hello World dalam file teks). Saya mencoba beberapa tutorial dan buku, tetapi semuanya untuk kasus praktis. Mereka berurusan dengan menyusun kode dinamis dengan makna yang terhubung dengan bahasa yang sesuai.

Bagaimana saya bisa menulis kompiler dasar untuk mengubah teks statis menjadi file yang dapat dibaca mesin?

Langkah selanjutnya adalah memperkenalkan variabel ke dalam kompiler; bayangkan kita ingin menulis kompiler yang hanya mengkompilasi beberapa fungsi bahasa.

Memperkenalkan tutorial dan sumber daya yang praktis sangat dihargai :-)

Intro

Kompiler tipikal melakukan langkah-langkah berikut:

• Parsing: teks sumber dikonversi ke pohon sintaksis abstrak (AST).
• Resolusi referensi ke modul lain (C menunda langkah ini sampai menghubungkan).
• Validasi semantik: menghilangkan pernyataan yang benar secara sintaksis yang tidak masuk akal, misalnya kode yang tidak dapat dijangkau atau deklarasi rangkap.
• Transformasi yang setara dan optimisasi tingkat tinggi: AST ditransformasikan untuk mewakili komputasi yang lebih efisien dengan semantik yang sama. Ini termasuk misalnya perhitungan awal dari subekspresi umum dan ekspresi konstan, menghilangkan penugasan lokal yang berlebihan (lihat juga SSA ), dll.
• Pembuatan kode: AST diubah menjadi kode linier tingkat rendah, dengan lompatan, alokasi register, dan sejenisnya. Beberapa panggilan fungsi dapat diuraikan pada tahap ini, beberapa loop terbuka, dll.
• Optimalisasi lubang telepon: kode tingkat rendah dipindai untuk inefisiensi lokal sederhana yang dihilangkan.

Kebanyakan kompiler modern (misalnya, gcc dan dentang) ulangi dua langkah terakhir sekali lagi. Mereka menggunakan bahasa tingkat rendah menengah-platform tapi independen untuk pembuatan kode awal. Kemudian bahasa itu dikonversi menjadi kode platform-spesifik (x86, ARM, dll) melakukan hal yang kira-kira sama dengan cara yang dioptimalkan platform. Ini termasuk misalnya penggunaan instruksi vektor bila memungkinkan, penataan ulang instruksi untuk meningkatkan efisiensi prediksi cabang, dan sebagainya.

Setelah itu, kode objek siap untuk dihubungkan. Sebagian besar kompiler kode asli tahu cara memanggil tautan untuk menghasilkan yang dapat dieksekusi, tetapi itu bukan langkah kompilasi per se. Dalam bahasa seperti Java dan tautan C # mungkin benar-benar dinamis, dilakukan oleh VM pada waktu pengambilan.

Ingat dasar-dasarnya

• Buat itu bekerja
• Jadikan itu indah
• Jadikan efisien

Urutan klasik ini berlaku untuk semua pengembangan perangkat lunak, tetapi menanggung pengulangan.

Berkonsentrasilah pada langkah pertama dari urutan. Buat hal paling sederhana yang mungkin bisa berhasil.

Baca buku!

Baca Buku Naga oleh Aho dan Ullman. Ini klasik dan masih cukup berlaku hingga saat ini.

Desain Kompiler Modern juga dipuji.

Jika hal ini terlalu sulit bagi Anda sekarang, bacalah beberapa pengantar tentang penguraian terlebih dahulu; biasanya parsing pustaka termasuk intro dan contoh.

Pastikan Anda merasa nyaman bekerja dengan grafik, terutama pohon. Hal-hal ini adalah program-program yang dibuat dari pada tingkat logis.

Definisikan bahasa Anda dengan baik

Gunakan notasi apa pun yang Anda inginkan, tetapi pastikan Anda memiliki deskripsi yang lengkap dan konsisten dari bahasa Anda. Ini termasuk sintaks dan semantik.

Saatnya untuk menulis cuplikan kode dalam bahasa baru Anda sebagai kasus uji untuk kompiler masa depan.

Gunakan bahasa favorit Anda

Tidak apa-apa menulis kompiler dengan Python atau Ruby atau bahasa apa pun yang mudah bagi Anda. Gunakan algoritma sederhana yang Anda pahami dengan baik. Versi pertama tidak harus cepat, efisien, atau lengkap fitur. Hanya perlu cukup benar dan mudah dimodifikasi.

Tidak apa-apa untuk menulis tahapan kompiler yang berbeda dalam bahasa yang berbeda, jika diperlukan.

Bersiaplah untuk menulis banyak tes

Seluruh bahasa Anda harus dicakup oleh uji kasus; secara efektif itu akan ditentukan oleh mereka. Kenal baik-baik dengan kerangka pengujian pilihan Anda. Tulis tes dari hari pertama. Berkonsentrasi pada tes 'positif' yang menerima kode yang benar, yang bertentangan dengan deteksi kode yang salah.

Jalankan semua tes secara teratur. Perbaiki tes yang rusak sebelum melanjutkan. Memalukan untuk berakhir dengan bahasa yang tidak jelas yang tidak dapat menerima kode yang valid.

Buat parser yang bagus

Generator Parser banyak . Pilih apa pun yang Anda inginkan. Anda juga dapat menulis parser Anda sendiri dari awal, tetapi itu hanya layak jika sintaks bahasa Anda sudah mati sederhana.

Parser harus mendeteksi dan melaporkan kesalahan sintaksis. Tulis banyak kasus uji, baik positif maupun negatif; gunakan kembali kode yang Anda tulis saat mendefinisikan bahasa.

Output parser Anda adalah pohon sintaksis abstrak.

Jika bahasa Anda memiliki modul, output parser mungkin merupakan representasi paling sederhana dari 'kode objek' yang Anda hasilkan. Ada banyak cara sederhana untuk membuang pohon ke file dan dengan cepat memuatnya kembali.

Buat validator semantik

Kemungkinan besar bahasa Anda memungkinkan konstruksi yang benar secara sintaksis yang mungkin tidak masuk akal dalam konteks tertentu. Contohnya adalah deklarasi duplikat dari variabel yang sama atau melewati parameter dari tipe yang salah. Validator akan mendeteksi kesalahan seperti itu melihat pohon.

Validator juga akan menyelesaikan referensi ke modul lain yang ditulis dalam bahasa Anda, memuat modul lain ini dan digunakan dalam proses validasi. Misalnya, langkah ini akan memastikan bahwa jumlah parameter yang diteruskan ke fungsi dari modul lain sudah benar.

Sekali lagi, tulis dan jalankan banyak test case. Kasus-kasus sepele sangat diperlukan dalam pemecahan masalah seperti pintar dan kompleks.

Buat kode

Gunakan teknik paling sederhana yang Anda tahu. Seringkali tidak apa-apa untuk langsung menerjemahkan konstruksi bahasa (seperti ifpernyataan) ke templat kode yang parametrik ringan, tidak seperti templat HTML.

Sekali lagi, abaikan efisiensi dan konsentrasi pada kebenaran.

Menargetkan VM level rendah independen-platform

Saya kira Anda mengabaikan hal-hal tingkat rendah kecuali jika Anda tertarik pada detail perangkat keras tertentu. Detail-detail ini berdarah dan kompleks.

Pilihan Anda:

• LLVM: memungkinkan pembuatan kode mesin yang efisien, biasanya untuk x86 dan ARM.
• CLR: target .NET, sebagian besar berbasis x86 / Windows; memiliki JIT yang bagus.
• JVM: menargetkan dunia Java, cukup multiplatform, memiliki JIT yang baik.

Abaikan optimasi

Optimalisasi sulit. Hampir selalu optimisasi prematur. Hasilkan kode yang tidak efisien tetapi benar. Terapkan seluruh bahasa sebelum Anda mencoba mengoptimalkan kode yang dihasilkan.

Tentu saja, optimasi sepele boleh saja diperkenalkan. Tetapi hindari hal-hal yang licik dan berbulu sebelum kompiler Anda stabil.

Terus?

Jika semua ini tidak terlalu menakutkan bagi Anda, silakan lanjutkan! Untuk bahasa yang sederhana, setiap langkah mungkin lebih sederhana dari yang Anda kira.

Melihat 'Hello world' dari program yang dibuat oleh kompiler Anda mungkin sepadan dengan usaha.

Jack Crenshaw's Let's Build a Compiler , walaupun belum selesai, adalah pengantar dan tutorial yang mudah dibaca.

Konstruksi Kompilator Nicklaus Wirth adalah buku teks yang sangat bagus tentang dasar-dasar konstruksi kompiler sederhana. Dia berfokus pada keturunan rekursif top-down, yang, mari kita hadapi itu, BANYAK lebih mudah daripada lex / yacc atau flex / bison. Kompilator PASCAL asli yang ditulis kelompoknya dilakukan dengan cara ini.

Orang lain telah menyebutkan berbagai buku Naga.

Saya benar-benar mulai dengan menulis kompiler untuk Brainfuck . Ini adalah bahasa yang cukup bodoh untuk diprogram, tetapi hanya memiliki 8 instruksi untuk diterapkan. Ini tentang sesederhana yang Anda bisa dapatkan dan ada instruksi C yang setara di luar sana untuk perintah yang terlibat jika Anda menemukan sintaks yang tidak sesuai.

Jika Anda benar-benar ingin menulis kode yang dapat dibaca mesin saja dan tidak ditargetkan ke mesin virtual, maka Anda harus membaca manual Intel dan mengerti

• Sebuah. Menautkan dan Memuat kode yang dapat dijalankan

• b. Format COFF dan PE (untuk windows), atau memahami format ELF (untuk Linux)

• c. Memahami format file .COM (lebih mudah daripada PE)
• d. Memahami assembler
• e. Memahami kompiler dan mesin pembuatan kode dalam kompiler.

Jauh lebih sulit dilakukan daripada dikatakan. Saya sarankan Anda untuk membaca Compiler dan Juru Bahasa dalam C ++ sebagai titik awal (Oleh Ronald Mak). Atau, "mari kita buat kompiler" oleh Crenshaw adalah OK.

Jika Anda tidak ingin melakukan itu, Anda juga bisa menulis VM Anda sendiri dan menulis pembuat kode yang ditargetkan untuk VM itu.

• Titik awal lainnya: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/
• Great Book Oleh Kenneth Louden: http://www.amazon.com/Compiler-Construction-Principles-Kenneth-Louden/dp/0534939724

Kiat: Pelajari Flex dan Bison PERTAMA. Kemudian lanjutkan untuk membangun kompiler / VM Anda sendiri.

Semoga berhasil!

Pendekatan DIY untuk kompiler sederhana bisa terlihat seperti ini (setidaknya seperti itulah proyek uni saya):

1. Tentukan Grammar bahasa. Bebas konteks.
2. Jika tata bahasa Anda belum LL (1), lakukan sekarang. Perhatikan, bahwa beberapa aturan yang tampak ok dalam tata bahasa CF polos mungkin menjadi jelek. Mungkin bahasa Anda terlalu rumit ...
3. Tulis Lexer yang memotong aliran teks menjadi token (kata, angka, literal).
4. Tulis parser keturunan rekursif top-down untuk tata bahasa Anda, yang menerima atau menolak input.
5. Tambahkan generasi pohon sintaksis ke parser Anda.
6. Tulis pembuat kode mesin dari pohon sintaks.
7. Untung & Bir, atau Anda dapat mulai berpikir bagaimana melakukan parser yang lebih pintar atau menghasilkan kode yang lebih baik.

Seharusnya ada banyak literatur yang menjelaskan setiap langkah secara terperinci.