Bangau: Cara Membuat Bahasa Pemrograman di C++

Bagian 1: Tokenizer

Dalam seri ini, kami akan mengembangkan bahasa skrip baru dan menjelaskan proses itu selangkah demi selangkah.

Pertanyaan pertama yang secara spontan muncul di benak setiap pembaca yang bertanya-tanya mungkin adalah: "Apakah kita benar-benar membutuhkan bahasa pemrograman baru?"

Apakah Kita Benar-Benar Membutuhkan Bahasa Pemrograman Baru?

Untuk menjawab pertanyaan ini, saya akan membiarkan diri saya melakukan penyimpangan kecil.

Bayangkan Anda adalah seorang arsitek (arsitek bata-dan-mortir yang sebenarnya, bukan perangkat lunak), dan Anda cukup beruntung untuk dilahirkan di negara yang sangat birokratis. Anda memiliki ide bagus untuk membangun pusat perbelanjaan di kota asal Anda yang belum berkembang, jadi Anda membuat proyek dan mengajukan izin bangunan. Tentu saja, mereka langsung menolak Anda dengan alasan Anda tidak memiliki perusahaan terdaftar. Jadi, Anda mendaftarkan perusahaan. Untuk melakukan itu, Anda perlu menyetor sejumlah uang. Kemudian, Anda menemukan nama untuk perusahaan Anda, yang ditolak. Pada percobaan kelima Anda, itu diterima, dan aplikasi Anda pergi ke bagian bawah tumpukan. Pada akhirnya, Anda menyerah atau menyadari bahwa orang lain membangun pusat perbelanjaan sementara itu.

Tapi kami bukan arsitek asli. Kami adalah insinyur perangkat lunak, dan kami memiliki hak istimewa untuk mewujudkan ide-ide kami tanpa izin atau birokrasi. Satu-satunya hal yang kita butuhkan adalah waktu luang dan keinginan untuk menghabiskannya pada pemrograman daripada teka-teki sudoku.

Jika Anda masih bersikeras bahwa motivasi untuk pemrograman tidak dapat murni rasa ingin tahu, izinkan saya menyebutkan bahwa bahasa pemrograman pertama yang saya rancang dikembangkan sebagai hasil dari kebutuhan, bukan sekadar rasa ingin tahu. Namun, itu seharusnya tidak menjadi motivasi pertama untuk membaca blog ini. Saya rasa banyak ide yang akan Anda temui di sini cukup menarik dan inovatif untuk membuat Anda tetap tertarik meskipun Anda sebenarnya tidak perlu membuat bahasa pemrograman sendiri.

Tujuan kami mengembangkan bahasa scripting small-footprint mengilhami saya untuk menamakannya “Stork”; dan untungnya, kita tidak perlu meyakinkan birokrat mana pun untuk menyetujui nama itu.

Saya akan mengembangkan bahasa pemrograman saat kita melewati seri ini, jadi ada kemungkinan saya akan mengembangkan beberapa bug juga. Mereka harus disetrika saat kita mendekati akhir seri.

Kode sumber lengkap untuk semua yang dijelaskan di sini tersedia secara gratis di GitHub.

Terakhir, untuk menjawab pertanyaan dari judul paragraf ini—tidak, sebenarnya kita tidak membutuhkan bahasa pemrograman baru, tetapi karena kita mencoba mendemonstrasikan cara membuat bahasa pemrograman di C++, kita akan membuatnya untuk tujuan demonstrasi. .

Pembantu Kecil Tokenizer

Saya tidak tahu apakah programmer lain menghadapi masalah yang sama secara teratur, tetapi saya cukup sering menghadapi masalah ini:

Saya membutuhkan wadah nilai kunci yang harus mengambil nilai dengan cepat, dalam waktu logaritmik. Namun, setelah saya menginisialisasi wadah, saya tidak ingin menambahkan nilai baru ke dalamnya. Oleh karena itu, std::map<Key, Value> (atau std::unordered_map<Key, Value> ) berlebihan, karena memungkinkan penyisipan cepat juga.

Saya sepenuhnya menentang pengoptimalan yang tidak perlu, tetapi dalam kasus ini, saya merasa banyak memori yang terbuang sia-sia. Tidak hanya itu, tetapi nanti, kita perlu menerapkan algoritma mengunyah maksimal di atas wadah seperti itu, dan map bukanlah wadah terbaik untuk itu.

