Menulis Kompiler Kompiler - Wawasan Penggunaan dan Fitur

Ini adalah bagian dari serangkaian pertanyaan yang berfokus pada proyek saudara ke Proyek Abstraksi, yang bertujuan untuk abstrak konsep yang digunakan dalam desain bahasa dalam bentuk kerangka kerja. Proyek saudara disebut OILexer, yang bertujuan untuk membangun parser dari file tata bahasa, tanpa menggunakan injeksi kode pada pertandingan.

Beberapa halaman lain yang terkait dengan pertanyaan ini, terkait dengan pengetikan struktural, dapat dilihat di sini , dan kemudahan penggunaannya, ditemukan di sini . Meta-topik yang terkait dengan penyelidikan tentang kerangka kerja dan tempat yang tepat untuk memposting dapat ditemukan di sini .

Saya sampai pada titik di mana saya akan mulai mengekstraksi pohon parse dari tata bahasa yang diberikan, diikuti oleh parser Keturunan Rekursif yang menggunakan DFA untuk membedakan jalur maju (mirip dengan LL ANTLR 4 (*)), jadi saya kupikir aku akan membukanya untuk mendapatkan wawasan.

Dalam kompiler parser, fitur apa saja yang ideal?

Sejauh ini di sini adalah gambaran singkat tentang apa yang diterapkan:

1. Templat
2. Lihat ke depan prediksi, mengetahui apa yang valid pada titik tertentu.
3. Peraturan 'Deliteralization' mengambil literal dalam aturan dan memutuskan dari mana token mereka berasal.
4. Automata Nondeterministic
5. Deterministic Automata
6. Mesin status leksikal sederhana untuk pengenalan token
7. Metode otomatisasi token:
   • Pindai - berguna untuk komentar: Komentar: = "/ *" Pindai ("* /");
   • Kurangi - Berguna untuk Pengidentifikasi: Pengidentifikasi: = Kurangi (IdentifierBody, Kata Kunci);
     • Pastikan pengidentifikasi tidak menerima kata kunci.
   • Encode - Mengkode otomatisasi sebagai hitungan X seri transisi basis N.
     • UnicodeEscape: = "\\ u" BaseEncode (IdentifierCharNoEscape, 16, 4);
       • Membuat pelarian unicode dalam heksadesimal, dengan hex 4-transisi. Perbedaan antara ini dan: [0-9A-Fa-f] {4} adalah otomatisasi yang dihasilkan dengan Encode membatasi set nilai heksadesimal yang diizinkan ke ruang lingkup IdentifierCharNoEscape. Jadi, jika Anda memberikannya \ u005c, versi enkode tidak akan menerima nilai. Hal-hal seperti ini memiliki peringatan serius: Gunakan hemat. Otomatisasi yang dihasilkan bisa sangat kompleks.

Apa yang tidak diimplementasikan adalah generasi CST, saya perlu menyesuaikan otomatisasi Deterministic untuk membawa konteks yang tepat untuk membuatnya bekerja.

Bagi siapa pun yang tertarik, saya telah mengunggah sebuah cetakan cantik dari bentuk asli proyek T * y♯ . Setiap file harus ditautkan ke setiap file lainnya, saya mulai menautkan dalam aturan individu untuk mengikuti mereka, tetapi itu akan memakan waktu terlalu lama (akan lebih mudah untuk diotomatisasi!)

Jika lebih banyak konteks diperlukan, silakan posting sesuai dengan itu.

Sunting 5-14-2013 : Saya telah menulis kode untuk membuat grafik GraphViz untuk mesin negara dalam bahasa yang diberikan. Berikut ini adalah grafik GraphViz dari AssemblyPart . Anggota yang ditautkan dalam uraian bahasa harus memiliki ruleename.txt di folder relatifnya dengan digraf untuk aturan itu. Beberapa uraian bahasa telah berubah sejak saya memposting contoh, ini karena menyederhanakan hal-hal tentang tata bahasa. Berikut ini adalah gambar graphviz yang menarik .

Ini adalah pertanyaan yang sangat bagus.

Saya telah mengerjakan banyak parsing baru-baru ini, dan IMHO beberapa fitur utama adalah:

• API terprogram - sehingga dapat digunakan dari dalam bahasa pemrograman, idealnya hanya dengan mengimpor perpustakaan. Ini dapat memiliki antarmuka seperti GUI atau BNF juga, tetapi yang terprogram adalah kuncinya, karena Anda dapat menggunakan kembali tooling, IDE, analisis statis, pengujian, fasilitas abstraksi bahasa, keakraban programmer, generator dokumentasi, proses pembuatan, dll. Plus, Anda bisa bermain secara interaktif dengan parser kecil, yang secara dramatis mengurangi kurva belajar. Alasan ini menempatkannya di bagian atas daftar "fitur penting" saya.

• pelaporan kesalahan, seperti yang disebutkan @guysherman. Ketika kesalahan ditemukan, saya ingin tahu di mana kesalahan itu dan apa yang terjadi ketika itu terjadi. Sayangnya, saya belum dapat menemukan sumber daya yang baik untuk menjelaskan cara menghasilkan kesalahan yang layak saat backtracking dimainkan. (Meskipun perhatikan @ Sk-logika komentar di bawah ini).

• hasil parsial. Ketika parsing gagal, saya ingin dapat melihat apa yang berhasil diurai dari bagian input yang sebelum lokasi kesalahan.

