Apa prosedur umum yang digunakan ketika kompiler mengetikkan ekspresi "kompleks" secara statis?

Catatan: Ketika saya menggunakan "complex" dalam judul, maksud saya bahwa ekspresi memiliki banyak operator dan operan. Bukan berarti ungkapan itu sendiri rumit.

Saya baru-baru ini bekerja pada kompiler sederhana untuk perakitan x86-64. Saya telah menyelesaikan ujung depan utama kompiler - lexer dan parser - dan sekarang saya dapat menghasilkan representasi Pohon Sintaksis Abstrak dari program saya. Dan karena bahasa saya akan diketik secara statis, saya sekarang sedang melakukan tahap selanjutnya: ketik memeriksa kode sumber. Namun, saya sampai pada masalah dan belum bisa menyelesaikannya dengan baik.

Perhatikan contoh berikut:

Parser kompiler saya telah membaca baris kode ini:

int a = 1 + 2 - 3 * 4 - 5

Dan mengubahnya menjadi AST berikut:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Sekarang harus mengetik periksa AST. itu dimulai dengan pertama-tama memeriksa =operator. Pertama-tama memeriksa sisi kiri operator. Itu melihat bahwa variabel adinyatakan sebagai integer. Jadi sekarang harus memverifikasi bahwa ekspresi sisi kanan mengevaluasi ke integer.

Saya mengerti bagaimana ini bisa dilakukan jika ekspresi itu hanya nilai tunggal, seperti 1atau 'a'. Tetapi bagaimana ini akan dilakukan untuk ekspresi dengan berbagai nilai dan operan - ekspresi kompleks - seperti yang di atas? Untuk menentukan nilai ekspresi dengan benar, sepertinya pemeriksa tipe harus mengeksekusi ekspresi itu sendiri dan mencatat hasilnya. Tapi ini jelas nampaknya mengalahkan tujuan memisahkan fase kompilasi dan eksekusi.

Satu-satunya cara saya membayangkan ini bisa dilakukan adalah dengan memeriksa secara rekursif daun setiap subekspresi di AST dan memverifikasi semua jenis daun sesuai dengan jenis operator yang diharapkan. Jadi dimulai dengan =operator, pemeriksa tipe kemudian akan memindai semua AST sisi kiri dan memverifikasi bahwa semua daun adalah bilangan bulat. Kemudian akan mengulang ini untuk setiap operator di subekspresi.

Saya sudah mencoba meneliti topik dalam salinan "The Dragon Book" saya , tetapi sepertinya tidak masuk ke banyak detail, dan hanya mengulangi apa yang sudah saya ketahui.

Apa metode yang biasa digunakan ketika kompiler mengetik ekspresi memeriksa dengan banyak operator dan operan? Apakah ada metode yang saya sebutkan di atas yang digunakan? Jika tidak, apa metode dan bagaimana cara kerjanya?

Rekursi adalah jawabannya, tetapi Anda turun ke setiap subtree sebelum menangani operasi:

int a = 1 + 2 - 3 * 4 - 5

ke bentuk pohon:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Inferring tipe terjadi dengan pertama-tama berjalan di sisi kiri, lalu di sisi kanan, dan kemudian menangani operator segera setelah tipe operan disimpulkan:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> turun ke lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> menyimpulkan a. adikenal sebagai int. Kami kembali ke assignsimpul sekarang:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> turun ke rhs, lalu ke lhs dari operator dalam sampai kita mencapai sesuatu yang menarik

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> menyimpulkan jenis 1, yaitu int, dan kembali ke induk

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> masuk ke rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> menyimpulkan jenis 2, yaitu int, dan kembali ke induk

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> menyimpulkan jenis add(int, int), yaitu int, dan kembali ke induk

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> turun ke rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

dll, sampai Anda berakhir dengan

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Apakah tugas itu sendiri juga merupakan ekspresi dengan tipe tergantung pada bahasa Anda.