Pilihan kedua adalah std::vector<std::pair<Key,Value> > , diurutkan setelah penyisipan. Satu-satunya masalah dengan pendekatan itu adalah keterbacaan kode yang lebih rendah karena kita perlu mengingat bahwa vektor diurutkan, jadi saya mengembangkan kelas kecil yang memastikan batasan itu.

(Semua fungsi, kelas, dll. dideklarasikan di namespace stork . Saya akan menghilangkan namespace itu agar mudah dibaca.)

 template <typename Key, typename Value> class lookup { public: using value_type = std::pair<Key, Value>; using container_type = std::vector<value_type>; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list<value_type> init) : _container(init) { std::sort(_container.begin(), _container.end()); } lookup(container_type container) : _container(std::move(container)) { std::sort(_container.begin(), _container.end()); } const_iterator begin() const { return _container.begin(); } const_iterator end() const { return _container.end(); } template <typename K> const_iterator find(const K& key) const { const_iterator it = std::lower_bound( begin(), end(), key, [](const value_type& p, const K& key) { return p.first < key; } ); return it != end() && it->first == key ? it : end(); } size_t size() const { return _container.size(); } };

Seperti yang Anda lihat, implementasi kelas ini cukup sederhana. Saya tidak ingin menerapkan semua metode yang mungkin, hanya metode yang akan kita perlukan. Wadah yang mendasarinya adalah vector , sehingga dapat diinisialisasi dengan vector yang sudah terisi sebelumnya, atau dengan initializer_list .

Tokenizer akan membaca karakter dari aliran input. Pada tahap proyek ini, sulit bagi saya untuk memutuskan apa aliran inputnya, jadi saya akan menggunakan std::function sebagai gantinya.

 using get_character = std::function<int()>;

Saya akan menggunakan konvensi terkenal dari fungsi aliran gaya-C, seperti getc , yang mengembalikan int alih-alih char serta angka negatif untuk menandakan akhir file.

Namun, sangat nyaman untuk membaca beberapa karakter terlebih dahulu, sebelum asumsi jenis token di tokenizer. Untuk itu, saya menerapkan aliran yang memungkinkan kita untuk tidak membaca beberapa karakter.

 class push_back_stream { private: const get_character& _input; std::stack<int> _stack; size_t _line_number; size_t _char_index; public: push_back_stream(const get_character& input); int operator()(); void push_back(int c); size_t line_number() const; size_t char_index() const; };

Untuk menghemat ruang, saya akan menghilangkan detail implementasi, yang dapat Anda temukan di halaman GitHub saya.

Seperti yang Anda lihat, push_back_stream diinisialisasi dari fungsi get_character . operator() digunakan untuk mengambil karakter berikutnya, dan push_back digunakan untuk mengembalikan karakter kembali ke aliran. line_number dan char_number adalah metode praktis yang digunakan untuk laporan kesalahan.

Ingatlah bahwa char_index bukan indeks karakter di baris saat ini tetapi secara keseluruhan; jika tidak, kita harus menyimpan semua karakter sebelumnya di beberapa wadah untuk mengimplementasikan fungsi push_back dengan benar.

Token Cadangan

Tokenizer adalah komponen penyusun level terendah. Itu harus membaca token input dan "spit-out". Ada empat jenis token yang menarik bagi kami:

• Token yang dipesan
• pengenal
• angka
• string

Kami tidak tertarik dengan komentar, jadi tokenizer hanya akan "memakannya", tanpa memberi tahu siapa pun.

Untuk memastikan daya tarik dan popularitas planet dari bahasa ini, kami akan menggunakan sintaks mirip C yang terkenal. Ini bekerja cukup baik untuk C, C++, JavaScript, Java, C#, dan Objective-C, jadi itu harus bekerja untuk Bangau juga. Jika Anda memerlukan kursus penyegaran, Anda dapat membaca salah satu artikel kami sebelumnya yang membahas sumber belajar C/C++.

