Stork：如何用 C++ 編寫編程語言

第 1 部分：分詞器

在本系列中，我們將開發一種新的腳本語言並逐步描述該過程。

任何好奇的讀者都會自發想到的第一個問題可能是： “我們真的需要一種新的編程語言嗎？”

我們真的需要一種新的編程語言嗎？

為了回答這個問題，我允許自己稍微題外話。

想像一下，您是一名建築師（實際的實體建築師，而不是軟件建築師），而您不幸出生在一個非常官僚的國家。 你有一個在你不發達的家鄉開一個購物中心的好主意，所以你創建了這個項目併申請了建築許可證。 當然，他們會立即以你沒有註冊公司為由拒絕你。 所以，你註冊了一家公司。 為此，您需要存入一些錢。 然後，您想出一個公司名稱，但被拒絕。 在你第五次嘗試時，它被接受了，你的應用程序進入了堆的底部。 最終，您要么放棄，要么意識到其他人在此期間建立了購物中心。

但我們不是真正的建築師。 我們是軟件工程師，我們有幸在沒有許可或官僚主義的情況下將我們的想法變為現實。 我們唯一需要的就是業餘時間和將其用於編程而不是數獨遊戲的意願。

如果你仍然堅持編程的動機不能純粹是出於好奇，我只想提一下，我設計的第一個編程語言是出於需要而開發的，而不僅僅是出於好奇。 但是，這不應該是閱讀此博客的第一個動機。 我認為您將在這裡遇到的許多想法都相當有趣和創新，即使您實際上並不需要創建自己的編程語言，也能保持您的興趣。

我們開發一種佔用空間小的腳本語言的目標啟發了我將其命名為“Stork”； 幸運的是，我們不需要說服任何官僚批准這個名字。

在我們完成這個系列的過程中，我將開發編程語言，所以我也有可能會開發一些錯誤。 當我們接近系列賽結束時，它們應該被解決。

此處描述的所有內容的完整源代碼可在 GitHub 上免費獲得。

最後，回答本段標題中的問題——不，我們實際上並不需要一種新的編程語言，但由於我們試圖演示如何用 C++ 製作編程語言，我們將創建一個用於演示目的.

Tokenizer 的小幫手

我不知道其他程序員是否經常遇到同樣的問題，但我經常遇到這個問題：

我需要一個鍵值容器，它應該在對數時間內快速檢索值。 但是，一旦我初始化了容器，我就不想向它添加新值。 因此， std::map<Key, Value> （或std::unordered_map<Key, Value> ）是多餘的，因為它也允許快速插入。

我完全反對不必要的優化，但在這種情況下，我覺得很多內存都被浪費了。 不僅如此，以後我們還需要在這樣的容器之上實現一個最大咀嚼算法，而map並不是最好的容器。

第二個選擇是std::vector<std::pair<Key,Value> > ，在插入之後排序。 這種方法的唯一問題是代碼可讀性較差，因為我們需要記住向量是已排序的，因此我開發了一個確保該約束的小類。

（所有函數、類等都在命名空間stork中聲明。為了便於閱讀，我將省略該命名空間。）

 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(); } };

如您所見，這個類的實現非常簡單。 我不想實現所有可能的方法，只是我們需要的那些。 底層容器是一個vector ，因此可以使用預先填充的vector或 initializer_list 對其進行initializer_list 。

分詞器將從輸入流中讀取字符。 在項目的這個階段，我很難決定輸入流是什麼，所以我將使用std::function代替。

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

我將使用 C 風格流函數中眾所周知的約定，例如getc ，它返回一個int而不是char以及一個負數來表示文件結束。

但是，在標記器中假設標記類型之前，提前讀取幾個字符真的很方便。 為此，我實現了一個流，允許我們未讀一些字符。

 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; };

為了節省篇幅，我將省略實現細節，你可以在我的 GitHub 頁面上找到。

如您所見， push_back_stream是從get_character函數初始化的。 重載的operator()用於檢索下一個字符，而push_back用於將字符返回到流中。 line_number和char_number是用於錯誤報告的便捷方法。

請記住， char_index不是當前行中字符的索引，而是整體； 否則，我們必須將所有過去的字符保存在某個容器中才能正確實現push_back函數。

保留令牌

標記器是最低級別的編譯器組件。 它必須讀取輸入和“吐出”標記。 我們感興趣的代幣有四種類型：

• 保留令牌
• 身份標識
• 數字
• 字符串

我們對評論不感興趣，所以分詞器只會“吃掉”它們，而不通知任何人。

為了確保這種語言的吸引力和全球流行，我們將使用眾所周知的類 C 語法。 它適用於 C、C++、JavaScript、Java、C# 和 Objective-C，因此它也必須適用於 Stork。 如果您需要進修課程，可以查閱我們之前的一篇文章，其中涵蓋 C/C++ 學習資源。

這是保留的令牌枚舉：

 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, };

以“kw_”為前綴的枚舉成員是關鍵字。 我必須給它們加上前綴，因為它們通常與 C++ 關鍵字相同。 沒有前綴的是運算符。

幾乎所有這些都遵循 C 約定。 沒有的是：
- concat和concat_assign ( ..和..= )，將用於連接
- idiv和idiv_assign ( \和\= )，將用於整數除法
- kw_var用於變量聲明
- 函數聲明的kw_fun
- kw_number用於數字變量
- kw_string用於字符串變量