Yang penting takeaway: untuk menentukan jenis simpul operator di pohon, Anda hanya perlu melihat anak-anak terdekatnya, yang sudah harus memiliki jenis yang ditugaskan kepada mereka.

Apa yang biasanya metode yang digunakan ketika kompiler adalah tipe memeriksa ekspresi dengan banyak operator dan operan.

Baca wikipage pada sistem tipe dan inferensi tipe dan pada sistem tipe Hindley-Milner , yang menggunakan penyatuan . Baca juga tentang semantik denotasi dan semantik operasional .

Pengecekan tipe bisa lebih sederhana jika:

• semua variabel Anda suka asecara eksplisit dinyatakan dengan tipe. Ini seperti C atau Pascal atau C ++ 98, tetapi tidak seperti C ++ 11 yang memiliki beberapa tipe inferensi auto.
• semua nilai literal seperti 1,, 2atau 'c'memiliki tipe yang melekat: sebuah literal int selalu memiliki tipe int, karakter literal selalu memiliki tipe char,….
• fungsi dan operator tidak kelebihan beban, mis. +operator selalu memiliki tipe (int, int) -> int. C memiliki kelebihan untuk operator ( +berfungsi untuk tipe bilangan bulat yang ditandatangani dan tidak ditandatangani serta untuk ganda) tetapi tidak ada fungsi yang berlebihan.

Di bawah kendala ini, algoritma dekorasi tipe AST rekursif bottom-up bisa cukup (ini hanya peduli tentang jenis , bukan tentang nilai-nilai konkret, jadi adalah pendekatan waktu kompilasi):

• Untuk setiap cakupan, Anda menyimpan tabel untuk tipe semua variabel yang terlihat (disebut lingkungan). Setelah deklarasi int a, Anda akan menambahkan entria: int ke tabel.

• Mengetik daun adalah kasus dasar rekursi sepele: jenis literal seperti 1sudah diketahui, dan jenis variabel suka adapat dilihat di lingkungan.

• Untuk mengetik ekspresi dengan beberapa operator dan operan sesuai dengan jenis operan (nested sub-ekspresi) yang dikomputasi sebelumnya, kami menggunakan rekursi pada operan (jadi kami mengetikkan sub-ekspresi ini terlebih dahulu) dan mengikuti aturan pengetikan yang terkait dengan operator .

Jadi dalam contoh Anda, 4 * 3dan 1 + 2diketik intkarena 4& 3dan 1& 2telah diketik sebelumnya intdan aturan pengetikan Anda mengatakan bahwa jumlah atau produk dari dua int-s adalah int, dan seterusnya untuk(4 * 3) - (1 + 2) .

Kemudian Baca buku Jenis dan Bahasa Pemrograman Pierce . Saya sarankan untuk belajar sedikit Ocaml dan λ-calculus

Untuk bahasa yang diketik secara lebih dinamis (seperti Lisp), baca juga Lisinn In Small Pieces dari Queinnec

Baca juga Pragmatik Bahasa Pemrograman Scott buku

BTW, Anda tidak dapat memiliki kode pengetikan agnostik bahasa, karena sistem jenis adalah bagian penting dari semantik bahasa .

Dalam C (dan terus terang sebagian besar bahasa yang diketik secara statis berdasarkan C) setiap operator dapat dilihat sebagai gula sintaksis untuk panggilan fungsi.

Jadi ekspresi Anda dapat ditulis ulang sebagai:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Kemudian resolusi kelebihan akan menendang dan memutuskan bahwa setiap fungsi adalah tipe (int, int)atau (const int&, const int&).

Cara ini membuat resolusi jenis mudah dimengerti dan diikuti dan (lebih penting) mudah diterapkan. Informasi tentang tipe hanya mengalir dalam 1 cara (dari ekspresi dalam ke luar).

Itulah alasan mengapa double x = 1/2;akan menghasilkan x == 0karena 1/2dievaluasi sebagai ekspresi int.