Berikut adalah pencacahan token yang dipesan:

 enum struct reserved_token { inc, dec, add, sub, concat, mul, div, idiv, mod, bitwise_not, bitwise_and, bitwise_or, bitwise_xor, shiftl, shiftr, assign, add_assign, sub_assign, concat_assign, mul_assign, div_assign, idiv_assign, mod_assign, and_assign, or_assign, xor_assign, shiftl_assign, shiftr_assign, logical_not, logical_and, logical_or, eq, ne, lt, gt, le, ge, question, colon, comma, semicolon, open_round, close_round, open_curly, close_curly, open_square, close_square, kw_if, kw_else, kw_elif, kw_switch, kw_case, kw_default, kw_for, kw_while, kw_do, kw_break, kw_continue, kw_return, kw_var, kw_fun, kw_void, kw_number, kw_string, };

Anggota pencacahan yang diawali dengan “kw_” adalah kata kunci. Saya harus mengawalinya karena biasanya sama dengan kata kunci C++. Yang tanpa awalan adalah operator.

Hampir semuanya mengikuti konvensi C. Yang tidak adalah:
- concat dan concat_assign ( .. and ..= ), yang akan digunakan untuk penggabungan
- idiv dan idiv_assign ( \ dan \= ), yang akan digunakan untuk pembagian bilangan bulat
- kw_var untuk deklarasi variabel
- kw_fun untuk deklarasi fungsi
- kw_number untuk variabel angka
- kw_string untuk variabel string

Kami akan menambahkan kata kunci tambahan, sesuai kebutuhan.

Ada satu kata kunci baru yang pantas untuk dijelaskan: kw_elif . Saya sangat percaya bahwa blok pernyataan tunggal (tanpa kurung kurawal) tidak sepadan. Saya tidak menggunakannya (dan saya tidak merasa ada yang hilang), kecuali pada dua kesempatan:

1. Ketika saya secara tidak sengaja menekan titik koma segera setelah pernyataan for , while , atau if sebelum blok. Jika saya beruntung, ini mengembalikan kesalahan waktu kompilasi, tetapi terkadang, ini menghasilkan pernyataan if dummy dan blok yang selalu dieksekusi. Untungnya, selama bertahun-tahun, saya telah belajar dari kesalahan saya, jadi itu sangat jarang terjadi. Anjing Pavlov juga belajar, akhirnya.
2. Ketika saya memiliki pernyataan if "merantai", jadi saya memiliki blok if, lalu satu atau lebih blok if-lain, dan secara opsional, blok-lain. Secara teknis, ketika saya menulis else if , itu adalah blok else dengan hanya satu pernyataan, yaitu pernyataan if itu.

Oleh karena itu, elif dapat digunakan untuk menghilangkan pernyataan braceless sepenuhnya. Apakah kita mengizinkannya atau tidak, itu adalah keputusan yang bisa menunggu untuk saat ini.

Ada dua fungsi pembantu yang mengembalikan token yang dicadangkan:

 std::optional<reserved_token> get_keyword(std::string_view word); std::optional<reserved_token> get_operator(push_back_stream& stream);

Fungsi get_keyword mengembalikan kata kunci opsional dari kata yang diteruskan. “Kata” itu adalah urutan huruf, angka, dan garis bawah, dimulai dengan huruf atau garis bawah. Ini akan mengembalikan reserved_token jika kata tersebut adalah kata kunci. Jika tidak, tokenizer akan menganggap bahwa itu adalah pengidentifikasi.

Fungsi get_operator mencoba membaca karakter sebanyak mungkin, selama urutannya adalah operator yang valid. Jika membaca lebih banyak, itu akan menghapus semua karakter tambahan yang telah dibacanya setelah operator yang paling lama dikenali.

Untuk implementasi yang efektif dari kedua fungsi tersebut, kita memerlukan dua pencarian antara string_view dan reserved_keyword .

 const lookup<std::string_view, reserved_token> operator_token_map { {"++", reserved_token::inc}, {"--", reserved_token::dec}, {"+", reserved_token::add}, {"-", reserved_token::sub}, {"..", reserved_token::concat}, /*more exciting operators*/ }; const lookup<std::string_view, reserved_token> keyword_token_map { {"if", reserved_token::kw_if}, {"else", reserved_token::kw_else}, {"elif", reserved_token::kw_elif}, {"switch", reserved_token::kw_switch}, {"case", reserved_token::kw_case}, {"default", reserved_token::kw_default}, {"for", reserved_token::kw_for}, {"while", reserved_token::kw_while}, {"do", reserved_token::kw_do}, {"break", reserved_token::kw_break}, {"continue", reserved_token::kw_continue}, {"return", reserved_token::kw_return}, {"var", reserved_token::kw_var}, {"fun", reserved_token::kw_fun}, {"void", reserved_token::kw_void}, {"number", reserved_token::kw_number}, {"string", reserved_token::kw_string} };