我們將根據需要添加其他關鍵字。

有一個值得描述的新關鍵字： kw_elif 。 我堅信單語句塊（沒有花括號）是不值得的。 我不使用它們（而且我不覺得缺少任何東西），除非有兩種情況：

1. 當我在塊之前的for ， while或if語句之後不小心打了分號時。 如果我很幸運，它會返回一個編譯時錯誤，但有時，它會導致一個虛擬的 if 語句和一個始終執行的塊。 幸運的是，這些年來，我從錯誤中吸取了教訓，所以這種情況很少發生。 巴甫洛夫的狗最終也學會了。
2. 當我有“鏈接”的 if 語句時，我有一個 if 塊，然後是一個或多個 else-if 塊，以及可選的一個 else 塊。 從技術上講，當我編寫else if時，這是一個只有一個語句的else塊，即 if 語句。

因此， elif可以用來完全消除無括號語句。 我們是否允許這是一個可以等待的決定。

有兩個幫助函數返回保留的標記：

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

函數get_keyword從傳遞的單詞中返回一個可選關鍵字。 該“單詞”是一系列字母、數字和下劃線，以字母或下劃線開頭。 如果單詞是關鍵字，它將返回一個reserved_token 。 否則，分詞器將假定它是一個標識符。

只要序列是有效的運算符，函數get_operator就會嘗試讀取盡可能多的字符。 如果它讀取更多，它將在最長識別運算符之後未讀取它已讀取的所有額外字符。

為了有效實現這兩個功能，我們需要在string_view和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} };

get_keyword實現非常簡單，但是對於get_operator ，我們需要一個自定義比較器，它將給定字符與候選運算符進行比較，只考慮第 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] ); } };

這是一個普通的詞法比較器，它只考慮位置idx處的字符，但如果字符串更短，它會將其視為位置idx處有一個空字符，這比任何其他字符都小。

這是get_operator的實現，它應該使maximal_munch_operator類更清晰：

 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; }

基本上，我們一開始就把所有算子都當作候選項。 然後，我們逐個字符讀取並通過調用equal_range過濾當前候選對象，僅比較第 n 個字符。 我們不需要比較前面的字符，因為它們已經比較過，我們也不想比較後面的字符，因為它們仍然無關緊要。

每當範圍非空時，我們檢查範圍中的第一個元素是否沒有更多字符（如果存在這樣的元素，它總是在查找排序時位於範圍的開頭）。 在這種情況下，我們匹配了一個合法的運算符。 最長的這種運算符是我們返回的。 在那之後，我們將不讀最終讀到的所有字符。

分詞器

由於令牌是異構的，因此令牌是一個便利類，它包裝了std::variant不同的令牌類型，即：

• 保留令牌
• 標識符
• 數字
• 細繩
• 文件結束

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只是一個具有std::string類型的單個成員的類。 它的存在是為了方便，因為在我看來，如果std::variant的所有替代品都是不同的類型，它會更乾淨。

現在，我們可以編寫分詞器了。 這將是一個接受push_back_stream並返回下一個令牌的函數。

訣竅是根據我們讀取的第一個字符的字符類型使用不同的代碼分支。

• 如果我們讀取文件結尾字符，我們將從函數返回。
• 如果我們讀取一個空格，我們將跳過它。
• 如果我們讀取一個字母數字字符（字母、數字或下劃線），我們將讀取該類型的所有連續字符（如果第一個字符是數字，我們還將讀取點）。 然後，如果第一個字符是數字，我們將嘗試將序列解析為數字。 否則，我們將使用get_keyword函數來檢查它是關鍵字還是標識符。
• 如果我們讀取一個引號，我們會將其視為一個字符串，從其中取消轉義轉義字符。
• 如果我們讀取斜線字符 ( / )，我們將檢查下一個字符是斜線還是星號 ( * )，在這種情況下我們將跳過行/塊註釋。
• 否則，我們將使用get_operator函數。

下面是 tokenize 函數的實現。 我將省略它調用的函數的實現細節。

 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; } } }

您可以看到它在調用較低級別的函數之前將讀取的字符推回。 性能損失幾乎不存在，底層函數代碼更簡潔。

例外

在他對例外的咆哮中，我的兄弟曾經說過：

“有兩種人：一種是拋出異常，另一種是必須捕獲異常。 我總是在那個悲傷的第二組。”

我同意該聲明的精神。 我不是特別喜歡異常，拋出它們會使任何代碼更難維護和閱讀。 幾乎總是。

我決定對該規則做一個例外（雙關語不好）。 從編譯器拋出異常以從編譯深度中解脫出來真的很方便。

這是異常實現：

 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; };

但是，我保證會捕獲頂級代碼中的所有異常。 我什至添加了line_number和char_index成員以進行漂亮的打印，以及執行此操作的函數：

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

包起來

我們系列的第一部分到此結束。 也許這並不太令人興奮，但我們現在有了一個有用的標記器，以及基本的解析錯誤處理。 兩者都是我將在接下來的文章中寫的更有趣的東西的關鍵組成部分。

我希望你從這篇文章中得到一些好的想法，如果你想探索細節，去我的 GitHub 頁面。

進一步閱讀 Toptal 工程博客：

• 如何從頭開始編寫解釋器