• abstraksi. Anda tidak pernah dapat membangun fungsi yang cukup, dan pengguna akan selalu membutuhkan lebih banyak, jadi mencoba mencari tahu semua fungsi yang mungkin ada di muka akan menemui kegagalan. Apakah ini yang Anda maksud dengan templat?

• Saya setuju dengan # 2 Anda (prediksi prediksi). Saya pikir ini membantu untuk menghasilkan laporan kesalahan yang baik. Apakah ini berguna untuk hal lain?

• dukungan untuk membangun pohon parse saat parsing terjadi, mungkin:

  • pohon sintaksis konkret, di mana struktur pohon terkait langsung dengan tata bahasa dan termasuk informasi tata letak untuk pelaporan kesalahan fase selanjutnya. Dalam hal ini, klien tidak harus melakukan apa pun untuk mendapatkan struktur pohon yang tepat - itu harus bergantung langsung pada tata bahasa.
  • pohon sintaksis abstrak. Dalam hal ini, pengguna dapat bermain-main dengan semua dan semua pohon parse

• semacam penebangan. Saya tidak yakin tentang yang ini; mungkin untuk menunjukkan jejak aturan yang telah diuraikan parser, atau untuk melacak token sampah seperti spasi putih atau komentar, dalam kasus (misalnya) Anda ingin menggunakan token untuk menghasilkan dokumentasi HTML.

• kemampuan untuk berurusan dengan bahasa yang peka konteks. Tidak yakin seberapa penting yang satu ini, baik - dalam praktiknya, tampaknya lebih bersih untuk mengurai superset dari bahasa dengan tata bahasa bebas konteks, kemudian untuk memeriksa kendala peka konteks dalam tambahan selanjutnya.

• pesan kesalahan khusus, sehingga saya dapat mengatur laporan kesalahan dalam situasi tertentu dan mungkin lebih cepat memahami dan memperbaiki masalah.

Di sisi lain, saya tidak menemukan koreksi kesalahan sangat penting - meskipun saya tidak mengetahui perkembangan terkini. Masalah yang saya perhatikan adalah bahwa koreksi potensial yang disediakan oleh peralatan tersebut adalah: 1) terlalu banyak, dan 2) tidak sesuai dengan kesalahan yang sebenarnya dibuat, dan karena itu tidak terlalu membantu. Semoga situasi ini akan membaik (atau mungkin sudah melakukannya).

Saya tidak berpengalaman dalam desain bahasa, tetapi saya pernah mencoba menulis parser sekali, ketika saya sedang membuat dan IDE untuk mesin permainan.

Sesuatu yang penting bagi pengguna akhir Anda, menurut pendapat saya, adalah pesan kesalahan yang masuk akal. Saya tahu, bukan titik yang sangat mengguncang bumi, tetapi mengikutinya ke belakang, salah satu implikasi utama dari hal ini adalah Anda harus dapat menghindari hal-hal yang salah. Dari mana asal positif palsu? Mereka datang dari pengurai yang jatuh pada kesalahan pertama dan tidak pernah benar-benar pulih. C / C ++ terkenal karena hal ini (walaupun kompiler yang lebih baru sedikit lebih pintar).

Jadi, apa yang Anda butuhkan? Saya pikir daripada hanya tahu apa yang valid / tidak valid pada suatu titik, Anda perlu tahu bagaimana mengambil apa yang tidak valid dan membuat perubahan minimal untuk membuatnya valid - sehingga Anda dapat melanjutkan penguraian tanpa menghasilkan kesalahan palsu terkait untuk keturunan rekursif Anda menjadi bingung. Mampu membangun parser yang dapat menghasilkan informasi ini tidak hanya memberi Anda parser yang sangat kuat, tetapi membuka beberapa fitur fantastis untuk perangkat lunak yang mengkonsumsi parser.

Saya menyadari bahwa saya mungkin menyarankan sesuatu yang benar-benar sulit, atau jelas sekali, maaf jika ini masalahnya. Jika ini bukan hal yang Anda cari, dengan senang hati saya akan menghapus jawaban saya.

Tata bahasanya tidak boleh memiliki batasan seperti "jangan tinggalkan aturan rekursif". Ini konyol bahwa alat banyak digunakan saat ini memiliki ini dan hanya dapat memahami mengisap tata bahasa LL - hampir 50 tahun setelah yacc melakukannya dengan benar.

Contoh untuk rekursi kanan (menggunakan sintaksis yacc):

list: 
      elem                  { $$ = singleton($1); }
    | elem ',' list         { $$ = cons($1, $2);  }
    ;

Contoh untuk rekursi kiri (menggunakan yacc synatx):

funapp:
    term                    { $$ = $1; }
    | funapp term           { $$ = application($1, $2); }
    ;

Sekarang, ini mungkin "refactored" untuk sesuatu yang lain, tetapi dalam kedua kasus, jenis rekursi khusus adalah cara yang "benar" untuk menulis ini, karena (dalam bahasa contoh) daftar adalah rekursif yang tepat sementara aplikasi fungsi dibiarkan rekursif .

Seseorang dapat mengharapkan dari alat-alat canggih bahwa mereka mendukung cara alami untuk menulis barang, alih-alih mengharuskan seseorang untuk "refactor" segala sesuatu menjadi kiri / kanan rekursif bentuk alat memaksakan ke satu.