Implementasi get_keyword benar-benar mudah, tetapi untuk get_operator , kita memerlukan pembanding khusus yang akan membandingkan karakter tertentu dengan kandidat operator, dengan hanya memperhitungkan karakter ke-n.

 class maximal_munch_comparator{ private: size_t _idx; public: maximal_munch_comparator(size_t idx) : _idx(idx) { } bool operator()(char l, char r) const { return l < r; } bool operator()( std::pair<std::string_view, reserved_token> l, char r ) const { return l.first.size() <= _idx || l.first[_idx] < r; } bool operator()( char l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && l < r.first[_idx]; } bool operator()( std::pair<std::string_view, reserved_token> l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && ( l.first.size() < _idx || l.first[_idx] < r.first[_idx] ); } };

Itu adalah pembanding leksikal biasa yang memperhitungkan hanya karakter pada posisi idx , tetapi jika string lebih pendek, ia memperlakukannya seolah-olah memiliki karakter nol pada posisi idx , yang lebih rendah daripada karakter lainnya.

Ini adalah implementasi get_operator , yang seharusnya membuat kelas maximal_munch_operator lebih jelas:

 std::optional<reserved_token> get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional<reserved_token> ret; size_t match_size = 0; std::stack<int> chars; for (size_t idx = 0; candidates.first != candidates.second; ++idx) { chars.push(stream()); candidates = std::equal_range( candidates.first, candidates.second, char(chars.top()), maximal_munch_comparator(idx) ); if ( candidates.first != candidates.second && candidates.first->first.size() == idx + 1 ) { match_size = idx + 1; ret = candidates.first->second; } } while (chars.size() > match_size) { stream.push_back(chars.top()); chars.pop(); } return ret; }

Pada dasarnya, kami memperlakukan semua operator sebagai kandidat di awal. Kemudian, kita membaca karakter demi karakter dan memfilter kandidat saat ini dengan memanggil equal_range , hanya membandingkan karakter ke-n. Kami tidak perlu membandingkan karakter sebelumnya karena mereka sudah dibandingkan, dan kami tidak ingin membandingkan karakter berikutnya karena masih tidak relevan.

Setiap kali rentang tidak kosong, kami memeriksa apakah elemen pertama dalam rentang tidak memiliki karakter lagi (jika elemen seperti itu ada, selalu ada di awal rentang saat pencarian diurutkan). Dalam hal ini, kami memiliki operator hukum yang cocok. Operator terpanjang seperti itu adalah yang kami kembalikan. Kami akan menghapus semua karakter yang akhirnya kami baca setelah itu.

Tokenizer

Karena token bersifat heterogen, token adalah kelas praktis yang membungkus std::variant tipe token yang berbeda, yaitu:

• Token yang dipesan
• pengenal
• Nomor
• Rangkaian
• Akhir file

 class token { private: using token_value = std::variant<reserved_token, identifier, double, std::string, eof>; token_value _value; size_t _line_number; size_t _char_index; public: token(token_value value, size_t line_number, size_t char_index); bool is_reserved_token() const; bool is_identifier() const; bool is_number() const; bool is_string() const; bool is_eof() const; reserved_token get_reserved_token() const; std::string_view get_identifier() const; double get_number() const; std::string_view get_string() const; size_t get_line_number() const; size_t get_char_index() const; };

identifier hanyalah sebuah kelas dengan satu anggota tipe std::string . Itu ada untuk kenyamanan karena, menurut saya, std::variant lebih bersih jika semua alternatifnya adalah tipe yang berbeda.

Sekarang, kita dapat menulis tokenizer. Ini akan menjadi salah satu fungsi yang akan menerima push_back_stream dan mengembalikan token berikutnya.

