Halo semuanya! Sebagai seorang programmer, saya selalu mencari cara untuk meningkatkan keterampilan saya. Suatu Jumat malam, pikiran muncul di kepalaku - "Bukankah aku menulis kompiler?"
Siapa yang peduli untuk mengetahui apa yang terjadi, selamat datang di kucing.
Berdasarkan "teori klasik kompiler" V. E. Karpov, kita dapat membedakan 5 tahap utama kompilasi:
- Analisis leksikal
- Parsing
- Pembuatan kode tengah
- Optimasi
- Generasi akhir, objek, kode
Tentang semuanya, lima bagian, Anda bisa menulis banyak kalimat dan artikel. Tapi, hari ini, kita akan membahas dua yang pertama dan bagaimana saya memilih struktur mereka di perpustakaan yang terpisah.
Ketika saya memutuskan untuk menulis, bahkan sebagian kecil, dari kompiler, saya tidak memikirkan bahasa apa yang saya tulis, karena alasan ini, hasilnya adalah perpustakaan untuk analisis leksikal dan sintaksis dari bahasa apa pun.
Tokenisasi
Sebelum Anda membangun sintaks dan pohon leksikal, menghasilkan kode yang dihasilkan dan melakukan hal-hal enak lainnya, Anda perlu memecah kode sumber menjadi garis, karakter, angka.
Di mana setiap elemen akan memiliki tipe yang didefinisikan secara tepat. Token jenis yang tidak terdefinisi akan dianggap sebagai kesalahan sintaks selama parsing.
Dalam konteks kompilasi, kode sumber dianggap sebagai peta-sumber, merupakan praktik yang baik untuk menyimpannya dalam proses leksikal dan penguraian untuk umpan balik dari pemrogram dan menunjukkan kesalahan sintaksis dalam kode sumber.
Anda dapat memecah kode sumber menjadi array token menggunakan ekspresi reguler sederhana:
/\S+/gm
Itu dapat berubah tergantung pada kondisi penguraian tambahan, seperti: penguraian garis, penguraian tab, penguraian ruang.
Hasil pemisahan akan berupa array kata-kata dari kode sumber, dan kata-kata tersebut diuraikan dari satu ruang ke ruang lain, yaitu desain ini:
let hello = 'world';
Ini akan dikonversi ke set token berikut:
["let", "hello", "=", "'world';"]
Untuk mendapatkan set token terakhir, Anda harus memeriksa masing-masingnya dengan ekspresi reguler tambahan:
/(\W)|(\w+)/gm
Hasilnya akan menjadi set token yang kita butuhkan:
["let", "hello", "=", "'", "world", "'", ";"]
Semua token yang kami terima, kami tulis ke larik, beserta indeksnya di peta sumber
Analisis leksikal
Sekarang kita memiliki array token, kita perlu menentukan tipe mereka untuk meneruskannya ke penguraian.
Algoritma yang mendefinisikan token dan tipenya disebut - Lexer
Token dan tipenya, yang didefinisikan Lexer, disebut Token
Setiap token dapat memiliki jenis yang didefinisikan secara unik, misalnya:
['let', 'const', 'var']
Saya, bagaimanapun, menerapkan skema untuk menentukan jenis token, menggunakan yang disebut Solver'ov.
Ia bekerja sebagai berikut:
1. Anda mendefinisikan konstanta untuk tipe token:
const DefaultTokenTypes = { KEYWORD: "Keyword", IDENTIFIER: "Identifier", OPERATOR: "Operator", DELIMITER: "Delimiter", LINEBREAK: "Linebreak", STRING: "String", NUMERIC: "Numeric", UNKNOWN: 'Unknown' };
2. Selanjutnya, perlu untuk menentukan apa yang disebut Solver'y:
const solvers = {}; solvers[MyTokenTypes.KEYWORD] = { include: [ 'const', 'let' ] }; solvers[MyTokenTypes.NUMERIC] = { regexp: /^[0-9.]*$/gm }; solvers[DefaultTokenTypes.STRING] = { type: StringSolver, delimiters: ['"', "'", '`'] }; solvers[MyTokenTypes.IDENTIFIER] = { regexp: /^[a-zA-Z_][a-zA-Z_0-9]*$/gm }; solvers[MyTokenTypes.DELIMITER] = { default: true };
Seperti yang Anda lihat, token dapat memiliki pengaturan berbeda:
termasuk - Array kata, secara kebetulan, jenis token dapat ditentukan.
regexp - Ekspresi reguler, secara kebetulan, jenis token dapat ditentukan.
default - Jenis standar untuk token yang tidak ditentukan.
Anda juga dapat melihat parameter
tipe , yang menunjukkan bahwa pemecah ini harus diwarisi dari yang ditentukan dalam
tipeDalam hal ini, pemecah mendefinisikan string yang tertutup dalam salah satu karakter yang ditentukan dalam
pembatas3. Kami menggunakan pemecah untuk larik token dan mendapatkan larik token yang diketik. Untuk kode sumber yang diberikan:
let a = 50;
Kami mendapatkan pohon berikut:
[ { "type": "Keyword", "value": "let", "range": [0, 3] }, { "type": "Identifier", "value": "a", "range": [4, 5] }, { "type": "Delimiter", "value": "=", "range": [6, 7] }, { "type": "Numeric", "value": "50", "range": [8, 10] }, { "type": "Delimiter", "value": ";", "range": [10, 11] } ]
Di mana
rentang adalah awal dan akhir fragmen dalam kode sumber.
Parsing
Setelah menerima larik token, Anda harus menguraikannya dan menentukan struktur sintaksis (pohon) dari kode sumber.
Ada berbagai opsi untuk penguraian, tetapi saya memilih algoritma top-down, langsung,.
Token diuraikan satu per satu menggunakan array templat. Jika template cocok dengan urutan token saat ini - di pohon sintaks, cabang baru dibuat.
Contoh satu templat dari array:
let declaration = new SequenceNode({ tokenType: MyTokenTypes.KEYWORD, type: MyNodeTypes.DECLARATION, sequence: [ {type: MyTokenTypes.KEYWORD}, {type: MyTokenTypes.IDENTIFIER}, {type: MyTokenTypes.DELIMITER}, {type: [MyTokenTypes.NUMERIC, MyTokenTypes.STRING]}, ';' ], onError: (e) => {
tokenType - Menjelaskan token untuk mulai memeriksa kecocokan.
type - Menjelaskan tipe node, semua tipe juga harus didefinisikan, mirip dengan tipe token.
sequence - Suatu array dari sequence, berisi jenis token, nilai spesifik, atau node lain dari pohon sintaks.
onError - Callback, yang akan bekerja ketika kesalahan sintaksis
terjadi , saat
mem -parsing node ini, ia mengembalikan tipe kesalahan + tempatnya di kode sumber.
Mari kita menganalisis
urutan simpul ini:
[ {type: MyTokenTypes.KEYWORD},
Saya menerapkan beberapa variasi node, untuk tujuan yang berbeda: mendefinisikan urutan token, mendefinisikan sekelompok elemen (Argumen, blok). Itu memungkinkan fungsi parsing panah tanpa masalah.
Anda dapat membaca tentang semua variasi Pemecah dan Node yang saya terapkan dalam dokumentasi perpustakaan ini.
Material
→ Tautan sumber:
Tyk→
Teori Kompiler Klasik