Bagaimana tepatnya kompiler pulih dari kesalahan tipe?

Saya telah membaca beberapa makalah, artikel, dan bagian 4.1.4, bab 4 dari Penyusun: Prinsip, Teknik, dan Peralatan (Edisi ke-2) (alias "The Dragon Book") yang semuanya membahas topik pemulihan kesalahan kompiler sintaksis. Namun, setelah bereksperimen dengan beberapa kompiler modern, saya telah melihat bahwa mereka juga pulih dari kesalahan semantik , serta kesalahan sintaksis.

Saya cukup mengerti dengan baik algoritma dan teknik di balik kompiler yang pulih dari kesalahan yang terkait secara sintaksis, namun saya tidak benar-benar mengerti bagaimana kompiler dapat pulih dari kesalahan semantik.

Saat ini saya menggunakan sedikit variasi pola pengunjung untuk menghasilkan kode dari pohon sintaksis abstrak saya. Pertimbangkan kompiler saya mengkompilasi ekspresi berikut:

1 / (2 * (3 + "4"))

Compiler akan menghasilkan pohon sintaksis abstrak berikut:

      op(/)
        |
     -------
    /       \ 
 int(1)    op(*)
             |
          -------
         /       \
       int(2)   op(+)
                  |
               -------
              /       \
           int(3)   str(4)

Tahap pembuatan kode kemudian akan menggunakan pola pengunjung untuk secara rekursif melintasi pohon sintaksis abstrak dan melakukan pengecekan tipe. Pohon sintaksis abstrak akan dilintasi hingga kompiler sampai ke bagian terdalam dari ekspresi; (3 + "4"). Kompilator kemudian memeriksa setiap sisi ekspresi dan melihat bahwa mereka tidak setara secara semantik. Kompiler memunculkan kesalahan tipe. Di sinilah masalahnya. Apa yang sekarang harus dilakukan oleh kompiler ?

Agar kompilator pulih dari kesalahan ini dan terus mengetik memeriksa bagian luar ekspresi, ia harus mengembalikan beberapa jenis ( intatau str) dari mengevaluasi bagian terdalam dari ekspresi, ke bagian terdalam berikutnya dari ekspresi. Tapi itu tidak memiliki tipe untuk kembali . Karena kesalahan tipe terjadi, tidak ada tipe yang dideduksi.

Salah satu solusi yang mungkin saya dalilkan, adalah bahwa jika kesalahan jenis memang terjadi, kesalahan harus dinaikkan, dan nilai khusus yang menandakan bahwa kesalahan jenis terjadi, harus dikembalikan ke panggilan traversal pohon sintaksis abstrak sebelumnya. Jika panggilan traversal sebelumnya menemukan nilai ini, mereka tahu bahwa kesalahan tipe terjadi lebih dalam di pohon sintaksis abstrak, dan harus menghindari mencoba menyimpulkan suatu tipe. Meskipun metode ini tampaknya berhasil, tampaknya sangat tidak efisien. Jika bagian terdalam dari ekspresi jauh di dalam pohon sintaksis abstrak, maka kompiler harus membuat banyak panggilan rekursif hanya untuk menyadari bahwa tidak ada pekerjaan nyata yang dapat dilakukan, dan hanya kembali dari masing-masing.

Apakah metode yang saya jelaskan di atas digunakan (saya ragu). Jika demikian, apakah itu tidak efisien? Jika tidak, apa sebenarnya metode yang digunakan ketika kompiler pulih dari kesalahan semantik?

Ide yang Anda usulkan pada dasarnya benar.

Kuncinya adalah bahwa jenis node AST dihitung hanya sekali dan kemudian disimpan. Kapan pun jenis itu dibutuhkan lagi, ia hanya mengambil jenis yang disimpan. Jika resolusi berakhir dengan kesalahan, jenis kesalahan disimpan sebagai gantinya.

Salah satu pendekatan yang menarik adalah memiliki jenis kesalahan khusus. Ketika kesalahan seperti itu pertama kali ditemukan, diagnostik dicatat, dan jenis kesalahan dikembalikan sebagai jenis ekspresi. Jenis kesalahan ini memiliki beberapa sifat menarik:

• Operasi apa pun yang dilakukan di atasnya berhasil (untuk mencegah kaskade pesan kesalahan semua disebabkan oleh kesalahan asli yang sama)
• Hasil dari setiap operasi yang dilakukan pada objek dengan tipe kesalahan juga memiliki tipe kesalahan
• Jika jenis kesalahan mencapai sejauh pembuatan kode, pembuat kode melihat penggunaan dan menghasilkan kode yang gagal (misalnya melempar pengecualian, batal, atau apa pun yang sesuai untuk bahasa Anda)

Dengan kombinasi ini, Anda dapat benar-benar berhasil mengkompilasi kode yang berisi kesalahan ketik, dan selama kode itu tidak benar-benar digunakan, tidak akan terjadi kesalahan runtime. Ini bisa berguna, misalnya, untuk memungkinkan Anda menjalankan tes unit untuk bagian-bagian kode yang tidak terpengaruh.

Jika ada kesalahan semantik, pesan kesalahan kompilasi yang mengindikasikan hal itu dikeluarkan untuk pengguna.

Setelah selesai, tidak masalah membatalkan kompilasi karena program input salah - ini bukan program hukum dalam bahasa, sehingga hanya dapat ditolak.

Itu cukup keras, jadi ada alternatif yang lebih lembut. Batalkan pembuatan kode dan pembuatan file keluaran apa pun, namun teruskan sesuatu untuk mencari lebih banyak kesalahan.

Sebagai contoh, itu bisa dengan mudah membatalkan setiap analisis jenis lebih lanjut untuk pohon ekspresi saat ini, dan melanjutkan memproses ekspresi dari pernyataan berikutnya.

Anggap saja bahasa Anda memungkinkan penambahan bilangan bulat, dan memungkinkan rangkaian string dengan +operator.

Karena int + stringtidak diizinkan, mengevaluasi +kehendak akan menghasilkan kesalahan yang dilaporkan. Kompilator hanya bisa kembali errorsebagai tipenya. Atau mungkin lebih pintar, karena int + int -> intdan string + string -> stringdiizinkan, mungkin mengembalikan "kesalahan, bisa int atau string".

Kemudian datang *operator, dan kami hanya akan menganggap int + intdiizinkan. Compiler kemudian dapat memutuskan bahwa +sebenarnya seharusnya kembali int, dan tipe yang dikembalikan untuk *kemudian int, tanpa pesan kesalahan.