コウノトリ：C++でプログラミング言語を作成する方法

公開: 2022-03-11

パート1：トークナイザー

このシリーズでは、新しいスクリプト言語を開発し、そのプロセスを段階的に説明します。

不思議な読者の頭に浮かぶ最初の質問は、 「本当に新しいプログラミング言語が必要なのか」ということでしょう。

本当に新しいプログラミング言語が必要ですか？

この質問に答えるために、私は自分自身に少し余談を許します。

あなたが建築家（ソフトウェアではなく実際の実店舗の建築家）であり、非常に官僚的な国で生まれるほど運が悪いと想像してみてください。あなたは未開発の故郷にあるショッピングモールの素晴らしいアイデアを持っているので、プロジェクトを作成して建築許可を申請します。もちろん、彼らはあなたが登録された会社を持っていないという理由であなたをすぐに拒絶します。だから、あなたは会社を登録します。それをするために、あなたはいくらかのお金を預ける必要があります。次に、あなたはあなたの会社の名前を思いつきますが、それは拒否されます。 5回目の試行で、それは受け入れられ、アプリケーションはヒープの一番下に移動します。最終的に、あなたはあきらめるか、誰かがその間にショッピングモールを建てたことに気づきます。

しかし、私たちは本物の建築家ではありません。私たちはソフトウェアエンジニアであり、許可や官僚主義なしにアイデアを実現する特権を持っています。必要なのは、暇な時間と、数独パズルの代わりにプログラミングに費やす意志だけです。

それでもプログラミングの動機が純粋な好奇心ではないと主張する場合は、私が設計した最初のプログラミング言語は、単なる好奇心ではなく、必要性の結果として開発されたものです。しかし、それがこのブログを読む最初の動機ではないはずです。ここで出会うアイデアの多くは、実際に独自のプログラミング言語を作成する必要がない場合でも、興味を持ってもらうためにかなり興味深く革新的だと思います。

フットプリントの小さいスクリプト言語を開発するという私たちの目標は、それを「コウノトリ」と名付けるように促しました。幸いなことに、名前を承認するように官僚を説得する必要はありません。

シリーズを進めながらプログラミング言語を開発していくので、バグも発生する可能性があります。シリーズの終わりに近づくにつれて、それらは解決されるべきです。

ここで説明するすべての完全なソースコードは、GitHubで無料で入手できます。

最後に、この段落のタイトルからの質問に答えるために、いいえ、実際には新しいプログラミング言語は必要ありませんが、C ++でプログラミング言語を作成する方法をデモンストレーションしようとしているため、デモンストレーション用に作成します。。

Tokenizerのリトルヘルパー

他のプログラマーが定期的に同じ問題に直面しているかどうかはわかりませんが、この問題に頻繁に直面しています。

対数時間で値を高速に取得する必要があるKey-Valueコンテナーが必要です。ただし、コンテナを初期化した後は、新しい値を追加したくありません。したがって、 std::map<Key, Value> （またはstd::unordered_map<Key, Value> ）は、高速挿入も可能にするため、やり過ぎです。

不必要な最適化には完全に反対ですが、この場合、多くのメモリが無駄になっているように感じます。それだけでなく、後で、そのようなコンテナの上に最大のムンクアルゴリズムを実装する必要があります。 mapはそのための最適なコンテナではありません。

2番目の選択肢は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を使用して初期化できます。

トークナイザーは、入力ストリームから文字を読み取ります。プロジェクトのこの段階では、入力ストリームを決定するのは難しいので、代わりにstd::functionを使用します。

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

getcなどのCスタイルのストリーム関数でよく知られている規則を使用します。getcは、 charの代わりにintを返し、ファイルの終わりを示す負の数を返します。

ただし、トークナイザーでトークンタイプを想定する前に、事前に2、3文字を読み取ると非常に便利です。そのために、一部の文字を未読にするストリームを実装しました。

 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関数を正しく実装するために、過去のすべての文字をいくつかのコンテナーに保持する必要があります。

予約済みトークン

トークナイザーは、最下位レベルのコンパイラコンポーネントです。入力トークンと「吐き出し」トークンを読み取る必要があります。私たちが関心を持っているトークンには、次の4つのタイプがあります。

予約済みトークン
識別子
数字
文字列

コメントには関心がないため、トークナイザーは誰にも通知せずにコメントを「食べる」だけです。

この言語の魅力と惑星での人気を確実にするために、よく知られているCのような構文を使用します。 C、C ++、JavaScript、Java、C＃、Objective-Cで非常にうまく機能したため、Storkでも機能する必要があります。復習コースが必要な場合は、C /C++学習リソースに関する以前の記事の1つを参照してください。

予約済みトークンの列挙は次のとおりです。

 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

必要に応じてキーワードを追加します。

説明する価値のある新しいキーワードが1つあります： kw_elif 。私は、単一ステートメントのブロック（中括弧なし）は価値がないと確信しています。次の2つの場合を除いて、私はそれらを使用しません（そして、何かが欠けているとは感じません）。

for 、 while 、またはifステートメントの直後に誤ってセミコロンをブロックの前にヒットしたとき。運が良ければ、コンパイル時エラーが返されますが、ダミーのifステートメントと常に実行されるブロックが発生する場合があります。幸いなことに、私は何年にもわたって自分の過ちから学んだので、それが起こることはめったにありません。パブロフの犬も、最終的には学びました。
ifステートメントを「連鎖」させた場合、ifブロック、1つ以上のelse-ifブロック、およびオプションでelseブロックがあります。技術的には、 else ifを書くと、それは1つのステートメントのみを持つelseブロック、つまりifステートメントです。

したがって、 elifを使用して、中括弧のないステートメントを完全に削除できます。それを許可するかどうかは、今のところ待つことができる決定です。

予約済みトークンを返す2つのヘルパー関数があります。

 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は、シーケンスが有効な演算子である限り、できるだけ多くの文字を読み取ろうとしています。さらに読み取ると、認識された最長の演算子の後に読み取った余分な文字がすべて読み取られなくなります。

これら2つの関数を効果的に実装するには、 string_viewとreserved_keywordの間で2つのルックアップが必要です。

 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を受け入れ、次のトークンを返す1つの関数になります。

秘訣は、最初に読んだ文字の文字タイプに基づいて、さまざまなコードブランチを使用することです。

ファイルの終わり文字を読み取ると、関数から戻ります。
空白を読み取る場合は、スキップします。
英数字（文字、数字、またはアンダースコア）を読み取る場合、そのタイプの連続するすべての文字を読み取ります（最初の文字が数字の場合は、ドットも読み取ります）。次に、最初の文字が数字の場合、シーケンスを数値として解析しようとします。それ以外の場合は、 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; } } }

下位レベルの関数を呼び出す前に、読み取った文字をプッシュバックすることがわかります。パフォーマンスの低下はほとんどなく、低レベルの関数コードははるかにクリーンです。

例外

例外に対する彼の暴言の1つで、私の兄弟はかつて言った：

「例外をスローする人と、例外をキャッチする必要がある人の2種類があります。 私はいつもその悲しい第二のグループにいます。」

私はその声明の精神に同意します。私は特に例外が好きではありません。例外をスローすると、コードの保守と読み取りが非常に難しくなる可能性があります。ほとんどいつも。

私はそのルールに例外を設けることにしました（駄洒落が意図されています）。コンパイラから例外をスローして、コンパイルの深さから解放するのは非常に便利です。

例外の実装は次のとおりです。

 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 Engineeringブログでさらに読む：

インタプリタを最初から書く方法