Berfokus pada algoritme Anda, coba ubah ke bawah-ke-atas. Anda tahu tipe pf variabel dan konstanta; tandai simpul yang bertuliskan operator dengan tipe hasil. Biarkan daun menentukan tipe operator, juga kebalikan dari ide Anda.

Ini sebenarnya cukup mudah, selama Anda anggap +sebagai berbagai fungsi daripada konsep tunggal.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

Selama tahap parsing di sisi kanan, parser mengambil 1, tahu itu int, lalu mem-parsing +, dan menyimpannya sebagai "nama fungsi yang tidak terselesaikan", lalu mem-parsing 2, tahu itu int, dan kemudian mengembalikannya ke tumpukan. The +fungsi simpul sekarang tahu kedua jenis parameter, sehingga dapat menyelesaikan +dalam int operator+(int, int), jadi sekarang tahu jenis ini sub-ekspresi, dan parser terus pada itu selamat jalan.

Seperti yang Anda lihat, setelah pohon dibangun sepenuhnya, setiap node, termasuk pemanggilan fungsi, tahu tipenya. Ini adalah kunci karena memungkinkan untuk fungsi yang mengembalikan tipe berbeda dari parameternya.

char* ptr = itoa(3);

Di sini, pohonnya adalah:

    char* itoa(int)
     /           \
  ptr(char*)      3

Dasar untuk pengecekan tipe bukanlah apa yang dilakukan oleh kompiler, itu adalah apa yang didefinisikan oleh bahasa.

Dalam bahasa C, setiap operan memiliki tipe. "abc" memiliki tipe "array const const". 1 memiliki tipe "int". 1L memiliki tipe "panjang". Jika x dan y adalah ekspresi, maka ada aturan untuk tipe x + y dan seterusnya. Jadi kompiler jelas harus mengikuti aturan bahasa.

Pada bahasa modern seperti Swift, aturannya jauh lebih rumit. Beberapa kasus sederhana seperti dalam C. Kasus lain, kompilator melihat ekspresi, telah diberitahu sebelumnya apa jenis ekspresi yang seharusnya, dan menentukan jenis subekspresi berdasarkan itu. Jika x dan y adalah variabel dari tipe yang berbeda, dan ekspresi yang sama diberikan, ekspresi itu mungkin dievaluasi dengan cara yang berbeda. Misalnya menetapkan 12 * (2/3) akan menetapkan 8,0 untuk Double dan 0 ke Int. Dan Anda memiliki kasus di mana kompiler tahu bahwa dua jenis terkait dan mencari tahu jenis apa mereka didasarkan pada itu.

Contoh cepat:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

mencetak "8.0, 0".

Dalam penugasan x = 12 * (2/3): Sisi kiri memiliki tipe Double, oleh karena itu sisi kanan harus tipe Double. Hanya ada satu kelebihan untuk operator "*" yang mengembalikan Double, dan itu adalah Double * Double -> Double. Oleh karena itu 12 harus memiliki tipe Double, serta 2 / 3. 12 mendukung protokol "IntegerLiteralConvertible". Double memiliki penginisialisasi yang mengambil argumen tipe "IntegerLiteralConvertible", jadi 12 dikonversi menjadi Double. 2/3 harus memiliki tipe Double. Hanya ada satu kelebihan untuk operator "/" yang mengembalikan Double, dan itu adalah Double / Double -> Double. 2 dan 3 dikonversi menjadi Double. Hasil 2/3 adalah 0,6666666. Hasil dari 12 * (2/3) adalah 8.0. 8.0 ditugaskan untuk x.

Dalam penugasan y = 12 * (2/3), y di sisi kiri bertipe Int, sehingga sisi kanan harus bertipe Int, jadi 12, 2, 3 dikonversi ke Int dengan hasil 2/3 = 0, 12 * (2/3) = 0.