Caranya adalah dengan menggunakan cabang kode yang berbeda, berdasarkan tipe karakter dari karakter pertama yang kita baca.

• Jika kita membaca karakter akhir file, kita akan kembali dari fungsi.
• Jika kita membaca spasi, kita akan melewatkannya.
• Jika kita membaca karakter alfanumerik (huruf, angka, atau garis bawah), kita akan membaca semua karakter berurutan dari jenis itu (kita juga akan membaca titik jika karakter pertama adalah digit). Kemudian, jika karakter pertama adalah angka, kami akan mencoba mengurai urutannya sebagai angka. Jika tidak, kita akan menggunakan fungsi get_keyword untuk memeriksa apakah itu kata kunci atau pengenal.
• Jika kita membaca tanda kutip, kita akan memperlakukannya sebagai string, melepaskan karakter yang lolos darinya.
• Jika kita membaca karakter garis miring ( / ), kita akan memeriksa apakah karakter berikutnya adalah garis miring atau tanda bintang ( * ), dan kita akan melewatkan komentar baris/blok dalam kasus itu.
• Jika tidak, kita akan menggunakan fungsi get_operator .

Berikut adalah implementasi fungsi tokenize. Saya akan menghilangkan detail implementasi fungsi yang dipanggilnya.

 token tokenize(push_back_stream& stream) { while (true) { size_t line_number = stream.line_number(); size_t char_index = stream.char_index(); int c = stream(); switch (get_character_type(c)) { case character_type::eof: return {eof(), line_number, char_index}; case character_type::space: continue; case character_type::alphanum: stream.push_back(c); return fetch_word(stream); case character_type::punct: switch (c) { case '"': return fetch_string(stream); case '/': { char c1 = stream(); switch(c1) { case '/': skip_line_comment(stream); continue; case '*': skip_block_comment(stream); continue; default: stream.push_back(c1); } } default: stream.push_back(c); return fetch_operator(stream); } break; } } }

Anda dapat melihat bahwa itu mendorong kembali karakter yang dibacanya sebelum memanggil fungsi tingkat yang lebih rendah. Penalti kinerja hampir tidak ada, dan kode fungsi tingkat yang lebih rendah jauh lebih bersih.

Pengecualian

Dalam salah satu omelannya terhadap pengecualian, saudara laki-laki saya pernah berkata:

“Ada dua jenis orang: mereka yang melempar pengecualian dan mereka yang harus menangkapnya. Saya selalu berada di grup kedua yang menyedihkan itu.”

Saya setuju dengan semangat pernyataan itu. Saya tidak terlalu suka pengecualian, dan membuangnya dapat membuat kode apa pun lebih sulit untuk dipelihara dan dibaca. Hampir selalu.

Saya memutuskan untuk membuat pengecualian (permainan kata yang buruk) untuk aturan itu. Sangat mudah untuk membuang pengecualian dari kompiler untuk bersantai dari kedalaman kompilasi.

Berikut adalah implementasi pengecualian:

 class error: public std::exception { private: std::string _message; size_t _line_number; size_t _char_index; public: error(std::string message, size_t line_number, size_t char_index) noexcept; const char* what() const noexcept override; size_t line_number() const noexcept; size_t char_index() const noexcept; };

Namun, saya berjanji untuk menangkap semua pengecualian dalam kode tingkat atas. Saya bahkan menambahkan anggota line_number dan char_index untuk pencetakan cantik, dan fungsi yang melakukannya:

 void format_error( const error& err, get_character source, std::ostream& output );

Membungkus

Itu menyimpulkan bagian pertama dari seri kami. Mungkin itu tidak terlalu menarik, tetapi kami sekarang memiliki tokenizer yang berguna, bersama dengan penanganan kesalahan penguraian dasar. Keduanya merupakan blok bangunan penting untuk hal-hal yang lebih menarik yang akan saya tulis di artikel mendatang.

Saya harap Anda mendapat beberapa ide bagus dari posting ini, dan jika Anda ingin menjelajahi detailnya, buka halaman GitHub saya.

Bacaan Lebih Lanjut di Blog Teknik Toptal:

• Bagaimana Pendekatan Menulis Penerjemah Dari Awal